القوائم المترابطة (Linked lists)

Written Explanation

Nodes

static class Node<T> {
    T value;
    Node<T> next;
    Node(T value) { this.value = value; }
}

A node holds one value and a reference to the next node. Node<T> refers to Node<T>: the class mentions itself, which is what makes a chain possible. The list keeps references to the ends of the chain:

head                              tail
 |                                 |
[A|*]-->[B|*]-->[C|*]-->[D|null]

• head is the first node. Without it you lose the whole list, because nothing else points at the first node.
• tail is the last node. Keeping it is optional but makes adding at the end fast.
• The last node's next is null. That is how a walk knows to stop.
• An empty list has head == null.

Nodes are separate objects, so they can sit anywhere on the heap. You cannot compute where node 5 is. You must follow references.

The classic walk

Every operation that looks at the list follows the same pattern:

for (Node<T> cur = head; cur != null; cur = cur.next) {
    // look at cur.value
}

Start at head, stop when cur becomes null, step with cur = cur.next. The cost is O(n) because in the worst case it visits every node.

addFirst: O(1)

To put a new node at the front, point it at the old head, then make it the new head. The order matters:

void addFirst(T v) {
    Node<T> n = new Node<>(v);
    n.next = head;     // 1. new node points at the old first node
    head = n;          // 2. the list now starts at the new node
    if (tail == null) tail = n;   // first item: also the last
    size++;
}

If you did step 2 first, you would lose the old chain. Nothing is shifted and nothing is copied, so this is O(1).

addLast: O(1) with a tail, O(n) without

With a tail reference you attach to the end directly:

void addLast(T v) {
    Node<T> n = new Node<>(v);
    if (tail == null) { head = n; tail = n; }
    else { tail.next = n; tail = n; }
    size++;
}

Without tail you would walk from head to the last node first: O(n). So we keep both ends. Keeping tail correct is a responsibility, which leads to the main mistake of this module.

contains: O(n)

Walk the list and compare each value with equals (not ==, which compares references, as BEG-026 taught). If you reach null, the value is not there. The cost is O(n), the same as scanning an array. There is no way to skip ahead, because there is no index. Likewise get(i) walks i steps, so it is O(n).

remove: find the previous node

To remove a node, make the node before it point past it. That means you need the previous node, so the walk carries two references, prev and cur:

boolean remove(T v) {
    Node<T> prev = null;
    Node<T> cur = head;
    while (cur != null && !cur.value.equals(v)) {
        prev = cur;
        cur = cur.next;
    }
    if (cur == null) return false;          // not found
    if (prev == null) head = cur.next;      // removing the head
    else prev.next = cur.next;              // rewire around cur
    if (cur == tail) tail = prev;           // do not lose the tail
    size--;
    return true;
}

Three cases, and each needs care:

1. Not found: cur reached null; change nothing.
2. Removing the head (prev == null): the head moves to the next node.
3. Removing any other node: prev.next = cur.next skips it. If cur was the tail, the tail becomes prev. Forgetting this leaves tail pointing at a node that is no longer in the list, and the next addLast quietly adds to a detached node. This is "losing the list's tail on removal".

Finding the node is O(n); the rewiring itself is O(1). So remove(value) is O(n). If you already hold the previous node, the removal is O(1). That is the real strength of linked lists: cheap changes at a known position.

The skipped node still points at the next one, but nothing in the list points at it, so the garbage collector can reclaim it (as in the memory module, BEG-038).

Costs

Last one surprises people. In a singly linked list, nodes know only their next node. To remove the tail you must find its predecessor, so you walk from the head. A doubly linked list stores both next and prev, which fixes that, at the cost of one more reference per node. The JDK's LinkedList is a doubly linked list, according to its documentation.

Arrays versus linked nodes

Lesson 6 turns this into a rule for choosing.