Circular doubly linked list and Tail pointer doubly linked list

Question

What are the advantage/disavantages of building a doubly linked list by using either circular pointer and tail pointer ? which one is preferrable for building a deque ?

From my opinion, they are pretty much the same in doing all the search, insert, and delete node. The only thing that is different is, for the tail pointer doubly linked list, you need to have a tail pointer points to the last node and you need to update it every time when you insert a new node after the tail. Moreover, in the circular linked list, you have the first node linked to the last node and vice-versa, while in the tail pointer, you have both of the head->prev and tail-> point to null pointer. I think both of them are greate for building a deque. It all comes down to exactly how you want your program runs. If you want your program can run back and forth between the head and tail node fast, use the circular approach, otherwise, tail pointer should be sufficient.

That is my answer to the question. Since I have not built any circular doubly linked list yet, I do not have any experience on how it runs on the machine, but I suspect it will be as fast as the tail pointer. Any suggestion at all ? And thank you everyone for their inputs.

Answer 1

Circular double-linked list is probably preferred, since you can efficiently add/remove from either the start or end and it uses a simple uniform data-structure.

The easiest way to implement a circular dbl-linked list is to hold a 'head' node of the same type as all other nodes, but always having a 'null' item/value and used only to hold the next/prev pointers to the actual "item nodes".

When the list is empty, head.next & head.prev will both point to itself.

Logic is simpler for a circular dbl-linked list, as opposed to a tail-pointer variant allowing 'head' and 'tail' to be null when empty; that requires both 'head' and 'tail' pointers to be potentially updated in any modification operation, making the logic more complex.

Naming is a little bit unclear here: I've used head to refer the the 'list node', but it could be called 'list' or 'node'.

head.next -> first -> second -> ...
head.last -> last -> second-last -> ...

If the list is empty:

head.next -> head
head.last -> head

If the list has one item:

head.next -> item -> head
head.last -> item -> head