YouTipC Exercise Example73
# C Programming Exercise - Example 73: Print a Linked List in Reverse Order
This tutorial provides a comprehensive guide on how to work with singly linked lists in C, specifically focusing on creating a linked list and printing its elements in reverse order.
---
## 1. Introduction
A **Singly Linked List** is a fundamental linear data structure where elements (nodes) are not stored in contiguous memory locations. Instead, each node contains a data field and a pointer (reference) to the next node in the sequence.
In this exercise, we will:
1. Dynamically allocate and construct a singly linked list with a dummy head node.
2. Populate the list with user-defined integer values.
3. Print the list in its original order.
4. Implement a clean, recursive solution to print the linked list in **reverse order** without modifying the original structure.
---
## 2. Problem Analysis & Algorithm Design
### The Challenge
Given a singly linked list, we want to print its elements from the last node to the first node.
### Solutions
There are multiple ways to reverse-print a linked list:
1. **Recursion (Recommended for simplicity):** By using the call stack, we can traverse to the end of the list first, and print the node values as the recursive calls unwind.
2. **Using an Auxiliary Stack:** Push all node values onto a stack, then pop and print them.
3. **Reversing the List:** Physically reverse the pointers of the linked list, print it, and then reverse it back (or leave it reversed).
In this tutorial, we will demonstrate the **Recursive Approach** because it is elegant, requires no extra data structures, and does not alter the original list structure.
---
## 3. Code Implementation
Below is the complete, production-ready C program. It includes the logic to create a linked list, print it forward, and print it in reverse using recursion.
```c
#include
#include
// Define the structure of a Node
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
// Function Prototypes
LinkList CreateList(int n);
void PrintForward(LinkList h);
void PrintReverse(LinkList p);
int main() {
LinkList Head = NULL;
int n;
printf("Enter the number of elements to create: ");
if (scanf("%d", &n) != 1 || n <= 0) {
printf("Invalid input. Please enter a positive integer.\n");
return 1;
}
// Create the linked list
Head = CreateList(n);
if (Head == NULL) {
printf("Memory allocation failed.\n");
return 1;
}
// Print the list in forward order
printf("\nThe elements in the created linked list (Forward): \n");
PrintForward(Head);
printf("\n");
// Print the list in reverse order
printf("\nThe elements in the linked list (Reverse): \n");
// Pass Head->next to skip the dummy head node
PrintReverse(Head->next);
printf("\n\n");
// Free allocated memory
LinkList temp;
while (Head != NULL) {
temp = Head;
Head = Head->next;
free(temp);
}
return 0;
}
/**
* Creates a singly linked list with a dummy head node.
* @param n Number of elements to insert.
* @return Pointer to the dummy head node of the created list.
*/
LinkList CreateList(int n) {
LinkList L, p, q;
int i;
// Allocate memory for the dummy head node
L = (LinkList)malloc(sizeof(LNode));
if (!L) return NULL;
L->next = NULL;
q = L; // q always points to the current tail node
for (i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(LNode));
if (!p) return NULL;
printf("Enter value for element %d: ", i);
if (scanf("%d", &(p->data)) != 1) {
printf("Invalid input.\n");
return NULL;
}
p->next = NULL;
q->next = p; // Link the new node to the end of the list
q = p; // Move the tail pointer to the new node
}
return L;
}
/**
* Prints the linked list in forward order.
* @param h Pointer to the dummy head node.
*/
void PrintForward(LinkList h) {
if (h == NULL) return;
LinkList p = h->next; // Skip the dummy head node
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
/**
* Recursively prints the linked list in reverse order.
* @param p Pointer to the first data node (Head->next).
*/
void PrintReverse(LinkList p) {
if (p == NULL) {
return; // Base case: end of the list
}
// Recursive step: Go to the next node first
PrintReverse(p->next);
// Print the current node's data during backtracking
printf("%d ", p->data);
}
```
---
## 4. Detailed Code Explanation
### A. Node Structure Definition
```c
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
```
* `LNode` represents a single node containing an integer `data` and a pointer `next` pointing to the next node.
* `LinkList` is defined as a pointer type to `LNode` (`LNode*`), making the code cleaner and easier to read.
### B. Dummy Head Node Pattern
In `CreateList`, we allocate a dummy head node `L` that does not store actual data. Its primary purpose is to simplify list operations (like insertion and deletion) by ensuring that the first actual data node is treated the same as subsequent nodes.
### C. The Recursive Reverse Printing Logic
The core of the reverse printing is implemented in `PrintReverse`:
```c
void PrintReverse(LinkList p) {
if (p == NULL) {
return;
}
PrintReverse(p->next);
printf("%d ", p->data);
}
```
* **Base Case:** If the current node pointer `p` is `NULL`, the function returns immediately.
* **Recursive Call:** `PrintReverse(p->next)` is called before printing the current node. This pushes the current node onto the system call stack and moves to the next node.
* **Backtracking (Printing):** Once the end of the list is reached, the recursive calls begin to return (unwind). As each call returns, `printf("%d ", p->data)` executes, printing the elements from last to first.
---
## 5. Execution & Output Example
### Input
```text
Enter the number of elements to create: 5
Enter value for element 1: 10
Enter value for element 2: 20
Enter value for element 3: 30
Enter value for element 4: 40
Enter value for element 5: 50
```
### Output
```text
The elements in the created linked list (Forward):
10 20 30 40 50
The elements in the linked list (Reverse):
50 40 30 20 10
```
---
## 6. Key Considerations & Best Practices
1. **Memory Management:** Always free the dynamically allocated memory (`malloc`) using `free()` when the linked list is no longer needed to prevent memory leaks.
2. **Stack Overflow Risk:** The recursive approach uses the system call stack. For extremely large linked lists (e.g., millions of nodes), recursion can cause a **Stack Overflow**. In such production scenarios, an iterative approach using an explicit stack or reversing the list in-place is preferred.
3. **Input Validation:** Always validate user inputs (`scanf` return values) to prevent infinite loops or undefined behavior when non-integer values are entered.