Author Archives: Raghavendar T S

Stack Implementation using Linked List – C Program

Stack Implementation using Linked List - C Program

Stack Implementation using Linked List – C Program

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Stack Implementation using Linked List – C Program :

Source Code :

#include<stdio.h>
struct node *top=NULL;
//Declared as global variable since it is accessed by multiple functions
//Pointer that points the top node of the stack

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
};

void push(int data)
{
    	//This function will push a new node to the stack

    	struct node *temp = (struct node*)malloc(sizeof(struct node));
    	//malloc is used to allocate the memory dynamically
    	//Pointer variable temp is stored in heap
    	//A memory block(size of structre node) is created and a pointer variable temp is made to point to that memory location

    	temp->data=data;
    	//Store the integer data obtained from the function insert to the member variable data of newly created node 

    	temp->next=top;
    	//Make newly created node point to address location where top is pointing to

    	top=temp;
    	//Make top pointer point to newly created node
}

void pop()
{
    	//Function to delete the top node
    	if(top!=NULL)
    	{
    		//Executes if the stack has atleast one node
    		struct node *temp=top;

    		top=top->next;
    		//Making the top pointer point to next node

    		free(temp);
    		//Releasing the memory of top node
    	}
    	else
    	{
        		printf("\nStack is empty");
    	}
}

void print()
{
    	//This funtion is used to print data present in the stack 

    	struct node *temp=top;
 	   printf("\nList:");
    	while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;				
    	}
}

int main()
{
    	printf("\nPushing data 1 into stack");
    	push(1);
    	print();
    	//Insert the data 1 to the stack

    	printf("\nPushing data 2 into stack");
    	push(2);
    	print();
    	//Insert the data 2 to the stack

    	printf("\nPushing data 3 into stack");
    	push(3);
    	print();
    	//Insert the data 3 to the stack

    	printf("\nPopping data from stack");
    	pop();
    	print();
    	//Delete the top element from the stack

    	printf("\nPopping data from stack");
    	pop();
    	print();
    	//Delete the top element from the stack

    	printf("\nPopping data from stack");
    	pop();
    	print();
    	//Delete the top element from the stack

    	printf("\nPopping data from stack");
    	pop();
    	//Delete the top element from the stack
    	//But there is nothing to delete now.Stack is empty

    	return 0;
}

Output :

Pushing data 1 into stack
List:
1

Pushing data 2 into stack
List:
2
1

Pushing data 3 into stack
List:
3
2
1

Popping data from stack
List:
2
1

Popping data from stack
List:
1

Popping data from stack
List:

Popping data from stack
Stack is empty

Linked List in C- Print Linked List in Reverse Order using Recursion

Linked List in C- Print Linked List in Reverse Order using Recursion

Linked List in C- Print Linked List in Reverse Order using Recursion

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Print Linked List in Reverse Order using Recursion :

Source Code :

#include<stdio.h>
struct node *head=NULL;
//Pointer to store the staring node of the linked list
//Always stores the address location of first node
//Declared as global variable since it is accessed by multiple functions

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;
};

void  print_reverse(struct node* p)
{
    	//Recursive function
    	//Function to print the linked list in reverse. i.e. from the last node
    	//Note that we are not reversing the linked list. We are just printing the list in reverse
	    if(p==NULL)
    	{
        		//Exit condition - It is most important thing to consider.Else the recursive function will be called infinitely
        		//The condition will be true for last node i.e the node with next pointer NULL
        		return;
    	}
    	print_reverse(p->next);
    	//Recursive funtion is called by passing address of next node
    	//p is current node and p->next is next node of node p

    	printf("\n%d ",p->data);
    	//Print the data from the node p
    	//This statement will be executed for the first time only when print_reverse(address of last node) of last node is called
    	//This statement will be executed for the first time only after the above if condition becomes true
}

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));
    	//Memory is allocated dynamically in heap and pointer "one" points to that allocated address
    	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));

    	head=one;
    	//The head points to node "one"

    	one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=NULL;
    	//The last node points to NULL which means it is the end of linked list

    	//node one->node two->node three->four

    	printf("\nOriginal Linked List:");
    	print();
    	//Printing the linked list from first node to last node

    	printf("\nPrinting the linked list in reverse order:");
    	print_reverse(head);	
 	   //Printing the linked list from last node to first node

    	return 0;
}

Output :

Original Linked List:
List:
1
2
3
4

Printing the linked list in reverse order:
4
3
2
1

Linked List in C- Split a Linked List into 2 Linked List

Linked List in C- Split a Linked List into 2 Linked List

Linked List in C- Split a Linked List into 2 Linked List

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C- Split a Linked List into 2 Linked List :

Input:
        Head Pointer: head1
        Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7

Output:
        Head Pointer: head1
        Linked List 1: node 1->node 3->node 5->node 7

        Head Pointer: head2
        Linked List 2: node 2->node 4->node 6

Source Code :

#include<stdio.h>
///////////////////////////////////////////////////////////////////////////////////////////
//Input:
//        Head Pointer: head1
//        Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7
//
//Output:
//        Head Pointer: head1
//        Linked List 1: node 1->node 3->node 5->node 7
//
//        Head Pointer: head2
//        Linked List 2: node 2->node 4->node 6
///////////////////////////////////////////////////////////////////////////////////////////

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 *head1 = NULL;
struct node *head2=NULL;
void split()
{
	    int i=0;

	    struct node *temp=head1;
    	head2=temp->next;
    	//one->two->three->four->five->six->seven
    	//Making the pointer head1 point to node "one"
    	//Making the pointer head2 point to node "two"

    	struct node *holder1=head1;
    	struct node *holder2=head2;
    	//Temporary pointer to store address of previous node

    	while(temp!=NULL)
    	{
        		i++;
        		if(i%2==1 && i!=1)
        		{			
            			//Not executed for i=1
            			holder1->next=temp;
            			holder1=holder1->next;
        		}
        		if(i%2==0 && i!=2)		
        		{
            			//Not executed for i=2
            			holder2->next=temp;
            			holder2=holder2->next;
        		}
        		temp=temp->next;
	    }
    	holder1->next=NULL;
    	holder2->next=NULL;
	    //Making the last nodes of two linked list with head pointer "head1" and "head2" point to NULL
}

void print(struct node *temp)
{
    	//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
    	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));
    	struct node *five = (struct node*)malloc(sizeof(struct node));
    	struct node *six = (struct node*)malloc(sizeof(struct node));
    	struct node *seven = (struct node*)malloc(sizeof(struct node));
    	//Seven nodes are created

    	head1=one;
    	//head1 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=five;

    	five->data=5;
    	five->next=six;

    	six->data=6;
    	six->next=seven;

    	seven->data=7;
    	seven->next=NULL;
    	//Last node of input linked list

    	//one->two->three->four->five->six->seven

    	printf("\nLinked List:Before Splitting");
    	print(head1);
    	//Before split function is executed , Linked list with head pointer "head1" has 7 nodes

    	split();
    	//Function to split a linked list into two linked list

    	printf("\nLinked List:After Splitting");
    	printf("\nOutput:Linked List 1");
    	print(head1);
    	//After split function is executed , Linked list with head pointer "head1" has nodes with odd index

    	printf("\nOutput:Linked List 2");
    	print(head2);
    	//After split function is executed , Linked list with head pointer "head2" has nodes with even index

    	return 0;
}

Output :

Linked List:Before Splitting
//Input Linked List
//Head Pointer is head1
1
2
3
4
5
6
7

Linked List:After Splitting
Output:Linked List 1
//Head Pointer is head1
1
3
5
7

Output:Linked List 2
//Head Pointer is head2
2
4
6

Linked List in C – Split a Linked List into 2 Separate Linked List

Linked List in C - Split a Linked List into 2 Separate Linked List

Linked List in C – Split a Linked List into 2 Separate Linked List

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Split a Linked List into 2 Separate Linked List :

Input:
        Head Pointer: head
        Original linked list: node 1->node 2->node 3->node 4->node 5->node 6->node 7

Output:
        Head Pointer: head_of_list_1
        Linked List 1: node 1->node 3->node 5->node 7

        Head Pointer: head_of_list_2
        Linked List 2: node 2->node 4->node 6

Source Code :

#include<stdio.h>
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

struct node *head_of_list_1 = NULL;
struct node *head_of_list_2 = NULL;
//Pointer head_of_list_1 and head_of_list_2 i used to store the starting node of the two output linked list
//Declared as global variable since it is accessed by multiple functions

void split_the_linked_list()
{
    	//Function to split a linked list into two seperate linked list
    	//If the original list is 1->2->3->4->5->6, then the the first linked list will contain nodes 1->3->5(outputlinked list 1)
    	//													 the seconf linked list will contain nodes 2->4->6(outputlinked list 2)

    	struct node *temp = head;	
    	//Use a new pointer variable temp
    	//Do not use the pointer variable head directly. If we use it, the address location of the first node in the linked list will be lost

    	struct node *listholder1 = NULL;
    	struct node *listholder2 = NULL;
    	//listholder1 and listholder2 are temporary pointer variables to store the address of last node of two output linked  list

    	struct node *ptr;	
    	int i=1;
    	while(temp!=NULL)
    	{
        		//Loop to traverse the original linked list
        		if(i%2==1)
        		{
            			//Executed for nodes with odd index of nodes i.e. for nodes 1,3,5 etc of the original input linked list
            			ptr = (struct node*)malloc(sizeof(struct node));
            			//A new node is created

            			ptr->data=temp->data;
           			 ptr->next=NULL;	
            			//The newly created node is assigned the data from the node of original list

            			if(head_of_list_1==NULL)
            			{						
               				//Executed only once when the the pointer head_of_list_1 is empty
				head_of_list_1=ptr;			
            			}
            			else
            			{			
                				listholder1->next=ptr;
                				//listholer1 is used to identify the last node of output linked list 1
                				//Once a new node is created we need to make listholder1 point to newly created node
            			}
            			listholder1=ptr;
            			//Making the newly created node as last node
        		}
        		else
        		{
            			//Executed for nodes with even index of nodes i.e. for nodes 2,4,6 etc of the original input linked list
            			//Other statements are same as above except that we use head_of_list_2 and listholder2 to maintain output linked list 2
            			ptr = (struct node*)malloc(sizeof(struct node));	
            			ptr->data=temp->data;
            			ptr->next=NULL;			
            			if(head_of_list_2==NULL)
            			{						
                				head_of_list_2=ptr;
            			}	
            			else
            			{
                				listholder2->next=ptr;
            			}
            			listholder2=ptr;
        		}
        		temp=temp->next;
        		i++;
    	}	
}

void print(struct node *temp)
{
    	//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
    	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));
    	struct node *five = (struct node*)malloc(sizeof(struct node));
    	struct node *six = (struct node*)malloc(sizeof(struct node));
    	struct node *seven = (struct node*)malloc(sizeof(struct node));
    	//Seven nodes are created

    	head=one;
    	//head pointsto 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=five;

    	five->data=5;
    	five->next=six;

    	six->data=6;
    	six->next=seven;

    	seven->data=7;
    	seven->next=NULL;
    	//Last node of input linked list

    	//one->two->three->four->five->six->seven

    	split_the_linked_list();
    	//Function to split the input linked list into two output linked list

    	printf("\nOriginal Linked List/Input Linked List");
        	print(head);
    	//Printnig original linked list/input linked list

    	printf("\nOutput:Linked List 1");
    	print(head_of_list_1);
    	//Printnig output linked list 1

    	printf("\nOutput:Linked List 2");
	    print(head_of_list_2);
    	//Printnig output linked list 2

    	return 0;
}

Output :

Original Linked List/Input Linked List
1
2
3
4
5
6
7

Output:Linked List 1
1
3
5
7

Output:Linked List 2
2
4
6

Linked List in C – Merge two Linked List into separate single Linked List

Linked List in C - Merge two Linked List into separate single Linked List

Linked List in C – Merge two Linked List into separate single Linked List

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Merge two Linked List into separate single Linked List :

Input
Linked List 1: one->three->five->seven
Head of Linked List 1 is head1

Linked List 2: two->four->six
Head of Linked List 2 is head2

Output
Linked List 3: one->two->three->four->five->six->seven

Head of Linked List 3 is head1

This program works irrespective of size of the two input linked list.

Source Code :

#include<stdio.h>

	//Input
	//Linked List 1: one->three->five->seven
	//Head of Linked List 1 is head1 
	//
	//Linked List 2: two->four->six
	//Head of Linked List 2 is head2
	//
	//Output
	//Linked List 3: one->two->three->four->five->six->seven
	//Head of Linked List 3 is head1

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 *head1 = NULL;
struct node *head2 = NULL;
//Pointer head1 and head2 are the pointers which stores the address of two input linked list

void merge()
{
    	//Function to merge the two input linked list
    	struct node *temp1 = head1;
    	struct node *temp2 = head2;
    	//Use a new pointer variable temp1 and temp2
    	//Do not use the pointer variable head1 and head2 directly. If we use it, the address location of the first node in the two linked list will be lost

    	struct node *holder1 = NULL;
    	struct node *holder2 = NULL;
    	//Temporary pointer variables to store the address of next node of the two input linked list

    	while(temp1!=NULL && temp2!=NULL)	
    	{
        		//Executes until both temp1 and temp2 are not NULL

        		holder1=temp1->next;
        		//Storing the address of next node of first linked list

        		temp1->next=temp2;
        		//Making the first node of first linked list point to first node of second linked list

	        	if(holder1!=NULL)			
        		{
            			//Making the first node of second linked list point to second node of first linked list
            			holder2=temp2->next;
            			temp2->next=holder1;
        		}							
        		temp1=holder1;
        		temp2=holder2;	
        		//Updating the address location of two pointer variables temp1 and temp2
    	}
}

void print(struct node *temp)
{
    	//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
    	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));
    	struct node *five = (struct node*)malloc(sizeof(struct node));
    	struct node *six = (struct node*)malloc(sizeof(struct node));
    	struct node *seven = (struct node*)malloc(sizeof(struct node));
    	//Seven nodes are created

    	head1=one;
    	head2=two;
    	//head1 points to first node of first linked list
    	//head2 points to first node of second linked list

    	one->data=1;
    	one->next=three;

    	two->data=2;	
    	two->next=four;

    	three->data=3;
    	three->next=five;

    	four->data=4;
    	four->next=six;

    	five->data=5;
    	five->next=seven;

    	six->data=6;
    	six->next=NULL;
    	//Last node of second input linked list

    	seven->data=7;
    	seven->next=NULL;
    	//Last node of first input linked list

    	//Input
    	//Linked List 1: one->three->five->seven
    	//Head of Linked List 1 is head1 
    	//
    	//Linked List 2: two->four->six
    	//Head of Linked List 2 is head2
    	//
    	//Output
    	//Linked List 3: one->two->three->four->five->six->seven
    	//Head of Linked List 3 is head1

    	printf("\nBefore Merging");
    	printf("\nInput: Linked List 1");
    	print(head1);

    	printf("\nInput: Linked List 2");
    	print(head2);

    	merge();
    	//Merging the two linked list into single linked list

    	printf("\nAfter Merging");
    	printf("\nOutput: Linked List 3");
    	print(head1);

    	return 0;
}

Output :

Before Merging
Input: Linked List 1
// Head pointer of first linked list is head1
1
3
5
7

Input: Linked List 2
// Head pointer of second linked list is head2
2
4
6

After Merging
Output: Linked List 3
// Head pointer of output linked list is head1
1
2
3
4
5
6
7