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