# What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've implemented the same functionality as a circular linked list using only one pointer tail. I'm wondering what's the advantage of two pointers versus one in a circular list. It takes more space as I understand so why did they choose this implementation?

• None. Yours is better. They chose it because it's conventional. May 18, 2017 at 10:26

If you're not using a circular list, then you must have a pointer to head and tail to achieve $O(1)$ enqueue and dequeue. Furthermore, if it is not a circular list and not a doubly-linked list, then without a pointer to head, we can't enqueue!

Some picture might help a little too.

1. Single Linked List with only tail pointer:

There's no way to get back to the head to enqueue! We would have to remedy this with a pointer to the head.

2. Doubly Linked List with only tail pointer:

We can get back to the head, but at an $O(n)$ cost, we might as well just add another pointer to head for convenience.

3. Single Circular Linked List with only tail pointer:

We can get back to the head in $O(1)$! This is a good shortcut. In circular linked lists this node can sometimes implemented as a Sentinel Node which does not contain any information but works as a separator between the head and tail of the queue.

In terms of additional space, adding tail or head or both is almost negligible. The nodes will be taking up memory no matter what, it's just whether or not you use a variable to reference them. Using a circular linked list kind of acts like a head pointer if you think about it. tail.next would be a synonym for head, so it's not really saving space, nor is it really costing much space.

• thanks, so the approach with a circular list is better, right? May 18, 2017 at 16:04
• Better is a very subjective term. Whichever you can better defend for reasons why you chose it would most likely be a better choice. They both have pros and cons. It's really up to you to decide which one is better for your circumstances.
– ryan
May 18, 2017 at 20:07

One possible advantage is that it is a little easier to understand how the push and pop operations work with a doubly-linked list. The use of a singly-linked circular list is not that much harder to understand, but it is a trick, and at this stage where it's the first time you're seeing anything of the sort, any extra complication can be extra confusing.

• thanks, work with a doubly-linked list - I didn't probably specify it correctly. It's not doubly-linked list, i.e. the nodes don't have two pointers (next and previous), it's that instead of a pointer to first node head only there's also a pointer to the last node tail. Or is that also called doubly-linked list? May 13, 2017 at 8:45
• @Maximus, ahh, that is different indeed... but a suitable modification of the comments in my answer still apply.
– D.W.
May 14, 2017 at 2:03