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.

Thomas W · Accepted Answer · 2013-11-05 09:28:54Z

3

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

edited Nov 5, 2013 at 9:28

answered Nov 5, 2013 at 3:19

Thomas W

14.2k4 gold badges64 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Hoang Minh Over a year ago

What is the algorithm for inserting a node before and after the head for circular doubly linked list ? Aren't they same ? because in a circular linked list, you don't actually keep track of the tail at all, and the last node can connect to the first node and vice-versa >

Thomas W Over a year ago

The algorithm for inserting a node anywhere is the same, you take a 'prev' parameter & insert after that. To insert first, you pass 'head'. To insert last, you pass 'head.prev'. Insert function must update the next pointer of the previous, the prev pointer of the next, and set the next/prev pointers of the inserted node. Job done.

Collectives™ on Stack Overflow

Circular doubly linked list and Tail pointer doubly linked list

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related