1

I am learning about queue data structure in python. I learnt the implementation of a queue using list in python and the issue of memory wastage when we dequeue a few elements from the front. We use a circular queue ( wrap around from the last index to the first) to overcome this issue. All fine and dandy!

Then we learn about using linked list to implement a queue and then textbooks show circular linked list ( tail pointing back to head) to implement a circular queue. But is that needed? There is no issue of memory wastage in linked list, therefore there should be no concept of "circular". But everywhere I see, there is a circular linked list to implement a "circular" queue. Does making the linked list "circular" add any value if we already maintain the head and tail pointer ( like in leetcode 622).

Similarly, when we implement a deque ( leetcode 641), we use a doubly linked list(DLL) and usually people again connect the tail pointer to the head pointer. But in terms of the interface (or ADT) of a deque its not really needed ( or is it?)

I tried submitting the code with and without the "circular" linked list and both seem to work ( as it should!).

Can someone clarify this for me. Am i missing something here?

Improve this question

1 Answer 1

Reset to default
1

There is no surprise that different implementations can solve the same problem.

Whether you make the linked list circular or not (for the purpose of a queue), is an implementation choice.

Both provide a way to access both the head and the tail nodes of the linked list in O(1) time complexity, which is required if you want to implement an efficient queue.

You can achieve this by storing both references separately, or by storing just the tail reference, and put the other (the head reference) as the "next" property of the tail node, thereby making it a circular list. The focus is here not so much on making the list circular, but to find some location where to maintain the reference to the head node, and since in a non-circular linked list, the "next" property of the tail node is by definition null, you can use that spot to store the reference to the head node.

One reason to use the circular version is that the code may look more elegant as it has to manage fewer references outside the scope of a node. For instance, removing the head node is an operation that does not need to update a separate reference: it is a pure node manipulation.

This analysis is similar for deque implementations that use a doubly linked list: if the list is not circular, you need two references again: one to the tail, and one to the head. But you can store these two references in the head.prev and tail.next respectively, making the list circular. Then you only need to maintain one reference (either the head or the tail) outside of the nodes themselves, and the code for the standard operations will often look more elegant.

For doubly linked lists there is even a third variation that can be handy: a circular one that has a sentinel node. The sentinel node has the references to the head and the tail through its prev and next members. This can make the code even more elegant, as less code is needed to deal with the boundary case of an empty list.

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

1 Comment

Yes thats what I was thinking. Thanks for confirmation. I read so many references nowhere they mention this. They blindly start with logic that in order to make the queue “circular” we need to physically make it circular without explaining why its needed. A simple linked list with head and tail pointer is a valid circular queue and a DLL with head and tail is a valid deque.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.