How to Implementing linked lists in java

In this section, we will see the implementation of a simplified version of linked list class provided by the Java library. This shows how the lists of operations manipulate the links when the list is modified.

To keep this simple example code does not implement all methods of the class linked list. We will implement only one simply linked list, and the class list will provide direct access only to the first element of the list, not the last. Our list will not use a type parameter. We will simply store raw Object values and use coercions to get them back. The result will be a fully functional class list that shows how the links are updated in the operations add and remove and how the iterator through the list.

An object can store an object and a reference to the next node. Because the methods of both the class linked list as the iterator class have frequent access to the Node instance variables do not become private instance variables. Instead, we will make a private inner class Node of the LinkedList class. As none of the list of methods returns a Node object is safe to leave the public instance variables.

public class LinkedList
{
     . . .
     private class Node
     {
         public Object data;
         public Node next;
     }
}

The LinkedList class stores a reference first to the first node (or null if the list is completely empty).

public class LinkedList
{
   public LinkedList()
   {
       first = null;
   }
   public Object getFirst()
   {
         if (first == null)
           throw new NoSuchElementException();
           return first.data;
   }
         . . .
         private Node first;
}

Now let’s go back to the add First method (see Figure). When a new node is added to the list, it becomes the top of the list and the node that was the old top of the list; it becomes your next node:

public class LinkedList
{
   . . .
   public void addFirst(Object element)
   {
       Node newNode = new Node();
       newNode.data = element;
       newNode.next = first;
       first = newNode;
   }
       . . .
}

Remove the first element of the list works as follows. Data from the first node are saved and are later returned as the result of the method. The successor to the first node becomes the first node of the shortest list (see Figure). So no more references to the old node and the garbage collector will eventually recycle it.

public class LinkedList
{
     . . .
     public Object removeFirst()
     {
         if (first == null)
               throw new NoSuchElementException();
               Object element = first.data;
               first = first.next;
               return element;
     }
         . . .
}

Now, back to the iterator class. The ListIterator interface in the standard library defines nine methods. We omit four of them (the methods kicking the iterator and the methods applied to an entire index of iterator).

Our LinkedList class defines an internal and private LinkedList iterator class that implements the simplified ListIterator interface. As LinkedListIterator is an inner class, it has access to private resources LinkedList class – in particular, the first field and the private class Node.

Note that clients of the LinkedList class, in fact, do not know the name of the iterator class. They just know it’s a class that implements the interface ListIterator.

public class LinkedList
{
   . . .
   public ListIterator listIterator()
   {
       return new LinkedListIterator();
   }
   private class LinkedListIterator
       implements ListIterator
       {
             public LinkedListIterator()
             {
                 position = null;
                 previous = null;
             }
                 . . .
             private Node position;
             private Node previous;
       }
         . . .
}

Each iterator object has a positive reference to the last node visited. We also store a reference to the last node before that. We will need that reference to adjust the links properly the remove method.

The next method is simple. The position reference is advanced to position.next and the old position is remembered in previous. But there is a special case – if the iterator point before the first element of the list, then the old position is null and position must be set to first.

private class LinkedListIterator implements ListIterator
{
   . . .
   public Object next()
   {
       if (!hasNext())
           throw new NoSuchElementException();
           previous = position;
           if (position == null)
             position = first;
           else
               position = position.next;
               return position.data;
     }
       . . .
}

The next method should only be called when the iterator is not at the end of the list. The iterator is at the end if the list is empty (i.e., first == null) or if there is no element after the current position (position.next == null).

private class LinkedListIterator implements ListIterator
{
   . . .
   public boolean hasNext()
   {
       if (position == null)
         return first != null;
       else
       return position.next != null;
   }
       . . .
}

Remove the last node visited is more complex. If the element to be removed is the first element, we call only remove- First. Otherwise, an element in the middle of the list must be removed and the previous node must have its next updated reference to skip the removed element (see Figure). If the reference is equal to the previous position, then this call to remove does not immediately follow a call to next and launched an IllegalStateException.

According to the method definition removes invalid call removes twice the line. Therefore, the remove method sets the reference position as previous.

private class LinkedListIterator implements ListIterator
{
   . . .
   public void remove()
   {
     if (previous == position)
         throw new IllegalStateException();
       if (position == first)
         {
             removeFirst();
         }
       else
         {
           previous.next = position.next;
         }
           position = previous;
   }
       . . .
}

The set method to change the data storage on previously visited element. Its implementation is simple and straightforward because our linked list can be traversed only in one direction. The implementation of standard library linked list should monitor whether the last movement of the iterator moved forward or backward. For this reason, the standard library prohibits a call to the set method following a method add or remove. We do not impose this restriction.

public void set(Object element)
{
   if (position == null)
       throw new NoSuchElementException();
       position.data = element;
}

Finally, more complex operation is the addition of a node. You insert the new node after the current position and sets the successor of the new node as successor to the current position (see Figure)

private class LinkedListIterator implements ListIterator
{
   . . .
     public void add(Object element)
     {
         if (position == null)
           {
               addFirst(element);
               position = first;
           }
         else
           {
               Node newNode = new Node();
               newNode.data = element;
               newNode.next = position.next;
               position.next = newNode;
               position = newNode;
           }
               previous = position;
     }
         . . .
}

Full implementation of our LinkedList class is at the end of this section.

Now you know how to use the Java Library LinkedList class and had a quick introduction to understand how linked lists are implemented.

import java.util.NoSuchElementException; 
    public class LinkedList 
 { 
      public LinkedList() 
      { 
          first = null; 
      } 
      public Object getFirst() 
      { 
            if (first == null) 
                throw new NoSuchElementException(); 
                return first.data; 
      } 
      public Object removeFirst() 
        { 
          if (first == null) 
              throw new NoSuchElementException(); 
            Object element = first.data; 
              first = first.next; 
              return element; 
        } 
      public void addFirst(Object element) 
        { 
            Node newNode = new Node(); 
            newNode.data = element; 
            newNode.next = first; 
            first = newNode; 
        } 
        private Node first; 
        private class Node 
        { 
              public Object data; 
              public Node next; 
        } 
        private class LinkedListIterator implements ListIterator 
        { 
            public LinkedListIterator() 
            { 
              position = null; 
              previous = null; 
            } 
        public Object next() 
            { 
                if (!hasNext()) 
                  throw new NoSuchElementException(); 
                  previous = position; 
                  if (position == null) 
                    position = first; 
                  else 
                    position = position.next; 
                    return position.data; 
          } 
        public boolean hasNext() 
          { 
              if (position == null) 
                return first != null; 
                else 
                return position.next != null; 
          } 
        public void add(Object element) 
        { 
              if (position == null) 
                { 
                  addFirst(element); 
                  position = first; 
               } 
              else 
                { 
                    Node newNode = new Node(); 
                    newNode.data = element; 
                    newNode.next = position.next; 
                    position.next = newNode; 
                    position = newNode; 
                } 
                    previous = position; 
        } 
        public void remove() 
        { 
            if (previous == position) 
                throw new IllegalStateException(); 
              if (position == first) 
                  { 
                      removeFirst(); 
                  } 
              else 
                  { 
                      previous.next = position.next; 
                  } 
                      position = previous; 
        } 
        public void set(Object element) 
        { 
              if (position == null) 
                throw new NoSuchElementException(); 
                position.data = element; 
        } 
                private Node position; 
                private Node previous; 
    } 
 } 
 public interface ListIterator 
 { 
    Object next(); 
    boolean hasNext(); 
    void add(Object element); 
    void remove(); 
    void set(Object element); 
 }