Insertion in a linear linked list can be done in these ways-
- Insertion at the beginning
- Insertion at the end
- Insertion after a node with given value
- Insertion before a node with given value
- Insertion at a given position
- Insertion in a sorted Linked List
Insertion at the Beginning
When a node has to be inserted at the beginning of the linked list, the original first node becomes second node and the new node becomes the first node. This is done by assigning the address stored in START pointer to the LINK part of the new node. Address of new node is saved in the START pointer making it first node in the linked list.
Insertion in a Linked List at the End
After inserting node at the end of the linked list, the last node becomes second last node. The new node becomes the last node. This is done by traversing to the end of the Linked List. The last node’s address is stored in a pointer PTR. LINK part of the last node identified by PTR pointer is given the address of new node.
Insertion after a node with given value
Insertion of a new node after a node with a given value, is done by following these steps –
- Traverse the linked list to locate the element after which the new node is to be inserted. Store address of this node in a pointer PTR.
- Store value of LINK part of the node identified by PTR in LINK part of NEW node
- Store NEW address in the LINK part of the node identified by PTR
Insertion Before a node with given value
A new node can be inserted before a node with given value by following these steps
- Traverse the linked list to locate the element before which the new node is to be inserted. Store address of its previous node in SAVE pointer and the current node in PTR pointer.
- Store address stored in LINK part of the node identified by SAVE in LINK part of NEW node
- Store NEW address in the LINK part of the node identified by SAVE
Insertion at a given Position
A node can be inserted an element at a given location. For example you want to insert element at 7th Location. In this case a counter variable is required that increments with each iteration of traversal process. A pointer SAVE can be used to store the address of previously traversed node. When this counter becomes equal to the position of insertion, the following things are done-
- Update LINK of NEW node with LINK of SAVE (handing the address of next node to new node)
- Update LINK of node identified by SAVE pointer with address of NEW node
Insertion in a Sorted Linked List
Insertion in a Linked List with elements in sorted values, allows insertion of a new node at a location. The sorted order of nodes on DATA part or Key value is maintained. The following things are done for such an insertion-
- Linked list is traversed to find a node with value just greater than the node to be inserted .
- In the traversal process, a pointer SAVE is used to store the address of previously traversed node. PTR pointer stores the address of the current node with which the node to be inserted is compared.
- When a correct location for insertion is identified after comparison , LINK of new node is updated with LINK of SAVE (handing the address of next node to new node)
- LINK of node identified by SAVE pointer is updated with the address of new node
Be First to Comment