Linked Lists

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. In this chapter we consider another data structure called Linked Lists that addresses some of the limitations of arrays.

A linked list is a linear data structure where each element is a separate object.

Each element (we will call it a node) of a list is comprising of two items – the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.

Another disadvantage is that a linked list uses more memory compare with an array – we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

The Node class

In Java you are allowed to define a class (say, B) inside of another class (say, A). The class A is called the outer class, and the class B is called the inner class. The purpose of inner classes is purely to be used internally as helper classes. Here is the LinkedList class with the inner Node class

private static class Node<AnyType>
{
   private AnyType data;
   private Node<AnyType> next;

   public Node(AnyType data, Node<AnyType> next)
   {
      this.data = data;
      this.next = next;
   }
}

An inner class is a member of its enclosing class and has access to other members (including private) of the outer class, And vice versa, the outer class can have a direct access to all members of the inner class. An inner class can be declared private, public, protected, or package private. There are two kind of inner classes: static and non-static. A static inner class cannot refer directly to instance variables or methods defined in its outer class: it can use them only through an object reference.

We implement the LinkedList class with two inner classes: static Node class and non-static LinkedListIterator class.

Examples
Let us assume the singly linked list above and trace down the effect of each fragment below. The list is restored to its initial state before each line executes

  1. head = head.next;
    

     

     

  2. head.next = head.next.next;
    

  3. head.next.next.next.next = head;
    

Linked List Operations

addFirst

The method creates a node and prepends it at the beginning of the list.

undefined

public void addFirst(AnyType item)
{
   head = new Node<AnyType>(item, head);
}

Traversing

Start with the head and access each node until you reach null. Do not change the head reference.

Node tmp = head;
while(tmp != null) tmp = tmp.next;

addLast

The method appends the node to the end of the list. This requires traversing, but make sure you stop at the last node

public void addLast(AnyType item)
{
   if(head == null) addFirst(item);
   else
   {
      Node<AnyType> tmp = head;
      while(tmp.next != null) tmp = tmp.next;

      tmp.next = new Node<AnyType>(item, null);
   }
}

Inserting “after”

Find a node containing “key” and insert a new node after it. In the picture below, we insert a new node after “e”:

public void insertAfter(AnyType key, AnyType toInsert)
{
   Node<AnyType> tmp = head;
   while(tmp != null && !tmp.data.equals(key)) tmp = tmp.next;

   if(tmp != null)
      tmp.next = new Node<AnyType>(toInsert, tmp.next);
}

Inserting “before”

Find a node containing “key” and insert a new node before that node. In the picture below, we insert a new node before “a”:

For the sake of convenience, we maintain two references prev and cur. When we move along the list we shift these two references, keeping prev one step before cur. We continue until cur reaches the node before which we need to make an insertion. If cur reaches null, we don’t insert, otherwise we insert a new node between prev and cur.

Examine this implementation

public void insertBefore(AnyType key, AnyType toInsert)
{
   if(head == null) return null;
   if(head.data.equals(key))
   {
      addFirst(toInsert);
      return;
   }

   Node<AnyType> prev = null;
   Node<AnyType> cur = head;

   while(cur != null && !cur.data.equals(key))
   {
      prev = cur;
      cur = cur.next;
   }
   //insert between cur and prev
   if(cur != null) prev.next = new Node<AnyType>(toInsert, cur);
}

Deletion

Find a node containing “key” and delete it. In the picture below we delete a node containing “A”

The algorithm is similar to insert “before” algorithm. It is convinient to use two references prev and cur. When we move along the list we shift these two references, keeping prev one step before cur. We continue until cur reaches the node which we need to delete. There are three exceptional cases, we need to take care of:

  1. list is empty
  2. delete the head node
  3. node is not in the list
public void remove(AnyType key)
{
   if(head == null) throw new RuntimeException("cannot delete");

   if( head.data.equals(key) )
   {
      head = head.next;
      return;
   }

   Node<AnyType> cur  = head;
   Node<AnyType> prev = null;

   while(cur != null && !cur.data.equals(key) )
   {
      prev = cur;
      cur = cur.next;
   }

   if(cur == null) throw new RuntimeException("cannot delete");

   //delete cur node
   prev.next = cur.next;
}

Types of Linked Lists