Linked List  (Introduction)[1]

• Linked List is a linear data structure, similar to arrays. 

• Linked list elements are not stored at contiguous location; 

• The elements are linked using pointers.

Limitation of Arrays

• • The size of the arrays is fixed. Upper limit on the number of elements has to be known in advance. 

  • The allocated memory is equal to the upper limit irrespective of the usage generally.

  • Inserting a new element in an array of elements is expensive, as room has to be created for the new elements and to create room existing elements have to shifted.

Advantages of LinkedList over arrays

• • Dynamic size

  • Ease of insertion/deletion

Drawbacks

• • 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.

  • Extra memory space for a pointer is required with each element of the list.

Example in Java

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. 

class LinkedList

{

    Node head;  // head of list

    /*Linked list Node*/

    class Node

    {

        int data;

        Node next;

        /*Constructor to create a new node

          Next is by default initialized

          as null*/

        Node(int d) {

           data = d;

        }

    }

}

LinkedList (Inserting a node)

A node can be added in three ways

• 1. At the front of the linked list

  2. After a given node.

  3. At the end of the linked list.

1. Add Node at front: (A 4 steps process)

• 1. The new node is always added before the head of the given Linked List. 

  2. And newly added node becomes the new head of the Linked List. 

  3. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. 

  4. Let us call the function that adds at the front of the list is add(). The add() must receive a pointer to the head pointer, because add must change the head pointer to point to the new node 

Following are the four steps to add a node at the front of the LinkedList

/* This function is in LinkedList class. Inserts a

   new Node at front of the list. This method is

   defined inside LinkedList class shown above */

public void add(int new_data)

{

    /* 1 & 2: Allocate the Node & Put in the data*/

    Node new_node = new Node(new_data);

    /* 3. Make next of new Node as head */

    new_node.next = head;

    /* 4. Move the head to point to new Node */

    head = new_node;

}

Time complexity of add() is O(1) as it does constant amount of work.

2. Add Node after a given node: (5 steps process)

We are given pointer to a node, and the new node is inserted after the given node.

Following are the 5 steps to add node after a given node.

/* This function is in LinkedList class.

   Inserts a new node after the given prev_node.

This method is defined inside LinkedList class shown above */

public void insertAfter(Node prev_node, int new_data)

{

    /* 1. Check if the given Node is null */

    if (prev_node == null)

    {

        System.out.println("The given previous node cannot be null");

        return;

    }

    /* 2. Allocate the Node & 3. Put in the data*/

    Node new_node = new Node(new_data);

    /* 4. Make next of new Node as next of prev_node */

    new_node.next = prev_node.next;

    /* 5. make next of prev_node as new_node */

    prev_node.next = new_node;

}

Time complexity of insertAfter() is O(1) as it does constant amount of work.

3. Add node at the end: (6 steps process)

• • The new node is always added after the last node of the given Linked List. 

  • For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.

  • Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

Following are the 6 steps to add node at the end.

/* Appends a new node at the end.  This method is

   defined inside LinkedList class shown above */

public void append(int new_data)

{

    /* 1. Allocate the Node &

       2. Put in the data

       3. Set next as null */

    Node new_node = new Node(new_data);

    /* 4. If the Linked List is empty, then make the new node as head */

    if (head == null)

    {

        head = new Node(new_data);

        return;

    }

    /* 4. This new node is going to be the last node, so make next of it as null */

    new_node.next = null;

    /* 5. Else traverse till the last node */

    Node last = head;

    while (last.next != null)

        last = last.next;

    /* 6. Change the next of last node */

    last.next = new_node;

    return;

}

Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.

This method can also be optimised to work in O(1) by keeping an extra pointer to tail of linked list/

Following is a complete program that uses all of the above methods to create a linked list.

// A complete working Java program to demonstrate all insertion methods

// on linked list

class LinkedList

{

    Node head;  // head of list

    /* Linked list Node*/

    class Node

    {

        int data;

        Node next;

        Node(int d) {

            data = d; 

            next = null; }

    }

    /* Inserts a new Node at front of the list. */

    public void add(int new_data)

    {

        /* 1 & 2: Allocate the Node & Put in the data*/

        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */

        new_node.next = head;

        /* 4. Move the head to point to new Node */

        head = new_node;

    }

    /* Inserts a new node after the given prev_node. */

    public void insertAfter(Node prev_node, int new_data)

    {

        /* 1. Check if the given Node is null */

        if (prev_node == null)

        {

            System.out.println("The given previous node cannot be null");

            return;

        }

        /* 2 & 3: Allocate the Node & Put in the data*/

        Node new_node = new Node(new_data);

        /* 4. Make next of new Node as next of prev_node */

        new_node.next = prev_node.next;

        /* 5. make next of prev_node as new_node */

        prev_node.next = new_node;

    }

   /* Appends a new node at the end.  This method is defined inside LinkedList class shown above */

    public void append(int new_data)

    {

        /* 1. Allocate the Node &

           2. Put in the data

           3. Set next as null */

        Node new_node = new Node(new_data);

        /* 4. If the Linked List is empty, then make the new node as head */

        if (head == null)

        {

            head = new Node(new_data);

            return;

        }

        /* 4. This new node is going to be the last node, so make next of it as null */

        new_node.next = null;

        /* 5. Else traverse till the last node */

        Node last = head;

        while (last.next != null)

            last = last.next;

        /* 6. Change the next of last node */

        last.next = new_node;

        return;

    }

    /* This function prints contents of linked list starting from the given node */

    public void printList()

    {

        Node tnode = head;

        while (tnode != null)

        {

            System.out.print(tnode.data+" ");

            tnode = tnode.next;

        }

    }

    /* Driver program to test above functions. Ideally this function

       should be in a separate user class.  It is kept here to keep

       code compact */

    public static void main(String[] args)

    {

        /* Start with the empty list */

        LinkedList llist = new LinkedList();

        /*Insert 6.  So linked list becomes 6->NUllist*/

        llist.append(6);

        /* Insert 7 at the beginning. So linked list becomes 7->6->NUllist */

        llist.add(7);

        /* Insert 1 at the beginning. So linked list becomes 1->7->6->NUllist */

        llist.add(1);

        /*Insert 4 at the end. So linked list becomes 1->7->6->4->NUllist */

        llist.append(4);

        /* Insert 8, after 7. So linked list becomes 1->7->8->6->4->NUllist */

        llist.insertAfter(llist.head.next, 8);

        System.out.println("\nCreated Linked list is: ");

        llist.printList();

    }

}

// This code is written by Rajat Mishra

LinkedList[3]

Singly linked list

Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

A singly linked list whose nodes contain two fields: an integer value and a link to the next node

Doubly linked list

In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').

Circular linked list

In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case the list is said to be 'circular' or 'circularly linked'; otherwise it is said to be 'open' or 'linear'. It is a list where the last pointer points to the first node.