Algorithm for creation in 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 has two parts DATA and NEXT. Let us assume that a linked list of N number of nodes is to be created. The new operator will be used for the dynamic allocation of nodes. A variable I is 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
Algorithm for TRAVERSING A LINKED LIST
Many times, it is required to traverse the 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 that is being pointed by NEXT(ptr);
Algorithm of 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 the search operation is given below:
SEARCH:
In this algorithm, a linked list, pointed by first, is traversed. While traversing the data part of each visited 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.
Algorithm for INSERTION in a Linked List
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
Algorithm for INSERTING AFTER A NODE in a Linked List
Let List be a pointer to a linked list. In this algorithm, a node X is inserted in the list after a node with a 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:
- Ptr=List;
- While (ptr<>NULL) repeat steps 3 to 4
- 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.
Algorithm for INSERTION BEFORE A NODE in a linked list
Let LIST be a pointer to a linked list. In this algorithm a node X is inserted in the list before a node with a data part equal to ‘VAL’ Two pointers ptr and back travel the list in such a way that each visited node is checked for a data part equal to ‘VAL’. If such a node is found then ptr points to the selected node and back point to the immediate previous node in the list. The node X is inserted before the selected node.
STEP:
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
Algorithm for DELETING A NODE FROM A LINKED LIST
A delete operation involves the following two steps:
a)search the list for the node that is to be deleted.
b)delete the node.
An 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 the 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, the efficiency and correctness of these algorithms are very much dependent upon the search operation.