Algorithm for insertion and deletion in singly linked list
Answers
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