Solution: Removing by Value

The last operation is remove(value): find the first matching value and remove it.

We could write this the same way as before:

int index = indexOf(value);
if (index == -1) {
  return false;
}
remove(index);
return true;

But that is the double traversal we noticed in the chapter. indexOf traverses the list to find the index, and then remove(index) traverses again to turn that index back into the node indexOf had already found.

We are inside the class here, so we do not have to go through an index at all. We can overload node to take a value instead, traverse once, and unlink the matching node as soon as we find it.

Solution

node(value) traverses the real nodes, starting at head.next and stopping at tail, just like indexOf:

private Node<T> node(T value) {
  Node<T> current = head.next;
  while (current != tail) {
    if (Objects.equals(current.value, value)) {
      return current;
    }
    current = current.next;
  }
  return null;
}

remove(value) uses it directly:

public boolean remove(T value) {
  Node<T> target = node(value);
  if (target == null) {
    return false;
  }
  unlink(target);
  return true;
}

current advances one node at a time, comparing each value. With remove(5), the first real node holds 3, so there is no match and current moves on:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘
                         ▲
                         │
                      current
           front                                         back
         sentinel                                      sentinel

At the next node, Objects.equals(current.value, 5) is true, so we have found the node to remove:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘
                                    ▲
                                    │
                                 current   (match)
           front                                         back
         sentinel                                      sentinel

unlink(current) reconnects its neighbors, leaving 5 detached:

          ┌─────┐      ┌───┐                 ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀─────────────▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘                 └───┘      └─────┘
           front                                         back
         sentinel                                      sentinel

                                  ┌───┐
                                  │ 5 │   (unlinked)
                                  └───┘

This is still $O (n)$ in the worst case, because we may have to search the whole list. But it avoids the double traversal from the index-based version. Once we find the matching node, removing it is $O (1)$ .

At this point, you have the same public list operations as the chapter’s LinkedList. The difference is that the sentinels handle the boundary cases. The list is empty when head.next == tail, not when head == null. The first real value is in head.next, not in head. The last real value is in tail.prev, not in tail.