Stacks & queues from a list

The same nodes build two different structures — depending on which end you use. · 5 min read

A linked list is a building block. Restrict where you add and remove, and you get the structures from the next chapter for free.

Only ever touch the head and you've built a stack — push and pop are both O(1) at the front:

Interactive visualization: A stack: only ever touch one end — step through it frame by frame on this page.

Add at the tail and remove from the head (keeping a tail pointer) and you've built a queue — O(1) at both ends:

Interactive visualization: A queue: add at the rear, remove from the front — step through it frame by frame on this page.