Other Linked List Operations

Other Linked List Operations

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

 

Example : 1

Write a C++ code for counting number of nodes in a singly linked list.

Solution :

void sll::count()

{

node *temp;

int c=0;

temp = head;

if(temp = = NULL)

{

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

      return;

}

while(templ=NULL)/*visiting each node*/

{

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

      temp = temp‒>next;

}

cout<<"\nThe Total number of nodes are: "<<c;

getch();

}

 

Example : 2

Write a C++ code for reversing the linked list (This is done using three pointers).

Solution :

void sll::reverse ()

{

node *temp1, *temp2, *temp3;

temp1= head;

if(temp1= =NULL)

{

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

      getch();

}

else

{

      temp2=NULL;

      while(temp1!= NULL)

      {

            temp3=temp2;

            temp2=temp1;

            temp1=temp1‒>next;

            temp2‒>next=temp3;

      }

head=temp2;

}

cout<<"\n The List is REVERSED";

}

 

For example

Consider a linked list ‒

Step 1:

As given in above algorithm initially

temp1 = head

temp2 = temp3 = NULL;

Step 2:

temp3 = NULL

//As in above code

//temp2=temp1;

//temp1=templ→ next;

……….list continued

Step 3:

For the statements

temp3=temp2;

temp2=temp1;

temp1=temp1‒>next;

we get the marking of nodes as ‒

Step 4:

As

temp2‒>next=temp3

Step 5:

temp3= temp2;

temp2= temp1;

temp1= temp1‒>next;

temp2‒>next = temp3;

will give us ‒

Step 6 :

Continuing the steps

temp3=temp2;

temp2=temp1;

temp1=temp1‒>next;

temp2‒>next=temp3;

We get ‒

Step 7 :

Finally set temp2 as head node. Hence the list becomes

Thus the linked list gets reverse using three pointers

 

Example : 3

Write a C++ code for concatenation of two linked list.

Solution :                                             

void sll: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*/

cout<<"\n The concatenated list is ...\n";

temp1=head1;

while(temp1!= NULL)

{/*printing the concatenated list*/

      cout<<" "<<temp1‒>Data;

      temp1=templ‒>next;

}

}

 

Example  : 4

Write a C++ code to copy one singly list to another.

Solution :

void sll::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(temp11=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*/

cout<<"\n The list is copied \n";

while(head2‒>next!= NULL)

{

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

      cout<<" "<<head2‒>data;

      head2 = head2‒>next;

}

}

 

Example : 5

Write a C++ code to recursive routine to erase a linked list (delete all node from the linked list).

Solution :

node sll::*list_free(struct node *temp)

{

if(temp‒>next!= NULL)

{

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

      temp‒>next=NULL;

      delete temp;

      list_free(temp1);/*recursive call*/

}

temp=NULL;

return temp;

}

 

Example : 6

Write a program in C++ to return the position of an element X in a list L.

Solution:

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*/

}

 

Example : 7

Write an algorithm to perform each of the following operations

i) Reverse a list so that the last element comes first and so on.

ii) Return the sum of integers in a list.

iii) Delete every third element from a list.

Solution:

i) Refer example 2.

ii)

void sum(node *head)

{

node *temp;

int sum=0;

temp = head;

while(temp!= NULL)

{

      sum = sum+temp‒>data;

      temp = temp‒>next;

}

cout<<"\n Sum of all the integers in a list is: "<<sum;

}

iii)

void Delete _Third_ Node(node *head)

{

node *temp;

node *key;

int n=0;

while(temp!=NULL)

{

      temp = temp‒>next;

      n++://denotes total number of nodes

}

int count=1;

temp=head;

while(count<=n)

{

      key=temp‒>next‒>next;

      temp‒>next‒>next=key‒>next;

      temp=key‒>next;

      key‒>next=NULL;

      delete key;

      count=count +3;

}

}

 

Example : 8

Write a C++ code to sum up all odd numbers in a single linked list

Solution:

The C++ code will be as follows ‒

void OddSum(node * head)

{

      node *temp;

      int sum;

      temp = head;

      sum=0;

      while(temp!= NULL)

      {

            if((temp‒>data)%2= =0)

                temp=temp‒>next;

            else

                sum=sum+temp‒>data;  // odd number in 'temp' node

      }

cout<<"\n Sum of odd numbers: "<<sum;

}