Insertion Sort a Linked List

Reading time: 15 minutes | Coding time: 20 minutes

Insertion sort is a comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Insertion Sort is preferred for sorting when the data set is almost sorted. The slow random-access performance of a linked list makes some other algorithms such as Quick Sort perform poorly, and others such as Heap Sort completely impossible.


Algorithm


The key idea of Insertion sort is to insert an element into a sorted section of the element set.

A single element is always sorted. Similarly, insertion sort begins with a single element and iteratively takes in consequtive elements one by one and inserts them into the sorted array such that the new element set is sorted as well.

The time complexity of Insertion Sort is O(N^2) and works faster than other algorithms when the data set is almost sorted.

Inserting an element in a sorted Linked List is a simple task which has been explored in this article in depth. Do check it out for better understanding.


Pseudocode


Pseudocode of Insertion Sorting a Linked List:


void insertionSort()
{
    // Initialize sorted linked list
    final Node<E> sorted = null;
    // Traverse the given linked list and insert every
    // node to sorted
    Node<E> current = first;
    while (current != NULL)
    {
        // Store next for next iteration
        Node<E> next = current.next;
        // insert current in sorted linked list
        Unlink(current); // Delete current
        sortedInsert(current.data); // Insert current in sorted order
        // Update current
        current = next;
    }
}

Complexity


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

Implementations


Implementation of applying Merge Sort on 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() {}    
    void insertionSort()
    {
        // Initialize sorted linked list
        final Node<E> sorted = null;
        // Traverse the given linked list and insert every
        // node to sorted
        Node<E> current = first;
        while (current != NULL)
        {
            // Store next for next iteration
            Node<E> next = current.next;
            // insert current in sorted linked list
            Unlink(current);
            sortedInsert(current.data);
            // Update current
            current = next;
        }
    }
    void sortedInsert(E e)
    {
         Node current = first;
         /* Special case for head node */
         if (current == null || current.data >= e)
         {
             LinkFirst(e);
         }
         else 
         {
            while (current.next != null && current.next.data < new_node.data)
                  current = current.next;
            final Node<E> newNode = new Node<>(current, e, current.next);
         }
     }
    //Checks whether the value x is present in linked list
    public boolean search(int x)
    {
        Node current = first;    //Initialize current
        while (current != null)
        {
            if (current.data == x)
                return true;    //data found
            current = current.next;
        }
        return false;    //data not found
    }
    // 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();
    }
}
   

Questions


What is the time complexity of this algorithm if Linked List is already sorted?

O(N)
O(1)
O(N log N)
O(log N)