Question

Algorithm for insertion and deletion in singly linked list

Answer 1

Answer:

Step-by-step explanation:

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