Removing by Index

Removing a node means rerouting links and keeping head, tail, and size correct.

We start by finding the node, using node(index) and the same bounds check as get and set:

public T remove(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  Node<T> target = node(index);
  T removed = target.value;
  // ... unlink target ...
  size--;
  return removed;
}

We save the value to return before unlinking, then reroute the links, then decrement size.

Unlinking a node in the middle

Take a node in the middle of the list, the one with value 5:

          ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀─── tail
          └───┘      └───┘      └───┘
                       ▲
                       │
                    target

Because the list is doubly linked, target can reach both neighbors directly: target.prev is the node with value 3, and target.next is the node with value 7. To remove target, we connect those two neighbors to each other so that they point past target:

Node<T> before = target.prev;
Node<T> after = target.next;
before.next = after;  // the node before points forward past target
after.prev = before;  // the node after points back past target

          before                after
            │                     │
            ▼                     ▼
          ┌───┐                 ┌───┐
head ───▶ │ 3 │ ◀─────────────▶ │ 7 │ ◀─── tail
          └───┘                 └───┘
                     ┌───┐
         target ───▶ │ 5 │   (no longer linked from either side)
                     └───┘

Once the method ends and target is no longer referenced, nothing points to the node with value 5, and it will be garbage-collected.

Removing the first or last node

If target is the first node, it has no predecessor: target.prev is null, so before.next would throw a NullPointerException. Removing the first node is also the case where the head has to change, because the second node becomes the new first node.

If target is the last node, it has no successor: target.next is null, so after.prev would throw a NullPointerException. Removing the last node is the case where the tail has to change.

So we guard each side. If there is a predecessor, we point it past target. If there is not, then target was the head, and the new head is target.next. We do the same thing on the other side. If there is a successor, we point it back past target. If there is not, then target was the tail, and the new tail is target.prev:

if (target.prev == null) {  // target is the first node
  head = target.next;
} else {
  target.prev.next = target.next;
}

if (target.next == null) {  // target is the last node
  tail = target.prev;
} else {
  target.next.prev = target.prev;
}

Removing the only node, which is both first and last, takes the if on both, setting head and tail to null and leaving an empty list.

The complete method

Here is the complete remove(index) method:

public T remove(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  Node<T> target = node(index);
  T removed = target.value;

  if (target.prev == null) {
    head = target.next;
  } else {
    target.prev.next = target.next;
  }

  if (target.next == null) {
    tail = target.prev;
  } else {
    target.next.prev = target.prev;
  }

  size--;
  return removed;
}

remove is $O(n)$ because of the call to node(index), which traverses the list to find the node. The unlinking itself is $O(1)$, because it only reroutes a fixed number of references and adjusts head, tail, and size.

DynamicArray.remove is also $O(n)$, but for a different reason. The array jumps to the index, so there is no traversal. Then it has to close the gap, which means shifting every element after the removed one left by one slot, and that is $O(n)$.