Today we are going to have a look at an interesting data structure, the Linked List.
We’ll start of by describing the nature of a Linked List, before implementing a Linked List in Java.

What is a Linked List?

A linked list is a collection of data elements, stored in linear order.
Unlike arrays, linked lists are not organized based on their physical placement in the memory. Linked List elements (nodes from now on), are stored using pointers.
Each node in a Linked List is composed of two elements – the actual data element, and a pointer to the next node in the List.
Below you’ll see a simple visualization of a Linked List composed of three nodes:

visualization of a linked list

The above illustration is of a singly linked list – which is the type of linked list we focus on in this article.

Advantages and drawbacks of the LinkedList

You may be wondering why one would ever want to use a Linked List, instead of an array.
Surely, having data scattered all across your memory must be a huge drawback?
As you may already guessed; No, it is not!

Consider an array, which stores data continously.

Visualization of an array

Suppose you want to insert a new data element at the very front of the array.
If we were to do that, all the elements in the array must be shifted one position up. Thus, we’ll have to loop through the entire array! You don’t have to be an expert programmer to understand that for an array of 10000+ elements, this is very inefficient.

Now, suppose we perform the same operation on a Linked List. As we now know, a Linked List is composed of nodes, which have a pointer to the next node.
Insertion at the front of a Linked List only require us to make the inserted node point to the previous first node in the list.
The following figure illustrates this scenario quite nicely.

visualization of insertion into a linked list

Another quite nice advange of the Linked List is that the size is dynamic; we don’t have to specify the max number of elements. When it comes to arrays, this is something we have to do. If you’re somewhat unfamiliar with arrays, or need a quick refresh, check out my article on arrays here.
Disclaimer: The ArrayList from the Java Collections API doesn’t require that you specify an array size, but what happens under the hood here is out of scope for this article.

Okay, so the linked list does have some advantages over arrays. But what are the drawbacks?

When it comes to linked lists, random access (or direct access) is not something that can be done efficiently. Say for example that we want to access the K’th element in the list. To do that, we have to loop through the entire chain of nodes. With an array, you can simply call get(K).

On top of that, there is also the issue with extra memory space. Remember that each element in a linked list have a reference to the next element, which leads to what we call overhead, or extra memory space.

If you didn’t quite understand everything, don’t worry.  The following list sums it up quite nicely:

  •  The linked list consists of nodes.
  •  Each node consists of (at least) two parts: the actual data, and a pointer to the next node.
  • The nodes in a linked list are stored in a linear manner – not continously, as with arrays.
  • Linked lists have dynamic size, unlike arrays.
  • Insertion and deletion are performed very efficiently, in constant time, O(1).
  • Random / direct access to a linked list is not efficient, O(N). Consider using an array.

If you haven’t seen the notation O(1) and O(N), check out my article on Algorithm Analysis.

Implementation of a Linked List in Java

Now that you have a basic understanding of what a linked list is, lets do the fun part; writing some code!

Before diving right into it, let’s explain the supported methods:

  • Inserting x at the front of the list: 
    Store the current front element in a temporary variable, temp = front. Set front element to x, front = x. Make x.next = temp
  • Inserting x at the end of the list:
    Loop until the end. lastNode.next = x
  • Inserting y after x:
    Loop until x is found. Set y.next = x.next. Set x.next = y.
  • Inserting y before x:
    Loop until x is found. Make the node previous to x point to y.  Set y.next = x
  • Deleting x:
    Make the node previous to x point to x.next. In other words, we are bypassing x.

Note about the LinkedListIterator.

An iterator is used to iterate through a collection of data elements. In this custom implementation, we create a custom iterator. The iterator class, LinkedListIterator, is implemented as an inner class. The definition of an inner class is a class that is inside another class, but without the keyword static.
With inner classes, we can reference to outer class’ variables implicitly. This means that in our implementation, we write

private LinkedListIterator {
next = front
}

instead of

private LinkedListIterator(LinkedList ll){
  next = ll.front
}

As you see, with inner classes, we do not need to keep an explicit reference to the outer class.

One last thing about the LinkedListIterator; as the Java documentation for the Iterator-interface specificies, the Iterator should be invalidated if the current list is changed.

Let’s assume we’re iterating through the Linked List.

If the list changes, there is no way for the Iterator to know about the change.

Thus, we have to throw an exception if the current list is modified. In our code, we keep track of these changes with a simple counter, which keeps track of number of modifications (insert and delete).

Please refer to the comments in the Java implementation for further information.

package linkedlist;

/**
 * This class represents a node in the LinkedList.
 * The next-variable is a pointer to the next node.
 * <p>
 * Be aware that this implementation only keeps a reference to the next node, thus only forward iteration is supported.
 *
 * @author Anders Engen Olsen.com
 * @see LinkedList
 */

class ListNode<AnyType> {

    // The actual data
    AnyType data;
    // Reference to the next node
    ListNode<AnyType> next;

    /**
     * Constructor.
     * Note that the next variable is set to null, thus this is the "root-node"
     *
     * @param data node data
     */
    ListNode(AnyType data) {
        this(data, null);
    }

    /**
     * Constructor.
     * Note that the next variable is not set to null. This is not the root node.
     *
     * @param data node data
     * @param next reference to next node
     */
    ListNode(AnyType data, ListNode<AnyType> next) {
        this.data = data;
        this.next = next;
    }
}
package linkedlist;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Class representing a LinkedList.
 * The runtime of inserting at the end is O(N). This can be avoided by keeping a reference to the last node.
 * Iteration through the list is done with a custom LinkedListIterator.
 * <p>
 * The operations supported by this implementation are:
 * <p>
 * addFirst(AnyType x): Add x to the beginning of the list.
 * addLast(AnyType x): Add x to the end of the list.
 * insertAfter(AnyType x, AnyType y): find x, and insert y after x.
 * insertBefore(AnyType x, AnyType y): find x, insert y before x.
 * delete(AnyType x): find node containing x, and delete it.
 * <p>
 * Iteration can be done with a LinkedListIterator (private class)
 *
 * @author Anders Engen Olsen.com
 * @see LinkedListIterator
 * @see ListNode
 */
public class LinkedList<AnyType> {

    // Front / head node
    private ListNode<AnyType> front;

    // Counter, keeping track of how many times the List has been modified.
    private int modificationCount;

    /**
     * Constructor, creating an empty LinkedList.
     */
    public LinkedList() {
        front = null;
        modificationCount = 0;
    }

    /**
     * Checking whether the list is empty.
     *
     * @return true if empty
     */
    public boolean isEmpty() {
        return front == null;
    }

    /**
     * Adding element to the front of the list.
     */
    public void addFirst(AnyType x) {
        front = new ListNode<AnyType>(x, front);

        modificationCount++;
    }

    /**
     * Adding element to the end of the list
     */
    public void addLast(AnyType x) {
        // If the list is empty, we can add at the front.
        if (isEmpty()) {
            addFirst(x);
        }
        // Otherwise, we'll have to loop through the entire list.
        else {
            ListNode<AnyType> temp = front;

            while (temp.next != null)
                temp = temp.next;

            // We have reached the end. We can now add the element
            temp.next = new ListNode<>(x, null);

            modificationCount++;
        }
    }

    /**
     * Inserting y after x
     *
     * @param x value to find
     * @param y value to insert
     * @throws NoSuchElementException x not found
     */
    public void insertAfter(AnyType x, AnyType y) {
        if (isEmpty())
            throw new NoSuchElementException("Empty list");

        ListNode<AnyType> temp = front;

        // Looping through until we encounter x.
        while (temp != null && !temp.data.equals(x))
            temp = temp.next;

        // Throwing exception if we have reached the end. Thus, x not found
        if (temp == null)
            throw new NoSuchElementException("Element not found in list");
        else
            temp.next = new ListNode<>(y, temp.next);

        modificationCount++;
    }

    /**
     * Inserting y before x
     *
     * @param x value to find
     * @param y value to insert
     * @throws NoSuchElementException x not found
     */
    public void insertBefore(AnyType x, AnyType y) {
        if (isEmpty())
            throw new NoSuchElementException("Empty list");

        ListNode<AnyType> previous = null;
        ListNode<AnyType> current = front;

        // Looping through until we encounter x
        while (current != null && !current.data.equals(x)) {
            previous = current;
            current = current.next;
        }

        // Throwing exception if we have reached the end. Thus, x not found
        if (current == null)
            throw new NoSuchElementException("Element not found in list");
        else
            previous.next = new ListNode<>(y, current);

        modificationCount++;
    }

    /**
     * Removing x from list.
     *
     * @param x element to remove
     * @throws NoSuchElementException x not found
     */
    public void remove(AnyType x) {
        if (isEmpty())
            throw new NoSuchElementException("Empty list");

        // We do not have to loop through if the front node contains x.
        if (front.data.equals(x)) {
            front = front.next;
            modificationCount++;
            return;
        }

        ListNode<AnyType> current = front;
        ListNode<AnyType> previous = null;

        while (current != null && !current.data.equals(x)) {
            previous = current;
            current = current.next;
        }

        // We looped until the end. X is not found!
        if (current == null || previous == null)
            throw new NoSuchElementException("Not found in list");

        // Deleting current node
        previous.next = current.next;
        modificationCount++;
    }

    /**
     * Returning a LinkedListIterator, always starting at the first node (head)
     *
     * @return iterator
     */
    public LinkedListIterator iterator() {
        if (isEmpty())
            throw new IllegalStateException();

        return new LinkedListIterator();
    }

    /**
     * Implementation of a LinkedListIterator.
     * Notice that the class is not static. Thus we can access LinkedList's variable implicitly,
     * and the LinkedListIterator is considered as a member of LinkedList.
     */
    private class LinkedListIterator implements Iterator<AnyType> {

        // Next node to return
        private ListNode<AnyType> next;
        // Number of modifications.
        // If this is not equal to modificationCount in LinkedList, we invalidate the iterator.
        private int currentModificationCount;

        /**
         * Private constructor, only the LinkedList need access to this.
         */
        private LinkedListIterator() {
            next = front;
            currentModificationCount = modificationCount;
        }

        @Override
        public boolean hasNext() {
            // If the list has been changed while iterating, we throw an exception
            if (currentModificationCount != modificationCount)
                throw new ConcurrentModificationException("Invalidated");
            return next != null;
        }

        @Override
        public AnyType next() {
            // If the list has been changed while iterating, we throw an exception
            if (currentModificationCount != modificationCount)
                throw new ConcurrentModificationException("Invalidated");
            // Checking whether the list has any more elements.
            if (!hasNext())
                throw new NoSuchElementException();
            // Getting the nodes data
            AnyType val = next.data;
            // Moving to next node
            next = next.next;

            return val;
        }
    }
}