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.

Linked List

Linked List

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.

Insert into Linked List -Phase 1

Insert into Linked List -Phase 1

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.

Insert into Linked List -Phase 2

Insert into Linked List -Phase 2

But we want to make NEW as first node, so we change the START pointer to point NEW node. START : =NEW

Insert into Linked List -Phase 3

Insert into Linked List -Phase 3

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

You may also like...