Creation,Insertion ,Deletion algorithms of a Linked List

 

Algorithm  of creation of a Linked List

CREATE---In this algorithm a Linked List of nodes is created. The list is pointed by pointer first, the last node of the list points to NULL., indicating the end of the list.

 

Each node is having two parts DATA and NEXT. Let us assume that a linked list of N number of nodes is to be created. The operator new will be used for the dynamic allocation of node. A variable I is being used as a counter to count the number of nodes in the created list.

STEPS:

                1.first=new node;{create the 1st  node of the list pointed by  first};

                2.Read(Data(first));

                3.NEXT(First)=NULL;

                4.Far a First;   [point Far to the First]

                5. For I=1 to N-1 repeat steps 6 to 10

                6.X=new node;

                7.Read(Data(X))

                8.NEXT(X)=NULL;

                9.NEXT(Far)=X;   {connect the nodes}

                10.Far=X;[shift the pointer to the last node of the list]

                                [end of For Loop]

                11.END

TRAVERSING A LINKED LIST

Many a times, it is required to traverse whole of a linked list. For Example counting of nodes in a list, printing data of all the nodes etc.

TRAVEL: In this algorithm a linked list, pointed by first, is traversed. The  number of nodes in the list is also counted during the traverse. A pointer ptr is being used to visit the various nodes in the list. A variable count is used to keep track of the number of nodes visited during the traverse. The traverse stops when a NULL is encountered.

STEPS:

                1.If First=NULL then {print “List empty” STOP};

                2.count=0;

                3.ptr=First;  {point ptr to the 1st node}

                4.While ptr<> NULL repeat Steps 5 to 6

                5.count=count+1;

                6.ptr=NEXT(ptr)  [shift ptr to the next node]

                7.print (‘Number of nodes=’, count)

                8.END

In the above algorithm , step 6 is worth noting i.e ptr=NEXT(ptr). This step means that the pointer Ptr should be shifted to the node which is being pointed by NEXT(ptr);

SEARCHING A LINKED LIST

Search is an operation in  which  an item is searched in a linked list. This operation is similar  to traveling the list. An algorithm for search operation is given below:

SEARCH:

In this algorithm a linked list, pointed by first, is traversed. While traversing the data part of each vivited node is compared with an item ‘x’. If the item is found then the search stops otherwise the process continues til the end of the list(i.e NULL) is encountered. A pointer ptr is being used to visit the various nodes in the list.

STEPS:

                1.If first=NULL then{

                                Print “List empty”;  STOP;}

                2.ptr=First;      [point ptr to the 1st node]

                3.while (ptr<>NULL) repeat steps 4 to 5

                4.If (DATA (ptr)= ‘X’)

                                Then {print “item found”;

                                STOP

                                }

                5.ptr=NEXT (ptr);  [shift ptr to the next node]

                                                [end of while]

                6.Print “item not found”;

                7.END

It may be noted in the above algorithm that if the item ‘X’ is found then the search stops.

INSERTION.......

In this algorithm a node X is inserted at the beginning of a linked list. The Linked List is being pointed by a pointer First at the beginning.

STEPS:

                1.X=new node;

                2.Read(DATA(X);

                3.If (FIRST=NULL) then

                     {

                                First=X;

                                NEXT(X)=NULL;

                    }

                 Else

                   {

                                NEXT(X)=First;

                                First=X;

                   }

                4.END

INSERT AFTER A NODE

Let List be a pointer to a linked list. In this algorithm a node X is inserted in the list after a node with data part equal to ‘VAL’. A  pointer ptr travels the list in such a way that each visited node is checked for data part equal to ‘VAL’. If such a node is found then node X is inserted after the same.

STEPS:

   1.       Ptr=List;

   2.       While (ptr<>NULL) repeat steps 3 to 4

   3.       If (DATA(ptr)=’VAL’) then

{

   X=new node

   Read (DATA(X);

  NEXT(X)=NEXT(ptr)

  NEXT(ptr)=X;

  BREAK;}

                4.ptr=NEXT(ptr)

                                [end of while]

                5.END.

It may be noted in the above algorithm that in step 3 a function exit() has been used. The purpose of this function is to leave the while loop.

INSERT BEFORE A NODE

Let LIST be a pointer to a linked list. In this algorithm a node X is inserted in the list before a node with data part equal to ‘VAL’ Two pointers ptr and back travel the list in such a way that each visited node is checked for data part equal to ‘VAL’. If such a node is found then ptr  points to the selected node and back point to immediate previous node in the list. The node X is inserted before the selected node.

STEPS:

                1.ptr=LIST

                                [check if the first node is the desired one]

                2.If(data(ptr)=’VAL’) then

                   {

                                X=new node;

                                Read DATA(X);

                                NEXT(X)=LIST;

LIST=X;

                                STOP;

                     }

3.While(ptr<>NULL ) repeat step 4 to 6

4.back=ptr;

5.ptr=NEXT(ptr);

6.If(DATA(ptr)=’VAL’)then

   {

                X=new node;

                Read DATA(X);

                NEXT(X)=ptr;

NEXT(back)=X;

                EXIT;

   }

[end of while loop]

7.END

DELETING A NODE FROM A LINKED LIST

A delete operation involves the following two steps:

                a)search the list for the node which is to be deleted.

                b)delete the node.

A algorithm for the deletion of a node from a linked list is given below:

DELETE:

Let List be a pointer to a linked list. In this algorithm a node with data value equal to ‘VAL’. Deleted from the list. Two pointers ptr and back travel the list in such a way that each visited node is checked for data equal to ‘VAL’. If such a node is found then ptr points to the selected node and back points to immediate previous node in the list. The selected node is deleted from the list.

STEPS:[CHECK IF THE FIRST NODE IS THE DESIRED ONE]

                1.If (DATA(list)=’VAL’)then

                    {

                                Ptr=LIST;

                                LIST=NEXT(list);

                                Delete ptr;

                                Stop;

                    }

                       Back=list;

                       Ptr=list;

                2.while(ptr<>NULL) repeat step 3 to 5

                3.If(DATA(ptr)=’VAL’) then

                     {

                                NEXT(back)=NEXT(ptr);

                                Delete ptr;

                                Exit;}

                4.back=ptr;

                5.ptr=next(ptr);

                                [end of while loop]

                6.END

It may be noted here that the search operation had an upper hand over the insert and delete algorithms for linked lists. Therefore, efficiency and correctness of these algorithms are very much dependent upon the search operation.