Linked Nodes

Note

Objectives

1. Explain the performance problem with ArrayList.remove.
2. Explain the role of encapsulation in both linked lists and resizing array lists.

Code: LinkedStack.java, LinkedQueue.java

Dynamic arrays aren't the only way to implement lists. In fact, for some methods, they can actually be quite slow. Lists not only allow adding elements, but also removing elements by a given index. How might we implement the remove(int index) method for the above ArrayList class?

// This method also returns the element that was removed.
public E remove(int index) {
    // Return null if the index is not in the given list.
    if (index >= size) {
        return null;
    }

    // Hold onto the element so that it can be returned later.
    E result = elementData[index];

    // Shift all following elements left by 1 position, thereby
    // removing the element at the given index.
    for (int i = index + 1; i < size; i += 1) {
        elementData[i - 1] = elementData[i];
    }

    // Decrement the size to indicate the list has shrunk.
    size -= 1;

    // Return the saved element.
    return result;
}

Why do we need to shift all the following elements down by 1 spot?

We need to shift all the following elements down by 1 to maintain the ArrayList class invariant. The i-th index in the array must hold the i-th value in the list; we can't have any gaps in the array! If we didn't shift all the following elements down by 1, methods like toString would no longer work.

Shifting elements can take a lot of time: if we want to remove the first element in an ArrayList, every other element needs to move over too. Linked nodes are an alternative to arrays for representing an ordered sequence of elements. Whereas arrays store all the elements together in memory, each linked node contains its own element and a "link" or reference to the next node. For example, our LinkedList class can represent linked nodes with a Node class consisting of two fields:

• The value of the node's element as the value field.
• A reference to the next element in the list.

public class Node<E> {
    private final E value;
    private Node<E> next;

    public Node(E value) {
        // Calls the other constructor to set the next field to null,
        // meaning that there is no next linked node in the sequence.
        this(value, null);
    }

    public Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }
}

It might seem strange for the Node class to contain a field referencing itself, but this is allowed in Java. We use the next field to access the node in the list after the current one. Remember that this is only a reference and does not store the actual object itself. A null next field indicates the end of a sequence of linked nodes.

The value field is marked final to prevent changes to value after the Node is created. In this course, we focus our study of linked nodes on changing only the references to next. For example, the following code represents the linked list [1, 2, 3].

Node<Integer> n1 = new Node<>(1);
Node<Integer> n3 = new Node<>(3);
Node<Integer> n2 = new Node<>(2, n3);
n1.next = n2;

Important

Open the preloaded Java Tutor environment to visualize this code one step at a time. Before each time you press Next >, predict what will change in the visualization.

After running the entire block of code, what is the value of n1.next.next.value?

Let's reason about this one subexpression at a time.

1. n1 refers to the node storing the value 1.
2. n1.next refers to the node storing the value 2, or n2.
3. n1.next.next refers to the node storing the value 3, or n3.
4. n1.next.next.value evaluates to 3, the value stored in n3.

Where do we write the add, remove, size, and toString methods? If each Node stores a single element's value, how do we refer to all the elements? We need a LinkedList class that encapsulates all the Node objects by bundling together all the data with the methods for operating on all of it.

public class LinkedList<E> implements List<E> {
    // Reference to the first node in the sequence.
    private Node front;

    public void add(E element) {
        if (front == null) {
            // If the list is empty, assign the new node to the front.
            front = new Node(element);
        } else {
            // Otherwise, add the element to the end of the list.
            Node current = front;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node(element);
        }
    }

    public E remove(int index) {
        // You'll implement this in your project.
    }

    public int size() {
        // Count the number of nodes starting from front.
        int result = 0;
        Node current = front;
        while (current != null) {
            result += 1;
            current = current.next;
        }
        return result;
    }

    private class Node {
        private final E value;
        private Node next;

        public Node(E value) {
            this(value, null);
        }

        public Node(E value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

Tip

Java allows classes to be nested within other classes. In this case, we say that Node is an inner class of LinkedList. Note that the <E> generic type does not have to be repeated in the inner class because each Node is associated with its encapsulating LinkedList. We also changed the Node access modifier from public to private to indicate that Node is only relevant to the implementer of LinkedList.

Encapsulation doesn't only describe the relationship between linked lists and their linked nodes. It can also be used to describe the relationship between array lists and their underlying arrays. Or really any class whose implementation details are hidden from clients---which is just about any program that we will write in this course! Encapsulation is the most common way to define an abstraction in data structures and algorithms.