doubly linked list empty situation

Question

In my lecture noes its given that if doubly linked list is empty then

header.next==tail;

Or

tail.prev==header; 

But I feel like this is the case when there's exactly two nodes. Shouldn't the empty case be head==null.
I don't know if I am correct.I am sill new to this subject.Can someone please clarify this

Answer 1

There are two common ways to store a double linked-list:

• Let head and tail refer to actual nodes in the tree.

  head variable       tail variable
    |                   |
    V                   V
  first -> second -> third -> null
  

  In this case, you are correct - head will be null.

• Let head and tail be special nodes (called "sentinel nodes", as pointed out in the other answer) which don't actually contain any data and point to the first and last nodes in the list through next and prev respectively.

  head variable                       tail variable
    |                                   |
    V                                   V
  head -> first -> second -> third -> tail -> null
  node                                node
  

  In this case, header.next == tail will mean the list is empty.

  One might use this approach instead of the above one to simplify the implementation a bit and make the code a bit faster - there's no need to make special provision for removing or inserting the first or last nodes.

Answer 2

This doubly-linked list is using both head and tail sentinel nodes. These are nodes that don't actually contain elements of the list, but help to make certain algorithms slightly nicer by making the head and tail cases work more like the middle of the list.

If the list weren't using sentinels, then the empty case would be head==null, and the two-element case would have header.next==tail and tail.prev==header.