Sunday, 1 November 2015

Operation on a single linked list in C

A linked list is a linear and dynamic data structure. There are so many operations the one can perform after creation of linked list. For example, one can insert or delete nodes from the list. Here are some basic operations that be performed on linked list data strictures.



The operations possible on single linked list are listed below.
  • Traversing the list 
  • Inserting a node into the list
  • Deleting a node from the list
  • copying the list to make duplicate of it
  • Merging the linked list with another one to make large list
  • searching for an element in the list. 

Traversing the list 

                      The process of visiting each node is called Traversing the list. In single linked list we can travel only in one direction. Were as in double linked list we can travel in both directions.

 Inserting a node into the list

                              One can insert one at three positions of a single linked list. By manipulating it's pointers properly one can achieve this. Here are three positions where we can insert elements in single linked list.

  1. Inserting at the beginning of the list
  2. Inserting at the end of the list
  3. Inserting in middle of the list

1.Inserting at the beginning of the list

                The following procedure tells you how to insert element at the beginning of the list in single linked list. For Example, If the initial list is


 It contains five node and we are going to be inserting at the beginning i.e., before node 21.

  • Then set pointer " p" to the node 21.
  • Allocate memory for new node.
  • Set pointer " temp" to new node
  • Using temp pointer insert data into new node (say 999)
  • Using temp set link part of new node with the address of first
  • Then set pointer "p" to point to new node.

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

2.Inserting at the end of the list

                                           We all of you know the last node of linked list is null. Initially the pointer "temp" is pointing to first node. Then follow the following steps.

  1. Move the pointer "temp" to last node of the list.
  2. Allocate the memory for new node and set pointer "r" the new node.
  3. Using pointer "r" insert data into new node.
  4. Using pointer" r" set the address field of new node to NULL
  5. Using pointers "temp" and "r" set the address of new node the existing node.

3.Inserting in middle of the list

                             Like above we can add the node in the list at any position. For example, in the above list, If I want to insert new node after node three, follow the following process


  1. Move the pointer "temp" to last node of the list.
  2. Allocate the memory for new node and set pointer "r" the new node.
  3. Using pointer "r" insert data into new node.
  4.  Using pointer "r" set the link part of the new node with the address part of the fourth node
  5.  Using pointer "temp" set the link part of the third node with address part of the new node.
Similar way you can perform all the remaining operations. 

0 comments:

Post a Comment

Advertisement

Find Us On Facebook

C Programming

More

C++ Tutorial

More

Java Tutorial

More

Computer Basics

More

MS Office

More

Database Management

More
Top