Insertion operation in a Linked List

Reading time: 15 minutes | Coding time: 20 minutes

Linked List is an efficient data structure to store data. You can learn about the basics of Linked List data structure in this wonderful post. In this session, we will explore the insertion operation in a Linked List.

As we discussed previously, any data structure that stores data has three basic operations:

  • Insertion: To insert data into the data structure
  • Deletion: To delete data from the data structure
  • Search: To search for a data in the data structure

In this leason, we will explore the insertion operation in a Linked List in depth.


The structure of a node in a Linked List is as follows:

Linked List Node

The structure of a node in a doubly Linked List is as follows:

Linked List Node

The variants of insertion operation that can be performed are:

  • Inserting a node at front of the linked list
  • Inserting a node at a particular location in a Linked List
  • Inserting a node at the end of the Linked List

How to insert a node at front of a Linked List?


To insert a node, we have to redirect the next pointer of the previous node to point to the new node instead of the current one and the next pointer of the new node must point to the original next node.

To insert a node at the front of the Linked List, the head pointer should point to the new node and the next pointer of the new node must point to the previous first node.

insertion at front of the linked list

Pseudocode of inserting a node at the front of a Linked List


private void LinkFirst(E e)
{
    final Node<E> front = first;
    final Node<E> newNode = new Node<>(null, e, front);
    first = newNode;
    if( front == null)
        last = newNode;
    else
        front.prev = newNode;
    ++ size;
}

How to insert a node at a particular location of a Linked List?


To insert a node at a particular location, we have to redirect the next pointer of the previous node to point to the new node instead of the current one and the next pointer of the new node must point to the original next node.


insertion at a particular location of a linked list

Pseudocode of inserting a node at a particular location of a Linked List


private void LinkBefore(E e, Node<E> succ)
{
    Node<E> before = succ.prev;
    Node<E> newNode = new Node<E>(before, e, succ);
    succ.prev = newNode;
    if(before == null)
    {
        first = newNode;
    } 
    else
    {
        before.next = newNode;
    }
    ++ size;
}

How to insert a node at the end of the Linked List?


To insert a node, we have to redirect the next pointer of the previous node to point to the new node instead of the current one and the next pointer of the new node must point to the original next node.

To insert a node at the end of the Linked List, the next pointer of the last node should point to the new node and the next pointer of the new node must point to null.


insertion at end of the linked list

Pseudocode of inserting a node at the end of a Linked List


private void LinkLast(E e)
{
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if(l == null)
        first = newNode;
    else
        l.next = newNode;
    ++ size;
}

Implementations


Implementations of inserting a node in a Linked List is as follows:

  • Java

Java


   import java.util.*;
class LinkedList<E> implements java.io.Serializable
{
	private static class Node<E>
    {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next)
        {
            this.item = element;
            this.prev = prev;
            this.next = next;
        }
    }
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    // Creates an empty list
    public LinkedList() {}
    // Return Node at index "index" O(N) time
    public Node<E> node( int index)
    {
        if(index < (size >> 1))
        {
            Node<E> x = first;
            for(int i=0;i<index; ++i)
                x = x.next;
            return x;
        }
        else
        {
            Node<E> x = last;
            for(int i=size-1; i>index; --i)
                x = x.prev;
            return x;
        }
    }
    // Print all elements in the LinkedList
    public void printList()
    {
        Node<E> x = first;
        for(int i=0;i<size; ++i)
        {
            System.out.println(x.item);
            x = x.next;
        }
    }      
    private void LinkFirst(E e)
    {
        final Node<E> front = first;
        final Node<E> newNode = new Node<>(null, e, front);
        first = newNode;
        if( front == null)
            last = newNode;
        else
            front.prev = newNode;
        ++ size;
    }
    private void LinkLast(E e)
    {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if(l == null)
            first = newNode;
        else
            l.next = newNode;
        ++ size;
    }
    // Inserts a node before a non null node succ
    private void LinkBefore(E e, Node<E> succ)
    {
        Node<E> before = succ.prev;
        Node<E> newNode = new Node<E>(before, e, succ);
        succ.prev = newNode;
        if(before == null)
        {
            first = newNode;
        } 
        else
        {
            before.next = newNode;
        }
        ++ size;
    }
    E unlinkFirst(Node<E> f)
    {
        final Node<E> next = f.next;
        first = next;
        final E element = f.item;
        f.item = null;
        f.next = null;
        if(next == null)
            last = null;
        else
            next.prev = null;
        -- size;
        return element;
    }
    E unlinkLast(Node<E> l)
    {
        final E element = l.item;
        final Node<E> newLast = l.prev;
        l.prev = null;
        l.item = null;
        last = newLast;
        if(newLast == null)
            first = null;
        else
            newLast.next = null;          
        -- size;
        return element;
    }
    E unlink(Node<E> n)
    {
        final E element = n.item;
        final Node<E> before = n.prev;
        final Node<E> next = n.next;
        if( before == null )
            return unlinkFirst(n);
        else if(next == null)
            return unlinkLast(n);
        else
        {
            n.item = null;
            n.next = null;
            n.prev = null;
            before.next = next;
            next.prev = before;
            -- size;
        }
        return element;
    }
    void add(E e)
    {
        LinkLast(e);
    }
    void addAtEnd(E e)
    {
        LinkLast(e);
    }
    void addAtFront(E e)
    {
        LinkFirst(e);
    }
}
public class Test_LinkedList
{
    public static void main()
    {
        LinkedList<Integer> ll = new LinkedList<Integer>();
        ll.add(10);
        ll.add(9);
        ll.add(10);
        ll.add(100);
        Node<Integer> nn = ll.node(3);
        ll.unlink(nn);
        ll.add(11);
        ll.printList();
    }
}
   

Complexity


  • Worst case time complexity: Θ(1)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)