The List ADT: Static, Dynamic, and Linked

From here on the course changes subject. You already know how to model objects and, in the Arrays of Objects: Holding and Iterating Many Instances lesson, you already stored many of them in an array with its own count. Now you will formalize that idea and — this is the important part — pick the right organization for what you plan to do with the data.

Let us start with a question that sounds silly: if ArrayList already exists, why implement a list by hand?

Because ArrayList is blazing fast at some things and terrible at others, and if you do not know why, you will choose badly. Implementing one once is what teaches you that difference for good.

1. What an ADT is

An Abstract Data Type is the separation of two things we tend to blur together:

• The specification: which operations it offers and what each one guarantees. The what.
• The implementation: how the data is laid out in memory and how each operation runs. The how.

In Java the ADT is written as an interface — exactly what you saw in the Abstract Classes, Interfaces, and Code Organization lesson:

public interface List<T> {
    void add(T item);
    boolean remove(T item);
    T get(int index);
    int size();
    boolean isEmpty();
}

Whoever programs against List<T> neither knows nor cares whether there is an array or a chain of nodes inside. That ignorance is precisely the goal.

2. Two ways to store the same thing, with opposite costs

Hold on to this idea, because it organizes everything that follows:

The array pays for insertion so that reading is free. The linked list pays for reading so that insertion is free.

3. The node: the most important class in this lesson

A node is a tiny object holding two things: a value and a reference to the next node.

public class Node<T> {
    T data;
    Node<T> next;   // ← a reference to another Node of the same type

    public Node(T data) {
        this.data = data;
        this.next = null;   // by default it points at nobody
    }
}

That Node<T> next; line is the one that trips everybody up: a class referencing itself. There is no infinite recursion there. Remember the OOP Fundamentals: Classes, Objects, and Attributes lesson: an object-typed field does not hold the object, it holds a reference (or null). A node does not contain another node: it knows where to find it.

4. Singly linked list, step by step

The whole list boils down to a single reference: the one pointing at the first node.

public class LinkedList<T> {
    private Node<T> head;   // if it is null, the list is empty
    private int size;

    public boolean isEmpty() { return head == null; }
    public int size() { return size; }
}

addFirst: the reference dance

These three lines are the heart of the whole structure, and the order between them is non-negotiable:

public void addFirst(T data) {
    Node<T> fresh = new Node<>(data);
    fresh.next = head;   // 2. the new node hooks up what was there
    head = fresh;        // 3. the list adopts it as its first
    size++;
}

Swap those last two lines and head points at the new node before anyone recorded where the old first node was. That reference is lost, and with it the whole list. It compiles perfectly. It breaks silently.

Traversal: the pattern you will repeat forever

public void print() {
    Node<T> current = head;          // a temporary pointer; never move head
    while (current != null) {
        System.out.print(current.data + " → ");
        current = current.next;      // the step that prevents an infinite loop
    }
    System.out.println("null");
}

Never use head as the traversal variable. Move it and you lose the start of the list with no way back. Always an auxiliary variable.

Appending at the end

public void addLast(T data) {
    Node<T> fresh = new Node<>(data);
    if (head == null) {              // special case: empty list
        head = fresh;
        size++;
        return;
    }
    Node<T> current = head;
    while (current.next != null) {   // note: next != null, not current != null
        current = current.next;      // you must walk the ENTIRE list
    }
    current.next = fresh;
    size++;
}

Notice the difference from the previous traversal: here the condition is current.next != null, because we want to stop on the last node, not step past it into null. That is a classic mistake.

And notice the cost: appending walks the whole list. That is the weakness of a singly linked list, and it is fixed by also keeping a tail reference.

5. Variants: doubly linked and circular

In the doubly linked list, the node gains a backward reference:

public class DoubleNode<T> {
    T data;
    DoubleNode<T> next;
    DoubleNode<T> previous;   // the one that makes it reversible
}

With that you can walk backwards and, above all, delete a node given only that node, without traversing to find its predecessor. That is what Java’s LinkedList uses internally.

In the circular list, the last node points at the first. It is used for round-robin turns, buffers, and repeat-mode players. Traversal changes shape:

// In a circular list this would be an infinite loop:
// while (current != null) { ... }

Node<T> current = head;
do {
    System.out.print(current.data + " → ");
    current = current.next;
} while (current != head);   // you stop when you get back to the start

6. The table that decides

And the practical conclusion, which is what matters:

In 95% of cases, use ArrayList. Sequential traversals over contiguous memory are far faster than the table suggests, because the processor prefetches whole contiguous blocks into its cache. A LinkedList with scattered nodes loses that advantage entirely.

LinkedList wins when you constantly insert and remove at the ends and almost never index into it. That case exists — you will see it in the next lesson, with stacks and queues — but it is the minority.

7. Common mistakes

8. Guided hands-on exercise

Challenge: remove(T data) on the singly linked list

Implement remove so that it:

1. Returns true when it removed something and false when the value was not there.
2. Works when the list is empty.
3. Works when the element to delete is the head.
4. Works when it is in the middle or at the end.
5. Updates size correctly.

Think through the four cases before writing anything. That is where all the difficulty of this exercise lives.

public class LinkedList<T> {
    private Node<T> head;
    private int size;

    public void addFirst(T data) {
        Node<T> fresh = new Node<>(data);
        fresh.next = head;
        head = fresh;
        size++;
    }

    public boolean remove(T data) {
        // CASE 1: empty list. Without this, the next line blows up.
        if (head == null) {
            return false;
        }

        // CASE 2: the element is the head.
        // It is different because there is no "previous" node to rewire.
        if (java.util.Objects.equals(head.data, data)) {
            head = head.next;   // the list now starts at the second node
            size--;
            return true;
        }

        // CASES 3 and 4: middle or end.
        // We always stand ONE node before the candidate, because unhooking a
        // node means modifying the 'next' of the node before it.
        Node<T> previous = head;
        while (previous.next != null) {
            if (java.util.Objects.equals(previous.next.data, data)) {
                previous.next = previous.next.next;   // the jump
                size--;
                return true;
            }
            previous = previous.next;
        }

        // We walked the whole list and it was not there.
        return false;
    }

    public void print() {
        Node<T> current = head;
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.data).append(" → ");
            current = current.next;
        }
        System.out.println(sb.append("null").append("  (size ").append(size).append(")"));
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(30);
        list.addFirst(20);
        list.addFirst(10);
        list.print();                              // 10 → 20 → 30 → null  (size 3)

        System.out.println(list.remove(20));  // true  — middle case
        list.print();                              // 10 → 30 → null  (size 2)

        System.out.println(list.remove(10));  // true  — head case
        list.print();                              // 30 → null  (size 1)

        System.out.println(list.remove(99));  // false — not present
        System.out.println(list.remove(30));  // true  — last element
        list.print();                              // null  (size 0)

        System.out.println(list.remove(1));   // false — empty list
    }
}

Key takeaways

• An ADT separates the what (the specification) from the how (the implementation). In Java the what is written as an interface.
• Array and linked list have inverse costs: one pays for insertion so reading is free, the other the other way round.
• A node is an object holding a value and a reference to another node. It does not contain it: it knows where it is.
• In addFirst, the order of the two assignments is non-negotiable: hook up first, move head second.
• Always traverse with an auxiliary variable; moving head destroys the list.
• The four cases of every operation are: empty list, first element, middle element, element not present.
• The doubly linked list walks backwards and deletes without searching for the predecessor; the circular one has no null and changes the stop condition.
• In production, ArrayList nearly always. Contiguous memory beats the theory thanks to the processor cache.