Insertion in a unordered LINKED LIST
Here in this case the NEW node is inserted after the location LOC. LOC is found by comparing the given Information with every node of the Linked List. For example consider the following Linked List. ROOT points to FIRST node with information 10. If a NEW node is to be inserted after a node with Information 20, 20 is given as Information.20 is compared with the information of first node, it is not equal, so it is compared with the second node it is equal hence address of second node is LOC. Now node is inserted by copying address of third node which is given by LINK of LOC, in the LINK field of NEW node and the LINK field of LOC is copied with the new node’s address given by NEW. So after the second node of the original list there comes the just inserted NEW node. When the Linked List is traversed after the second node there comes the new node as the third node. If the Information is printed it will be 10 20 15 5.
Algorithm to Insert node in unordered linked list:
INSERTNOLL(ROOT,IN)
[IN is the information of the node after which insertion is done]
If AVAIL =NULL Then:
Write: ‘Memory Allocation Error’
Exit.
[End of If]
NEW<--AVAIL
AVAIL<--AVAIL-->LINK
NEW-->LINK<--NULL
NEW-->INFO<--Information
[Information is the to be data stored in the NEW node]
LOC<--ROOT
Repeat While IN< >LOC-->INFO AND LOC< >NULL
LOC<--LOC-->LINK
[End of While]
If LOC = NULL Then:
Write: ‘Error in Insertion’
[Error because node with IN is not present]
Exit.
Else
NEW-->LINK<--LOC-->LINK
LOC-->LINK<--NEW
[End of If]
Exit.
Here in this case the NEW node is inserted after the location LOC. LOC is found by comparing the given Information with every node of the Linked List. For example consider the following Linked List. ROOT points to FIRST node with information 10. If a NEW node is to be inserted after a node with Information 20, 20 is given as Information.20 is compared with the information of first node, it is not equal, so it is compared with the second node it is equal hence address of second node is LOC. Now node is inserted by copying address of third node which is given by LINK of LOC, in the LINK field of NEW node and the LINK field of LOC is copied with the new node’s address given by NEW. So after the second node of the original list there comes the just inserted NEW node. When the Linked List is traversed after the second node there comes the new node as the third node. If the Information is printed it will be 10 20 15 5.
Algorithm to Insert node in unordered linked list:
INSERTNOLL(ROOT,IN)
[IN is the information of the node after which insertion is done]
If AVAIL =NULL Then:
Write: ‘Memory Allocation Error’
Exit.
[End of If]
NEW<--AVAIL
AVAIL<--AVAIL-->LINK
NEW-->LINK<--NULL
NEW-->INFO<--Information
[Information is the to be data stored in the NEW node]
LOC<--ROOT
Repeat While IN< >LOC-->INFO AND LOC< >NULL
LOC<--LOC-->LINK
[End of While]
If LOC = NULL Then:
Write: ‘Error in Insertion’
[Error because node with IN is not present]
Exit.
Else
NEW-->LINK<--LOC-->LINK
LOC-->LINK<--NEW
[End of If]
Exit.