What are sentinel nodes (header and trailer) in a doubly-linked list, and why use them?

Two dummy nodes that hold no element and permanently sit before the first and after the last real node; because every real node then always has a real predecessor and successor, insertion and removal need no special cases for an empty list or the ends.

Without sentinels, head and tail are plain references that can be null, and every operation has to ask awkward questions: is the list empty? Am I inserting at the very front, where there is no predecessor to update? Am I removing the only node, so both head and tail must change? Each of those is a branch in the code and a place for bugs.

With sentinels, the list always contains at least the header and the trailer:

• An empty list is just header ↔ trailer.
• The first real node is always header.next; the last is always trailer.prev.
• Inserting at the front is "insert after the header"; inserting at the back is "insert before the trailer". Both are the same general addAfter operation.

So one piece of code handles every position. The sentinels also serve as the fixed starting points for a search from either end. The cost is two extra nodes per list, which is negligible.

Algorithm addFirst(v)          { with sentinels, no empty-list check }
  w ← header.getNext()         { the first real node, or the trailer }
  v.setNext(w);  v.setPrev(header)
  w.setPrev(v);  header.setNext(v)
  size ← size + 1

Go deeper:

• Linked list — sentinel nodes — why the dummy nodes simplify the operations, and what they cost.