Implementation of linked list

Implementation

• The linked list is created using dynamic memory allocation. That means while creating the list we are not using arrays at all. Hence the main advantage of this kind of implementation is that we can create a list of nodes as per our needs and requirements. Hence there won't be any wastage or lack of memory. 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

void sll:: create()

{

node *temp, *New;

int val,flag;

char ans ='y';

flag=TRUE;

do

{

   cout<<"\nEnter the data :";

   cin>>val;

   // allocate memory to new node

   New = new node;

   if (New= = NULL)

      cout<<"Unable to allocate memory\n";

   New‒> data = val;

   New‒>next = NULL;

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

   {

      head= New;

      temp = head;

      flag=FALSE;

   }

   else

   {

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

   temp‒>next = New;

   temp = New;

   }

cout<<"\n Do you want to enter more elements?(y/n)";

ans = getche();

}while(ans= ='y' || ans= ='Y');

cout<<"\nThe Singly Linked List is created\n";

getch();

clrscr();

}

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 = new 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,

Then for value 40 ‒

Step 5:

is the final linked list.

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=temp node will be NULL. Therefore the message "The list is empty" will be displayed.

void sll ::display()

{

node *temp;

temp = head;

if ( temp = = NULL)

{

   cout<<"\nThe list is empty\n";

   getch(); clrscr();

   return;

}

while (temp != NULL

{

   cout<<temp‒>data<<" ";

   temp = temp‒>next;

}

getch();

}

If we have created some linked list like this then ‒

Continuing in this fashion we can display remaining nodes 40, 50. When

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 ‒

void sll:: insert head()

{

   node *New,*temp;

   New new node;

   cout<<"\n Enter The element which you want to insert";

   cin>>New‒>data;    // There is no node in the linked list. That means the linked list is empty

   if(head= NULL)

   head=New;

   else

   {

      temp=head;

      New‒>next = temp;

      head=New;

   }

}

If there is no node in the linked list then value of head is NULL. At that time if we want to insert 10 then

Otherwise suppose linked list is already created like this

Now we will insert a node at the end ‒

void sll::insert_last()

{

   node *New,*temp;

   cout<<"\nEnter The element which you want to insert";

   cin>>New‒>data;

   if(head= =NULL)

   head=New;

   else

   {

      temp=head;

      while(temp‒>next!= NULL)  //Finding the end of the linked list.Then temp will be a last bode.

      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 sll:: insert_after()

{

   int key;

   node *temp, *New;

   New = new node;

   cout<<"\n Enter The element which you want to insert";

   cin>>New‒>data;

   if(head = = NULL)

   {

      head=New;

   }

   else

   {

      cout<<"\n Enter The element after which you want to insert the node";

      cin>>key;

      temp = head;

   do

   {

      if(temp‒>data= =key)

   {

      New‒>next‒temp‒>next;

      temp‒>next=New;

      break;

   }

   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

•As we will search for the value 30, key = 30.

Then,

if(temp → data =

{

      New → next = temp → next;

      temp→ next = New;

      return

}

Thus desired node gets inserted at desired position.

4. Deletion of any element from the linked list

void sll:: dele()

{

   node *temp, *prev;

   int key:

   temp = head;

   clrscr();

   cout<<"\nEnter the data of the node you want to delete: ";

   cin>>key;

   while(temp!=NULL)

   {

      if(temp‒>data= = key)  // Firstly Node to be deleted is searched in the linked list

            break;

      prev=temp;  // Once the node to be deleted is found then get the previous node of that node in variable prev

      temp=temp‒>next;

   }

   if(temp==NULL)

      cout<<"\nNode not found";

   else

   {

      if(temp= =head) //first node  // If we want to delete the head node then set its adjacent node as a new head node and then release the memory

      head = temp‒>next;

   else

      prev‒>next =temp‒>next; //intermediate or end node

      delete temp;

      cout<<"\nThe Element is deleted\n";

}

getch();

}

• Suppose we have,

• Suppose we want to delete node 30. Then we will search the node containing 30. Mark the node to be deleted as temp. Then we will obtain previous node of temp Mark previous node as prev

• Then,

prev →next = temp→ next

• Now we will delete the temp node. Then the linked list will be

• Another case is, if we want to delete a head node then ‒

• This can be done using following statements

head = temp → next;

delete 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.

void sll::search(int key)

{

   node *temp;

   int found;

   temp = head;

   if ( temp = = NULL )

   {

      cout<<"The Linked List is empty\n";

      getch();

      clrscr();

   }

   found = FALSE;

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

   {

      if (temp‒>data != key)  // Compare data at each node with the key value. If not matching then move to the next node

      temp = temp ‒> next;

      else

      found =TRUE;   // If node containing desired data is obtained in the linked list then set found variable to TRUE

   }

   if (found = =TRUE ) 

   {

      cout<<"\nThe Element is present in the list\n";

      getch();

   }

   else

   {

      cout<<"The Element is not present in the list\n";

      getch();

   }

}

Consider that we have created a linked list as

Suppose key = 30 i.e. we want a node conaining 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 ‒

'C++' Program

/**********************************************************************

Demonstration Program to perform various operations on singly link lists.

*********************************************************************/

// List of include files

#include<iostream>

using namespace std;

#define TRUE 1

#define FALSE 0

// class defination

class sll

{

private:

struct node

{

   int data;

   structnode *next;

}*head;

public:

sll();

void create();

void display();

void search(int key);

void insert _head();

void insert_ after();

void insert_last();

void dele();

_sll();

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

sll::sll()

{

head=NULL;//initialize head to NULL

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Destructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

sll::~sll()

{

   node *temp, *temp1;

   temp = head‒>next;

   delete head;

   while(temp!= NULL) //free the memory allocated

   {

      temp1=temp‒>next;

      delete temp;

      temp = temp1;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll create()

{

   node *temp, *New;

   int val,flag;

   char ans ='y';

   flag=TRUE;

   do

   {

      cout<<"\nEnter the data:";

      cin>>val;

      // allocate memory to new node

      New = new node;

      if ( New = = NULL )

         cout<<"Unable to allocate memory\n";

      New‒> data = val;

      New‒> next =  NULL;

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

      {

         head = New;

         temp = head;

         flag = FALSE;

      }

      else

      {

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

         temp‒>next = New;

         temp = New;

   }

   cout<<"\n Do you want to enter more elements?(y/n)";

   ans = getche();

   }while(ans= ='y' || ans = = 'Y');

   cout<<"\nThe Singly Linked List is created\n";

   getch();

   clrscr();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The display function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll ::display()

{

   node *temp;

   temp = head;

   if (temp = = NULL )

   {

      cout<<"\nThe list is empty\n";

      getch(); clrscr();

      return;

   }

while (temp != NULL)

{

   cout<<temp‒>data<<" ",

   temp = temp ‒> next;

}

getch();

}

void sll::search(int key)

{

   node *temp;

   int found;

   temp = head;

   if (temp = = NULL )

   {

      cout<<"The Linked List is empty\n";

      getch();

      clrscr();

   }

   found = FALSE;

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

   {

   if (temp‒>data != key)

      temp = temp ‒> next;

   else

      found = TRUE;

   }

   if (found = =TRUE)

   {

      cout<<"\nThe Element is present in the list\n";

      getch();

   }

   else

   {

      cout<<"The Element is not present in the list\n";

      getch();

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The dele function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll:: dele()

{

   node *temp, *prev;

   int key;

   temp = head;

   clrscr();

   cout<<"\nEnter the data of the node you want to delete: ";

   cin>>key;

   while(temp!= NULL)

   {

      if(temp‒>data= =key)//traverse till required node to delete

      break;                 //is found

      prev = temp;

      temp = temp‒>next;

   }

   if(temp = =NULL)

      cout<<"\nNode not found";

   else

   {

      if(temp = = head) //first node

         head = temp‒>next;

      else

         prev‒>next=temp‒>next; //intermediate or end node

   delete temp;

cout<<"\nThe Element is deleted\n";

}

getch();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert at end

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll::insert last()

node *New*temp;

cout<<"\nEnter The element which you want to insert";

cin>>New‒>data;

if(head = NULL)

   head = New,

else

{

   temp = head;

   while(temp‒>next!=NULL)

   temp = temp‒>next;

   temp‒>next=New;

   New‒>next = NULL;

}

}

*/

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert after a node

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll:: insert_after()

{

   int key;

   node *temp, *New;

   New = new node;

   cout<<"\n Enter The element which you want to insert";

   cin>>New‒>data;

if(head = = NULL)

{

   head =New;

}

else

{

   cout<<"\n Enter The element after which you want to insert the node";

   cin>>key;

   temp = head;

   do

   {

   if(temp‒>data = = key)

   {

      New‒>next = temp‒>next;

      temp‒>next=New;

      break;

   }

   else

   temp = temp‒>next;

   }while(temp!= NULL);

}

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert at the beginning

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll:: insert_head()

{

node *New,*temp;

New = new node;

cout<<"\n Enter The element which you want to insert";

cin>>New‒>data;

if(head = = NULL)

   head=New;

else

{

   temp = head;

   New‒>next = temp;

   head=New;

}

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main function

Input: None

Output: None

Parameter Passing Method: None

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main()

{

   sll s;

   int choice,val,ch1;

   char ans = 'y';

   do

   {

      clrscr();

      cout<<"\nProgram to Perform Various operations on Linked List";

      cout<<"\n1.Create";

      cout<<"\n2.Display";

      cout<<"\n3.Search";

      cout<<"\n4.Insert an element in a list":

      cout<<"\n5.Delete an element from list";

      cout<<"\n6.Quit";

      cout<<"\nEnter Your Choice (1‒6) ";

      cin>>choice;

      switch( choice)

      {

         case 1:    s.create();

               break;

         case 2:   s.display();

               break;

         case 3:    cout<<"Enter the element you want to search";

               cin>>val;

               s.search(val);

               break;

         case 4:       clrscr();

               cout<<"\nThe list is:\n";

               s.display();

               cout<<"\nMenu";

               cout<<"\n1.Insert at beginning\n2.Insert after";

               cout<<"\n3.Insert at end";

               cout<<"\nEnter your choice";

               cin>>ch1;

            switch(chl)

            {

                  case 1:s.insert_head();

                  break;

                  case 2:s.insert_after();

                  break;

                  case 3:s.insert_last();

                  break;

                  default:cout<<"\nInvalid choice";

             }

             break;

       case 5: s.dele();

             break;

       default: cout<<"\nInvalid choice";

    }

cout<<"\nContinue?";

cin>>ans;

}while(ans = ='y'||ans = ='Y');

getch();

return;

}

Output

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search

4.Insert an element in a list

5.Delete an element from list

6.Quit

Enter Your Choice ( 1‒6) 1

Enter the data :10

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

Enter the data :20

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

Enter the data :30

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

Enter the data :40

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

Enter the data :50

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

The Singly Linked List is created

Continue?

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search

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

Review Questions

1. Give the algorithm for inserting an element and deleting an element in a linked list.

2. Give syntax to insert X in linked list.