5.3 claims double-ended queue requires doubly-linked list

[j-n-f]

Why does a double-ended queue require a doubly-linked list? This can be implemented with a singly-linked list

• push front - insert before the head node
• pop front - remove the head node, point to the following node
• push back - append to the tail
• pop back - remove the tail node

In all cases, you maintain a pointer to head and tail.

The only time a doubly-linked list would make sense is if you need to iterate through the entire list front-to-back and back-to-front.

[Xylphy]

The key benefit with a doubly-linked list is for pop-back operations. Since each node knows its predecessor (via the prev pointer), you can easily access and remove the tail node in O(1) time without needing to traverse the entire list.

[j-n-f]

That makes sense (how you've explained it). I didn't see that when reading the text and viewing the diagrams.

I think the diagrams are a little confusing. The one for popLast() seems to show the head node being removed (instead of the tail, the head node is colored orange). It does make sense if you view all the diagrams in order. Maybe the diagram where the node is removed could show the removed node at half opacity, or show it disconnected from the rest of the list.

Thanks for the clarification 🙂