REVERSE A LINKED LIST IN A DATA STRUCTURE
Reversing a linked list in a data structure means changing the direction(right to left,left to right) of these links so that the order of the nodes becomes opposite. In other words, the first node becomes the last, the last becomes the first, and all intermediate connections are reversed.
For example:
A linked list is a linear data structure where elements (nodes) are connected using pointers. Each node typically contains:
- Data(the value stored)
- Next(a pointer to the next node)
Reversing a linked list means changing the direction of links(data,next).
A linked list is a fundamental data structure in which elements, called nodes, are connected through links instead of being stored in continuous memory locations. Each node typically contains some data and a reference (or pointer) to the next node in the sequence. In a singly linked list, the last node points to NULL, indicating the end of the list.
Original list:
21 → 22 → 23 → 24 → NULL
Reversed list:
24 → 23 → 22 → 21 → NULL
This operation does not create new nodes; instead, it rearranges the existing links between the nodes. Reversing a linked list is an important concept in data structures because it improves understanding of pointer manipulation and logical problem-solving. It is also a common programming question in exams and technical interviews.
Overall, learning how to reverse a linked list helps build a strong foundation in working with dynamic data structures and memory management.
Why Do We Reverse a Linked List?
It helps in understanding pointer manipulation
It is frequently asked in programming interviews
It is used in applications like undo operations, stack implementation, and algorithm design
Methods to Reverse a Linked List
There are mainly two methods:
1️⃣ Iterative Method
Uses three pointers: prev, current, and next
Changes links one by one
Time Complexity: O(n)
Space Complexity: O(1)
2️⃣ Recursive Method
Uses the function call stack
Reverses the list using recursion
Time Complexity: O(n)
Space Complexity: O(n) (due to recursion stack)
Conclusion
Reversing a linked list is a basic but very important concept. It helps improve understanding of:
Pointers
Memory management
Logical thinking in programming
For Example:
Original List:10->20->30->40->NULL
Reversed List:40->30->20->10->NULL
Reversing a linked list is a useful operation in which we change next to prev, prev to current, and current to next. Reverse a linked list means changing the direction of the pointers so that the head becomes the last node, and the last node becomes the head.
/* Program to reverse a linked list in Data Structure*/
# include <stdio.h>
# include <malloc.h>
struct nod
{
int info;
struct nod *liink;
}*strt;
main()
{
int i,n,item;
strt=NULL;
printf(“How many nods you want : “);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“Enter the item %d : “,i+1);
scanf(“%d”,&item);
create_list(item);
}
printf(” The final liinked list is :\n”);
display();
reverse();
printf(“liinked list after reversing is :\n”);
display();
}/*End of main()*/
create_list(int num)
{
struct nod *q,*tmp;
tmp= malloc(sizeof(struct nod));
tmp->info=num;
tmp->liink=NULL;
if(strt==NULL)
strt=tmp;
else
{
q=strt;
while(q->liink!=NULL)
q=q->liink;
q->liink=tmp;
}
}/*End of create_list() */
display()
{
struct nod *q;
if(strt == NULL)
{
printf(“Oh!List is empty\n”);
return;
}
q=strt;
while(q!=NULL)
{
printf(“%d “, q->info);
q=q->liink;
}
printf(“\n”);
}/*End of display()*/
reverse()
{
struct nod *p1,*p2,*p3;
if(strt->liink==NULL) /*only 1 element*/
return;
p1=strt;
p2=p1->liink;
p3=p2->liink;
p1->liink=NULL;
p2->liink=p1;
while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->liink;
p2->liink=p1;
}
strt=p2;
}/*End of reverse() */
Algorithm (Iterative Method)
To reverse a singly linked list, we use three pointers:
prev – to store the previous node (initially NULL)
current – to store the current node (starts from head)
next – to store the next node
Steps:
Initialize prev = NULL and current = head.
Repeat until current becomes NULL:
Store next node: next = current.next
Reverse the link: current.next = prev
Move prev forward: prev = current
Move current forward: current = next
At the end, prev will be the new head of the reversed list.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1) (no extra memory used)
Conclusion
Reversing a linked list is a common and important operation in data structures. It helps in understanding pointer manipulation and improves problem-solving skills in programming.