DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)
Linked List in C- Reversing a Linked List :
Input:
Linked List: one->two->three->four
head pointer points to first node “one”
Output:
Linked List: four->three->two->one
head pointer points to first node “four”
Source Code :
#include<stdio.h>
//Input:
// Linked List: one->two->three->four
// head pointer points to first node "one"
//
//Output:
// Linked List: four->three->two->one
// head pointer points to first node "four"
struct node
{
//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
int data;
struct node *next;
//Pointer variable next is a self referential pointer which stores the address of structure node
};
struct node *head=NULL;
//Pointer head is used to store the starting node of the input linked list
void reverse()
{
//Function to reverse a linked list
struct node *next;
//Pointer to store the address of next node of current node
//current or cur pointer is the pointer with which we are traversing the linked list
struct node *prev=NULL;
//prev pointer stores the address of previous node of current node
struct node *cur=head;
//cur or Current pointer initially points to first node in the linked list
while(cur!=NULL)
{
next=cur->next;
//Storing the address of next node of the current node
cur->next=prev;
//Making the current node point to previous node
prev=cur;
//Making current node as previous node
cur=next;
//Making next node as current node
}
head=prev;
//Initially head points to first node in the linked list
//So we are now making the head point to last node in the linked list
}
void print()
{
//This funtion is used to print the data in each of the node in the linked list
//Process of moving from one node to another node is called as traversing
struct node *temp=head;
printf("\nList:");
while(temp!=NULL)
{
printf("\n%d ",temp->data);
temp=temp->next;
}
}
int main()
{
struct node *one = (struct node*)malloc(sizeof(struct node));
struct node *two = (struct node*)malloc(sizeof(struct node));
struct node *three = (struct node*)malloc(sizeof(struct node));
struct node *four = (struct node*)malloc(sizeof(struct node));
//Creating 4 nodes
head=one;
//head points to node one of input linked list
one->data=1;
one->next=two;
two->data=2;
two->next=three;
three->data=3;
three->next=four;
four->data=4;
four->next=NULL;
//End of linked list
//Linked List: one->two->three->four
//head pointer points to first node "one"
printf("\nBefore Reversing:");
printf("\nLinked List:");
print();
reverse();
//Calling the reverse function
printf("\nAfter Reversing:");
printf("\nLinked List:");
print();
return 0;
}
Output :
Before Reversing: Linked List: List: 1 2 3 4 After Reversing: Linked List: List: 4 3 2 1
