Problem: Rebuild LinkedList with Sentinels

In this practice problem, you will rebuild LinkedList using two sentinel nodes. The public operations stay the same:

  • add(value) — add a value to the end of the list
  • get(index) — return the value at an index
  • set(index, value) — replace the value at an index
  • size() — report how many values are in the list
  • indexOf(value) and contains(value) — search for a value
  • remove(index) — remove and return the value at an index
  • remove(value) — remove the first occurrence of a value

The difference is inside the list. head and tail always point to sentinels. The first real node is head.next, the last real node is tail.prev, and the list is empty exactly when head.next == tail.

An empty list looks like this. The two sentinels are linked to each other, with no real nodes between them:

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