There are two common ways to store a double linked-list:
Let
head
andtail
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 benull
.Let
head
andtail
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 throughnext
andprev
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.