Linked List Implementation

Linked List Implementation

• Various operations of linked list are

1. Creation of linked list.

2. Display of linked list.

3. Insertion of any element in the linked list.

4. Deletion of any element from the linked list.

5. Searching of desired element in the linked list.

We will discuss each operation one by one -

1. Creation of linked list

node* create()

{

node *temp, *New, *head;

int val, flag;

char ans='y';

node *get_node();

temp = NULL;

flag =TRUE; /* flag to indicate whether a new node is created for the first time or not */

do

{

printf("\nEnter the Element :");

scanf("%d", &val);

/* allocate new node */

New =get_node();

if (New == NULL)

printf("\nMemory is not allocated");

New-> data = val;

if (flag==TRUE) /* Executed only for the first time */

{

head = New;

temp = head; /*head is a first node in the SLL*/

flag = FALSE;

}

else

{

/* temp keeps track of the most recently

created node */

temp->next = New;

temp = New;

}

printf("\n Do you Want to enter more elements? (y/n)");

ans=getche();

} while(ans=='y');

printf("\nThe Singly Linked List is created\n");

getch();

clrscr();

return head;

}

node *get_node()

{

node *temp;

temp (node *) malloc(sizeof(node));

temp->next = NULL;

return temp;

}

Creation of linked list (logic explanation part) :

Initially one variable flag is taken whose value is initialized to TRUE (i.e. 1). The purpose of flag is for making a check on creation of first node. That means if flag is TRUE then we have to create head node or first node of linked list. Naturally after creation of first node we will reset the flag (i.e. assign FALSE to flag). Consider that we have entered the element value 10 initially then,

Step 1:

New = get_node ();

/* memory gets allocated for New node */

New data = Val;

/* value 10 will be put in data field of New */

Step 2:

If (flag == TRUE)

{

Head = New

temp head;

/* We have also called this node as temp because head's address will be preserved in 'head' and we can change 'temp' node as per requirement */

 flag=FALSE;

/* After creation of first node flag is reset */

Step 3:

If head node of linked list is created we can further create a linked list by attaching the subsequent nodes. Suppose we want to insert a node with value 20 then,

Step 4:

If user wants to enter more elements then let say for value 30 the scenario will be,

Step 5:

2. Display of linked list

We are passing the address of head node to the display routine and calling head as the 'temp' node. If the linked list is not created then naturally head NULL. Therefore the message "The list is empty" will be displayed.

void display(node *head)

{

node *temp;

temp head;

if (temp == NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return;

}

while (temp != NULL)

{

temp = printf("%d -> ", temp->data);

temp->next;

}

printf("NULL");

getch();

clrscr();

}

If we have created some linked list like this then

As now value of temp becomes NULL we will come out of while loop. As a result of such display routine we will get,

10 20 30 40 50 → NULL

will be printed on console.

3. Insertion of any element at anywhere in the linked list

There are three possible cases when we want to insert an element in the linked list -

a) Insertion of a node as a head node.

b) Insertion of a node as a last node.

c) Insertion of a node after some node.

We will see the case a) first -                        

node *insert_head(node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New->data);

if(head == NULL)

head=New;

else

Now we will insert a node at the end -

void insert_last(node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New->data);

if(head == NULL)

head=New;

else

{

temp=head;

while(temp->next!= NULL)

temp-temp->next;

temp->next=New;

New->next = NULL;

}

}

To attach a node at the end of linked list assume that we have already created a linked list like this -

Now we will insert a new node after some node at intermediate position

void insert_after(node *head)

{

int key;

node *New,*temp;

New= get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New->data);

if(head == NULL)

{

head=New;

}

else

{

printf("\n Enter The element after which you want to insert the node");

scanf("%d", &key);

temp=head;

do

if(temp->data==key)

{

New->next-temp->next;

temp->next=New;

return;

}

else

temp-temp->next;

}while(temp!= NULL);

}

}

If we want to insert 31 in the linked list which is already created. We want to insert this 31 after node containing 30 then

Thus desired node gets inserted at desired position.

4. Deletion of any element from the linked list

void dele(node **head)

{

node *temp,*prev;

int key;

temp = *head;

if (temp == NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return

}

Always check before deletion whether the linked list is empty or not. Because if the list is empty there is no point in performing deletion

clrscr();

printf("\nEnter the Element you want to delete: ");

scanf("%d", &key);

temp = search(*head,key);

if (temp != NULL)

{

prev = get_prev(*head,key);

if (prev != NULL)

{

prev -> next = temp->next;

free (temp);

}

else

{

*head = temp ->next;

free (temp);

}

printf("\nThe Element is deleted\n");

getch();

clrscr();

}

}

Suppose we have,

Suppose we want to delete node 30. Then we will search the node containing 30, using search (*head, key) routine. Mark the node to be deleted as temp. Then we will obtain previous node of temp using get_prev () function. Mark previous node as prev

This can be done using following statements

* head = temp->next;

free (temp);

5. Searching of desired element in the linked list

The search function is for searching the node containing desired value. We pass the head of the linked list to this routine so that the complete linked list can be searched from the beginning.

node *search(node *head, int key)

{

node *temp;

int found;

temp = head;

if (temp == NULL)

{

printf("The Linked List is empty\n");

getch();

clrscr();

return NULL;

}

found = FALSE;

while (temp != NULL && found == FALSE)

{

if (temp->data != key)

temp = temp ->next;

else

found = TRUE;

}

if (found == TRUE)

{

printf("\nThe Element is present in the list\n");

getch();

return temp;

}

else

{

printf("The Element is not present in the list\n");

getch();

return NULL;

}

}

Consider that we have created a linked list as

Suppose key=30 i.e. we want a node containing value 30 then compare temp → data and key value. If there is no match then we will mark next node as temp.

Hence print the message "The Element is present in the list".

Thus in search operation the entire list can be scanned in search of desired node. And still, if required node is not obtained then we have to print the message.

"The Element is not present in the list"

Let us see the complete program for it -

Ex. 1.6.1: Implementation of various operations on singly linked list (SLL). /***Program to perform various operations such as creation, insertion, deletion, search and display on singly link lists.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

typedef struct SLL

{

int data;

struct SLL *next;

}node;

node *create();

void main()

{

/* Local declarations */

int choice, val;

char ans;

node *head;

void display(node *);

node *search(node *,int);

node *insert(node *);

void dele(node **);

head=NULL;

do

{

clrscr();

printf("\nProgram to Perform Various operations on Linked List");

printf("\n1.Create");

printf("\n2.Display");

printf("\n3.Search for an item");

printf("\n4.Insert an element in a list");

printf("\n5.Delete an element from list");

printf("\n6.Quit");

printf("\nEnter Your Choice (1-6) ");

scanf("%d", &choice);

switch(choice) molenc

case 1: head = create();

break;

case 2: display(head);

break;

case 3: printf("Enter the element you want to search");

scanf("%d", &val);

search(head, val);

}

break;

case 4 head=insert(head);

break;

case 5 dele(&head);

break;

case 6 exit(0);

default:clrscr();

printf("Invalid Choice, Try again");

getch();

}

} while(choice != 6);

}

node* create()

{

node *temp, *New, *head;

int val, flag;

char ans='y';

node *get_node();

temp = NULL;

flag=TRUE; /* flag to indicate whether a new node is created for the first time or not */

do

{

printf("\nEnter the Element :");

scanf("%d", &val);

/* allocate new node */

New = get_node();

if ( New == NULL)

printf("\nMemory is not allocated");

New -> data = val;

if (flag==TRUE) /* Executed only for the first time */

{

head = New;

temp = head; /*head is a first node in the SLL*/

flag = FALSE;

}

else

{

/* temp keeps track of the most recently created node */

temp->next = New;

temp = New;

}

printf("\n Do you Want to enter more elements?(y/n)");

ans=getche();

}while(ans=='y');

printf("\nThe Singly Linked List is created\n");

getch();

clrscr();

return head;

node *get_node()

{

node *temp;

temp=(node *) malloc(sizeof(node));

temp->next = NULL;

return temp;

}

void display(node *head)

{

node *temp;

temp = head;

if (temp == NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return;

}

while (temp != NULL)

{

printf("%d -> ", temp->data);

temp = temp->next;

}

printf("NULL");

getch();

clrscr();

node *search(node *head, int key)

{

node *temp;

int found;

temp = head;

if (temp == NULL)

{

printf("The Linked List is empty\n");

getch();

clrscr();

return NULL;

}

found = FALSE;

while (temp != NULL && found == FALSE)

{

if (temp->data != key)

temp = temp->next;

else

found = TRUE;

}

if (found ==TRUE)

{

printf("\nThe Element is present in the list\n");

getch();

return temp;

}

else

{

printf("The Element is not present in the list\n");

getch();

return NULL;

}

}

/*          

The insert function

Input:Address of starting node of the list

Output:inserts an element into the list

Parameter Passing Method: call by value

Called By:main

Calls search()

*/

node *insert(node *head)

{

int choice;

node *insert_head(node *);

void insert_after(node *);

void insert_last(node *);

printf("\n 1. Insert a node as a head node");

printf("\n 2. Insert a node as a last node");

printf("\n 3. Insert a node at intermediate position in the linked list"); printf("\n Enter the your choice for insertion of node");

scanf("%d", &choice);

switch(choice)

{

case 1:head-insert_head(head);

break;

case 2:insert_last(head);

break;

case 3:insert_after(head);

New head is returned from function insert_head().

Hence we have to return the new

head from the insert function to main

break;

}

return head;

}

/* Insertion of node at first position*/

node *insert_head(node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New->data);

if(head == NULL)

head=New;

else

{

temp=head;

New->next=temp;

head=New;

}

return head;

}

/*Insertion of node at last position*/

void insert_last (node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d",&New->data);

if(head== NULL)

head=New;

else

{

temp=head;

while(temp->next!= NULL)

temp-temp->next;

temp->next=New;

New->next = NULL;

}

}

/*Insertion of node at intermediate position */

void insert_after(node *head)

{

int key;

node *New,*temp;

New= get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New->data);

if(head == NULL)

{

head=New;

}

else

{

printf("\n Enter The element after which you want to insert the node");

scanf("%d", &key);

temp=head;

do

{

if(temp->data== key)

{

New->next-temp->next;

temp->next=New;

return;

}

else

temp-temp->next;

} while(temp!= NULL);

}

}

node* get_prev(node *head, int val)

{

node *temp, *prev;

int flag;

temp = head;

if (temp==NULL)

return NULL;

flag = FALSE;

prev = NULL;

while (temp != NULL && !flag)

{

if (temp->data != val)

{

prev = temp;

temp = temp->next;

}

else

flag = TRUE;

}

if (flag )/*if flag is true*/

return prev;

else

return NULL;

/*The dele function

Input:Address of the starting node of the list

Output:deletes the desired element from the list

Parameter Passing Method: call by value

Calls search(), get_prev()

*/

void dele(node **head)

{

node *temp, *prev;

int key;

temp = *head;

if (temp == NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return;

}

clrscr();

printf("\nEnter the Element you want to delete: ");

scanf("%d", &key);

temp = search(*head,key);

if (temp != NULL)

{

prev = get_prev(*head,key);

if (prev != NULL)

{

prev -> next = temp->next;

free (temp);

}

else

{

*head = temp->next;

free(temp);

}

printf("\nThe Element is deleted\n");

getch();

clrscr();

}

}

Output

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 1

Enter the Element :10

Do you Want to enter more elements? (y/n)y Enter the Element :20

Do you Want to enter more elements?(y/n)y Enter the Element :30

Do you Want to enter more elements?(y/n)y Enter the Element :40

Do you Want to enter more elements?(y/n)y Enter the Element :50

Do you Want to enter more elements?(y/n)n

The Singly Linked List is created

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

10 - 20 -> 30 -> 40 -> 50 -> NULL

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 3

Enter the element you want to search 40

The Element is present in the list

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 4

1. Insert a node as a head node

2. Insert a node as a last node

3. Insert a node at intermediate position in the linked list

Enter the your choice for insertion of node 1

Enter The element which you want to insert 9

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

9-> 10-> 20 -> 30-> 40 -> 50 -> NULL

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

 6. Quit

Enter Your Choice (1-6) 4

1. Insert a node as a head node

2. Insert a node as a last node

3. Insert a node at intermediate position in the linked list

Enter the your choice for insertion of node 2

Enter The element which you want to insert 60

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

9 - 10 - 20 -> 30-> 40 -> 50 -> 60 -> NULL

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item all beds n nouiaog

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 4

1. Insert a node as a head node

2. Insert a node as a last node

3. Insert a node at intermediate position in the linked list

Enter the your choice for insertion of node 3

Enter The element which you want to insert 31

Enter The element after which you want to insert the node 30

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

9 - 10 -> 20 -> 30 -> 31 -> 40 -> 50 -> 60-> NULL

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 5

Enter the Element you want to delete: 40

obor Jasis-as

The Element is present in the list

The Element is deleted

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

9->

10-> 20 -> 30 -> 31 -> 50 -> 60-> NULL

More Programs on Linked List

In this section we will discuss various operations that can be performed on the linked list. For the sake of convenience we will discuss only functions performing these operations assuming that the list is already created. The create() and display() functions will be common to all these operations.

Ex. 1.6.2 Counting the nodes of linked list.

Sol;

void count()

{

node *temp;

int c=0;

temp=head;

if(temp== NULL)

{

printf("\n The list is empty");

return;

}

while(temp!= NULL)/*visiting each node*/

{

c=c+1;/*c is for counting the node*/

temp-temp->next;

}

printf("\nThe Total number of nodes are: %d",c);

getch();

}

Ex. 1.6.3 Concatenation of two linked list.

Sol. :

void concat(node *head1,node *head2)

{

node *temp1,*temp2;

temp1=head1;

temp2=head2;

while(temp1->next!= NULL)

temp1=temp1->next;/*searching end of first list*/

temp1->next=temp2;/* attaching head of the second list*/

printf("\n The concatenated list is ...\n");

temp1=head1;

while(temp1!= NULL)

{ /*printing the concatenated list*/

}

printf("%d",temp1->Data);

temp1=temp1->next;

}

}

Ex. 1.6.4 Algorithm to copy one singly list to another.

Sol.:

void copy(node *head1,node *head2)

{

node *temp1, *temp2;

temp1=head1;/*first non empty linked list*/

head2=(node *)malloc(sizeof(node));

temp2-head2;/* second empty linked list*/

while(temp1!= NULL)/*while not end of first linked list*/

{

temp2->data=temp1->data;/*copy the content to other node*/

temp2->next=(node *)malloc(sizeof(node));

temp2=temp2->next;/* moving one node ahead */

temp1=temp1->next;

}

temp2=NULL;/*set the next pointer of last node of second list to NULL*/

printf("\n The list is copied \n");

while(head2->next!= NULL)

{

/*printing the second list i.e. copied list*/

printf("%d",head2->data); head2-head2->next;

}

}

Ex. 1.6.5 Recursive routine to erase a linked list (delete all node from the linked list).

Sol. :

struct node *list_free(struct node *temp)

{

if(temp->next!= NULL)

{

temp1=temp->next;/*temp1 is declared globally*/

temp->next=NULL;

free(temp);

list_free(temp1);/*recursive call*/

}

temp=NULL;

return temp;

}

Ex. 1.6.6 Write a routine to merge two sorted linked lists.

Sol.

Consider two linked lists

node *merge(node *temp1,node *temp2)

{

node *prev_node1, *next_node2, *head;

if(temp1== NULL)

{

temp1=temp2;

head=temp2;

}

if(temp1->data<temp2->data)

head=temp1;

else

head=temp2;

while(temp1!= NULL && temp2!= NULL)

{

/*while data of 1st list is smaller then traverse*/

while((temp1->data<temp2->data) && (temp1!= NULL))

{

prev_node1=temp1; /* store prev node of Sl11 */

temp1=temp1->next;

}

if(temp1== NULL)

break;

/*when temp1's data>temp1 it will come out

of while loop so adjust links with temp1's prev node*/

prev_node1->next=temp2;

next_node2=temp2->next; /*store next node of Sl12*/

temp2->next=temp1;

temp1=temp2;

temp2=next_node2;

}

if(temp1==NULL&&temp2!=NULL) /*attach rem nodes of S112*/

{

while(temp2!= NULL)

 

{

prev_node1->next=temp2;

prev_node1=temp2;

temp2=temp2->next;

}

}

return head;

}

Ex. 1.6.7 Returning the position of an element X in a list L.

Sol.

The routine is as given below -

Return_position(node *head,int key)

{

/* head represents the starting node of the List*/

/* key represents the element X in the list*/

int count=0;

node *temp;

temp=head;

while(temp->data!=key)&&(temp!= NULL)

{

temp-temp->next;

count=count+1;

}

if(temp->data==key)

return count;

else if(temp== NULL)

return -1; /* -1 indicates that the element X is not present in the list*/

Ex. 1.6.8 Write a C function to display the sum of all the elements in a singly linked list.

Sol. :

void sum(node *head)

{

node *temp;

int s=0;

temp=head;

while(temp!= NULL)

{

s=s+temp->data;

temp-temp->next;

}

printf("%d",s);

}

Ex. 1.6.9 Assume a singly linked list where each node contains student details like name, rollno and percentage of marks. Write a "C" function COUNTO to traverse the linked list and count how many students have obtained more than 60 %.

Sol. The data structure can be

struct student

{

char *name;

};

int roll;

float marks;

struct student *next;

};

The COUNT function can be written as

void COUNT(struct student *temp)

{

int count=0;

while(temp!= NULL)

{

if(temp->marks>60)

count++;

temp-temp->next;

}

printf("\n\n %d students have obtained more than 60 Percentage", count);

}

Ex. 1.6.10: Write a C program to create a singly linked list and split it at the middle. And make the second half as the first and vice versa, display the final list.

Sol. :

typedef struct node

{

int data;

struct node *next;

}node;

void main().

{

node*head=NULL,*p,*q;

int n,i,x;

printf("\nEnter number of nodes:");

scanf("%d", &n);

for(i=0;i<n;i++)

{

printf("\nEnter element:");

scanf("%d",&x);

p=(node*)malloc(size of(node));

p->data=x;

p-next=NULL;

if(head= NULL)

head=q=p;

else

{

q->next=p;

q=p;

}

}

p=q=head;

while(q->next!= NULL)

{

p=p->next;

q=q->next;

if(q->next!= NULL)

q=q->next;

}

q-next-head;

head-p->next;

p->next=NULL;

for(p=head;p!= NULL;p=p->next)

printf("\n%d",p->data);

}

Ex. 1.6.11: Write a function that removes all duplicate elements from a linear singly linked list.

Sol. :

void dupdelete(node*head)

{

node *p, *q,*I;

p=head;

q=p->next;

while(q!= NULL)

{

if(p->data!=q->data)

{

p-p->next;

q-q->next;

}

else

if(p->data==q->data)

{

p->next=q->next;

r=q;

q=q->next;

free(r);

}

return(head);

}                                                            

}

Ex. 1.6.12: Suppose a linked list consists of numerical values. Write a function for finding the maximum element of the list and the product of all the numbers in the list.

Sol. i) To find the maximum element in the linked list :

void maxElement(node *root)

{

node *temp;

int Maxval;

temp=root;

Maxval=temp->data;

while(temp!= NULL)

{

if(temp->data>Maxval)

{

Maxval-temp->data;

}

temp-temp->next;

}

printf("\n Maximum Value is: %d", Maxval);

}

ii) To find the product of all numbers in the linked list :

void Product(node *root)

{

node *temp;

int p=1;

temp=root;

while(temp!= NULL)

{

p=p*temp->data;

temp-temp->next;

}

printf("\n Product of all the elements: %d",p);

}

Review Questions

1. Write C code for singly liked list with insert, delete, display operations using structure pointer.

 2. What are the ways to insert a note in linked list? Write an algorithm for inserting a node before a given node in a linked list.

3. Explain the insertion operation linked list. How nodes are inserted after a specified node ?