Inserting in a Linked List
In the last article of learning Data Structure Series we learnt Linked List and its types. In this article, we will learn to insert a new node in a linked list. It’s very simple. All we have to do is to maintain pointer. A new node is created from the available memory space. Each node has two parts 1) Information part 2) Linked part. To insert a node we just have to set address in this linked part.
We can insert a new node at the first location, in the middle as well as at the end of linked list. First we will see how we can insert a new node at the first location of linked list.
INSFIRST( INFO, LINK, START, AVAIL, ITEM)
1. If AVAIL= NULL, then: Write: OVERFLOW and Exit. 2. Set NEW := AVAIL and AVAIL := LINK [AVAIL] 3. Set INFO [NEW] := ITEM 4. Set LINK [NEW] := START 5. Set START := NEW 6. Exit
In the above algorithm START points to the first node of the linked list. AVAIL is the list of available memory. NEW is newly created node. INFO[NEW] refers to the information part of linked list whereas LINK[NEW] refers to the next pointer part of node.
First we check to see whether the memory is available in AVAIL list or not. If AVAIL=NULL then algorithm will print OVERFLOW and Exit.
If memory is available, then we create a NEW node from the AVAIL list. In next step of algorithm we set the value of ITEM in the INFO part of NEW node.
After execution of the statement LINK[NEW] := START, NEW node will point to the original first node . Now START is pointing to original first node and NEW node is also pointing to the first node.
But we want to make NEW as first node, so we change the START pointer to point NEW node. START : =NEW
We can also insert a new node in the middle as well as at the end of linked list. Algorithm for inserting a node after the given location is as follows.
INSLOC( INFO, LINK, START, AVAIL, LOC, ITEM)
1. If AVAIL := NULL ,then: Write : OVERFLOW, and Exit. 2. Set NEW := AVAIL and AVAIL := LINK[AVAIL] 3. Set INFO[NEW] := ITEM 4. If LOC = NULL, then: Set LINK[NEW] := START and START := NEW Else Set LINK[NEW] := LINK[LOC] LINK[LOC] :=NEW [End of If] 5. Exit
We know that, AVAIL is the list of ava