Trace

LinkedList<T> is doubly linked: it keeps head, tail, and size, and every node links to both its predecessor and its successor.

Exercise

Starting from an empty LinkedList<Integer>, perform these operations in order:

list.add(10);
list.add(20);
list.add(30);
list.remove(0);
list.add(40);
list.remove(1);

After each operation, draw the list’s nodes with head and tail, and give size.

Solution

After add(10), size 1:

          ┌────┐
head ───▶ │ 10 │ ◀─── tail
          └────┘

After add(20), size 2:

          ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀─── tail
          └────┘      └────┘

After add(30), size 3:

          ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀─── tail
          └────┘      └────┘      └────┘

After remove(0) (removes the node holding 10; it is the head with no predecessor, so head moves to the node holding 20), size 2:

          ┌────┐      ┌────┐
head ───▶ │ 20 │ ◀──▶ │ 30 │ ◀─── tail
          └────┘      └────┘

After add(40), size 3:

          ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘

After remove(1) (index 1 is the node holding 30, which has a real node on both sides, so the two-line unlink applies with no guard), size 2:

          ┌────┐      ┌────┐
head ───▶ │ 20 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘