1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ None. Yours is better. They chose it because it's conventional. $\endgroup$ – Thumbnail May 18 '17 at 10:26
2
$\begingroup$

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:

    single-tail

    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:

    double-tail

    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:

    circular

    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.

$\endgroup$
  • $\begingroup$ thanks, so the approach with a circular list is better, right? $\endgroup$ – Maxim Koretskyi May 18 '17 at 16:04
  • $\begingroup$ 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. $\endgroup$ – ryan May 18 '17 at 20:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Maxim Koretskyi May 13 '17 at 8:45
  • $\begingroup$ @Maximus, ahh, that is different indeed... but a suitable modification of the comments in my answer still apply. $\endgroup$ – D.W. May 14 '17 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.