sentinel node
A dummy node that sits permanently at the start of a linked list and holds no real data, so the list is never truly empty.
In more detail
With a sentinel, every real node has a predecessor, so insert and delete never need special cases for "the list is empty" or "this is the head". It costs one node of memory. The course's linked-list code shrinks noticeably once the sentinel is added.
Related terms
- singly linked list — A linked list in which each node points only to the next node, so it can be walked in one direction.
- sentinel value — A special value that can never be real data, used to mark a condition such as "empty", "deleted" or "end".
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers