Linked List

Reading time: 15 minutes | Coding time: 20 minutes

List is a collection of similar type of elements. There are two ways of maintaining a list in memory.The first way is to store the elements of the list in an array,but arrays have some restrictions and disadvantages.The second way of maintaining a list in memory is through linked list. Let us study what a linked list is and after that we will come to know how it overcomes the limitations of array.

In this article, we will explore the simplest form of Linked List which is known as Singly Linked List. There are several modifications of Linked List which finds use in various basic and advance applications. We will explore each one subsequently.

Singly linked list


A singly linked list is made up of nodes where each node has two parts:

  • The first part contains the actual data of the node
  • The second part contains a link that points to the next node of the list that is the address of the next node.
Linked List Node

The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.

resizeof_of_linkedlist-1

Advantages of Linked List over arrays

  1. Dynamic size
  2. Ease of insertion and deletion in constant time

Drawbacks of Linked List:

  1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
  2. Extra memory space for a pointer is required with each element of the list.

Representation of Linked List in C:

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:

  1. data
  2. pointer to the next node

In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.


Implementations


Implementation of Linked List class with all operations:

  • 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


Complexity of Insertion operation in a Linked List:

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

Complexity of Deletion operation in a Linked List:

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

Complexity of Search operation in a Linked List:

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

Applications


Real life applications of a Linked List is as follows:

  • Linked Lists can also be used to represent Graphs as adjacent matrices which is a much space efficient representation than an array. Memory consumption with an array for a graph with N nodes is of the order of O(N^2) and with a linked list is of the order of O(N).
  • Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list.
  • Undo functionality in Photoshop or Microsoft Word uses Linked List
  • Accessing next element in a Linked List takes less time compared to an Array. This is because Linked List takes the natural advantage of locality of reference and hence, works well with caches.