Insertion into a Linked list

Insertion in linked list can be done in two ways. First is to insert an element at the beginning of the list. Second is to insert the element after a given node. So we'll take a look at both the ways.

Let LIST be a linked list with successive nodes A and B. suppose a node N is to be inserted into the list between nodes A and B.

a. Insertion at the Beginning of a list

Suppose our linked list is not necessarily sorted and there is no reason to insert a new node in any special place in the list. Then the easiest place to insert the node is at the beginning of the list.

Algorithm: (Insertion into linked list at beginning.) INSFIRST(INFO, LINK, START, AVAIL, ITEM).

This algorithm inserts ITEM as the first node in the list.

Step I: [OVERFLOW?]
If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
Step II: [Remove first node from AVAIL list.]
(i) Set NEW := AVAIL,
(ii) AVAIL := LINK[AVAIL].
Step III: Set INFO[NEW] := ITEM. [Copies new data into NEW node.]
Step IV: [Add this node to the data list.]
(i) Set LINK[NEW] := START,
(ii) START := NEW. [Insert as first node.]
Step V: Exit.

b. Inserting after a given node

Suppose we are given the value of LOC where either LOC is the location of a node A in a linked list or LOC = NULL. The following is an algorithm which inserts ITEM into LIST so that ITEM follows node A or, when LOC = NULL, so that ITEM is the first node.

Let N denote the new node (whose location is NEW). If LOC = NULL, then N is inserted as the first node in LIST. Otherwise, we let node N point to node B (which originally followed node A) by the assignment

LINK[NEW] := LINK[LOC]

And we let node A point to the new node N by the assignment 

LINK[LOC] := NEW

Algorithm: (Insertion into a linked list after a given node.) INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM).

This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL.

Step I: [OVERFLOW?]
If AVAIL = NULL, then: Write: OVERFLOW, and Exit.

Step II: [Remove first node from AVAIL list.]
(i) Set NEW := AVAIL,
(ii) AVAIL := LINK[AVAIL].

Step III: Set INFO[NEW] := ITEM. [Copies new data into NEW node.]

Step IV: [Add this node to the data list.]
If LOC = NULL, then:
(i) Set LINK[NEW] := START,
(ii) START := NEW. [Insert as first node.]
Else: [Insert after node with location LOC.]
(i) Set LINK[NEW] := LINK[LOC],
(ii) LINK[LOC] := NEW
[End of If structure.]

Step V: Exit.