 Solution

A dummy list header makes insertion or deletion at the front resemble insertion or deletion in the middle: there is always a predecessor record to update. In a circular doubly linked list, it also supplies a stable end position, handles the empty case uniformly, and avoids changing an external head pointer every time the first data node changes.

Its disadvantage is the extra record and associated storage and initialization work; traversal must also distinguish the sentinel node from real data. Thus