Linked Lists, Stacks & Queues

Linear structures store data in a single sequence, but what makes stacks and queues powerful is not what they can do — it is what they deliberately forbid. We restrict how data is accessed on purpose, trading flexibility for a guaranteed O(1) cost and a correct ordering of work.

The discipline of restriction is the key idea: the less a structure can do, the easier it is to reason about.

Linked lists

Arrays store data in contiguous memory, which makes indexed access O(1). But they have limits: inserting or deleting in the middle forces every later element to shift, an O(n) operation, and their size is often fixed up front.

A linked list solves this with the idea of a node — small records scattered through memory. Each node holds its data and a pointer to the next node. There is no contiguous block to shift — only arrows to rewire.

Singly linked lists

head
 │
 ▼
┌────┬───┐   ┌────┬───┐   ┌────┬───┐
│ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │ ✕ │
└────┴───┘   └────┴───┘   └────┴───┘
 data next    data next    data next(null)

Once you already hold a pointer to a node, inserting or deleting at that position is just rewiring a few arrows — O(1), with no shifting at all.

But there is a price: a linked list has no index. To reach node i you must walk from head one step at a time, so indexing is O(n), and searching for a value is O(n) too.

Worked example 1 — prepend vs. append. Suppose we build the list [4, 8, 15] by only ever inserting at the head, one value at a time, starting from an empty list.

Step	Operation	List after	Pointers touched	Cost
1	prepend 15	15 → null	head = new node	O(1)
2	prepend 8	8 → 15 → null	new.next = head, head = new	O(1)
3	prepend 4	4 → 8 → 15 → null	new.next = head, head = new	O(1)

Every prepend is O(1) because we only ever touch head and one next pointer. Now compare that to appending the same three values in order, with only a head pointer and no tail pointer:

Step	Operation	Work required	Cost
1	append 4	walk 0 nodes from head (list empty)	O(1)
2	append 8	walk 1 node to find the last one	O(n)
3	append 15	walk 2 nodes to find the last one	O(n)

Appending without a tail pointer degrades to O(n) per call because you must walk the whole list to find the last node before rewiring it. Keeping a tail pointer (updated on every append) restores O(1) — this is exactly the trick collections.deque and most production linked-list implementations use.

Doubly linked lists

A doubly linked list adds a second pointer per node, prev, pointing backward. The cost is more memory per node; the payoff is the ability to walk backward in O(1) per step, and to delete a node in O(1) given only a pointer to that node — no need to separately track or search for its predecessor.

head                                                          tail
 │                                                              │
 ▼                                                              ▼
┌────┬────┬────┐        ┌────┬────┬────┐        ┌────┬────┬────┐
│null│ 10 │ ●──┼───────▶│ ●──┼ 20 │ ●──┼───────▶│ ●──┼ 30 │null│
└────┴────┴────┘◀───────┴────┴────┴────┘◀───────┴────┴────┴────┘
 prev data next            prev data next           prev data next

Worked example 2 — deleting the middle node. To remove the node holding 20 from the list above, rewire exactly two arrows: the node before it must point forward past it, and the node after it must point backward past it.

Step	Action	Effect
1	node20.prev.next = node20.next	node 10 now points forward to node 30, skipping 20
2	node20.next.prev = node20.prev	node 30 now points backward to node 10, skipping 20
3	(node 20 is now unreachable)	garbage collected; list is 10 ⇄ 30

Both steps are required. Skip step 2 and the list still “reads” correctly forward, but walking backward from 30 would incorrectly land back on the deleted node 20 — a subtle bug that only shows up when someone traverses in the other direction (see Exercise 2).

Property	Array	Singly linked list	Doubly linked list
Indexed access	O(1)	O(n)	O(n)
Search for a value	O(n)	O(n)	O(n)
Insert/delete at a known node	O(n)	O(1) forward only	O(1) either direction
Insert/delete at the head	O(n)	O(1)	O(1)
Insert/delete at the tail	O(n)	O(1) with tail pointer, else O(n)	O(1) with tail pointer
Traverse backward	O(1) per step	not possible	O(1) per step
Memory per element	Low (data only)	Medium (data + 1 pointer)	High (data + 2 pointers)

Stacks (LIFO)

A stack is a LIFO (Last In, First Out) structure — the most recently added item comes out first, like a stack of plates where you can only take the top one. It has just two core operations:

• push — place an item on top, O(1)
• pop — remove the top item, O(1)

Real-world uses: the undo button in applications, backtracking (trying a path, and unwinding to the last decision point when it fails — mazes, puzzle solvers, recursive search), the call stack a language uses to remember which function called which, and balanced-parentheses checking in compilers and editors.

stack = []          # a Python list works directly as a stack

stack.append("A")   # push
stack.append("B")   # push  -> ['A', 'B']
top = stack.pop()   # pop   -> returns 'B', leaves ['A']

Worked example 3 — checking balanced brackets with a stack. Trace is_balanced("{[()]}"): push every opening bracket, and on a closing bracket, it must match whatever is currently on top.

Step	Char	Action	Stack (top → right)
1	{	push	{
2	[	push	{ [
3	(	push	{ [ (
4	)	pop, expect ( — matches	{ [
5	]	pop, expect [ — matches	{
6	}	pop, expect { — matches	(empty)

Stack empty at the end → balanced. If any closing bracket found the wrong thing on top, or the stack were empty when a closing bracket needs to pop, the string is unbalanced immediately.

Worked example 4 — the call stack, made visible. Every function call your program makes is implicitly pushed onto a stack by the language runtime, and popped when it returns. Trace factorial(4):

Step	Action	Call stack (top → bottom)
1	call factorial(4)	factorial(4)
2	it calls factorial(3)	factorial(3), factorial(4)
3	it calls factorial(2)	factorial(2), factorial(3), factorial(4)
4	it calls factorial(1) → base case, returns 1	factorial(2), factorial(3), factorial(4)
5	factorial(2) returns 2 * 1 = 2	factorial(3), factorial(4)
6	factorial(3) returns 3 * 2 = 6	factorial(4)
7	factorial(4) returns 4 * 6 = 24	(empty)

This is why deep, unbounded recursion crashes with a RecursionError / “stack overflow” — the call stack is a real stack with finite space. It is also why backtracking algorithms (maze solving, N-Queens, Sudoku solvers) are naturally written as recursion: the language’s call stack is the stack of decisions to unwind when a path fails.

Queues (FIFO)

A queue is a FIFO (First In, First Out) structure — first come, first served, like people waiting in line. Its core operations are:

• enqueue — add an item at the back, O(1)
• dequeue — remove the item at the front, O(1)

Real-world uses: task scheduling (a print spooler, a job queue, an OS’s ready queue), breadth-first search (BFS) over graphs and trees, and rate-limited request handling.

Worked example 5 — BFS with a queue. Given the graph A–B, A–C, B–D, C–D, D–E, trace a breadth-first search starting at A. A queue guarantees we visit everything at distance 1 before anything at distance 2.

Step	Dequeue	Visit	Newly enqueued (unvisited neighbors)	Queue after
0	—	—	—	[A]
1	A	A	B, C	[B, C]
2	B	B	D	[C, D]
3	C	C	(D already queued)	[D]
4	D	D	E	[E]
5	E	E	—	[]

Visit order A, B, C, D, E — layer by layer, distance 0, then 1, then 2. Swap the queue for a stack and you get depth-first order instead (A, C, D, E, B or similar) — same graph, different structure, completely different traversal.

Why list.pop(0) is O(n) but deque.popleft() is O(1)

A Python list is a dynamic array under the hood — contiguous memory. Enqueuing with append() is O(1) (amortized), but dequeuing from the front with pop(0) forces every remaining element to shift left by one slot to close the gap — O(n) per call, and O(n²) to drain n items.

collections.deque is implemented as a doubly linked list of small fixed-size blocks. Both ends are first-class citizens — adding or removing at either end just rewires a few pointers, exactly like the doubly linked list from the section above. No shifting, ever.

from collections import deque

q = deque()
q.append("A")        # enqueue at the back   O(1)
q.append("B")
first = q.popleft()  # dequeue at the front  O(1)  -> returns 'A'

Deque — the double-ended queue

A deque (pronounced “deck”) generalizes both stack and queue: it supports push and pop at both ends in O(1).

from collections import deque

d = deque([2, 3, 4])
d.appendleft(1)   # [1, 2, 3, 4]   O(1) at the front
d.append(5)       # [1, 2, 3, 4, 5]  O(1) at the back
d.pop()           # -> 5, leaves [1, 2, 3, 4]   O(1) at the back
d.popleft()       # -> 1, leaves [2, 3, 4]      O(1) at the front

Use a deque instead of a plain list whenever you need to add/remove from both ends efficiently: a sliding window over a stream, a browser-history-as-single-structure, a work-stealing scheduler (workers steal from one end while the owner pushes/pops the other), or simply “a queue that also needs undo.”

Complexity summary

Operation	Array	Linked list	Stack	Queue	Deque
Access by index	O(1)	O(n)	O(1) top only	O(1) front only	O(1) at either end
Insert at front	O(n)	O(1)	—	—	O(1)
Insert at back	O(n)*	O(1) with tail ptr	O(1) (push)	O(1) (enqueue)	O(1)
Delete at front	O(n)	O(1)	—	O(1) (dequeue)	O(1)
Delete at back	O(1)*	O(1) doubly / O(n) singly	O(1) (pop)	—	O(1)
Search	O(n)	O(n)	O(n)	O(n)	O(n)

*Python’s dynamic array amortizes append/pop at the end to O(1); it is only the front operations that are O(n).

Stacks, queues, and deques are usually built on top of an array or linked list. They are access rules, not new ways of storing data — the whole lesson of this page is that the rule you pick determines your Big-O, not the raw data itself.

Real-world problem — the browser’s Back/Forward buttons

A browser’s Back and Forward buttons can be modeled with two stacks:

• Visiting a new page → push the current page onto the back stack and clear the forward stack.
• Pressing Back → pop from the back stack to become the current page, and push the old page onto the forward stack.
• Pressing Forward → pop from the forward stack to become the current page, and push the old page back onto the back stack.

Why a stack? Because “going back” is LIFO by nature — you always return to the page you just left first, and every operation is O(1). A queue (FIFO) would reverse the order and break the meaning entirely: pressing Back would take you to the oldest page you visited, not the most recent one.

At scale (a session with thousands of navigations) the naive alternative — storing history as a plain list and re-slicing it on every navigation — is O(n) per click because slicing copies. The two-stack design keeps every click O(1) regardless of history length.

Alternative design: many real browsers model history as a single doubly linked list with a current pointer instead of two stacks. Back/Forward just moves current along prev/next; visiting a new page cuts the next chain from current onward. Same O(1) guarantee, different mental model — proof that stacks, queues, and linked lists are often interchangeable skins over the same idea.

Exercises

Exercise 1 — Big-O: append with and without a tail pointer. A singly linked list keeps only a head pointer (no tail). What is the complexity of appending one new element to the end? What changes if the list also maintains an up-to-date tail pointer?

Answer

Without a tail pointer, appending is O(n): you must walk from head to the last node before you can attach the new one. With a tail pointer that is kept up to date on every insertion, appending becomes O(1): rewire tail.next = new_node, then tail = new_node. This is exactly the trick that makes collections.deque fast at both ends.

Exercise 2 — spot the bug in a doubly linked list deletion.

def remove(node: "Node") -> None:
    node.prev.next = node.next
    # (nothing else)

This “works” in casual testing — forward traversal looks fine. What breaks, and when does the bug actually show up?

Answer

It forgets node.next.prev = node.prev. Forward traversal (node.next, node.next.next, …) never touches prev, so it looks correct. But traversing backward from any node after the deleted one will still find prev pointing at the removed node — you can walk right back into “deleted” memory. It also silently breaks if node is the tail (node.next is None) or the head (node.prev is None) — those cases need to update head/tail instead of dereferencing a None. Fixed version:

def remove(node: "Node") -> None:
    if node.prev:
        node.prev.next = node.next
    else:
        head = node.next          # node was head
    if node.next:
        node.next.prev = node.prev
    else:
        tail = node.prev          # node was tail

Exercise 3 — predict the output (stack).

s = []
s.append(1)
s.append(2)
s.append(3)
s.pop()
s.append(4)
s.pop()
s.append(5)
print(s)

Answer

[1, 5]. Trace: [1] → [1,2] → [1,2,3] → pop → [1,2] → [1,2,4] → pop → [1,2]… wait, trace carefully: after s.append(4) the list is [1, 2, 4]; the next s.pop() removes 4, leaving [1, 2]; then s.append(5) gives [1, 2, 5]. Final answer: [1, 2, 5].

Exercise 4 — predict the output (queue vs. stack, same inputs). The same three operations — insert A, insert B, remove one, insert C — are run once on a stack and once on a queue. What does each contain at the end?

Answer

Stack: push A, push B → [A, B]; pop removes B (last in) → [A]; push C → [A, C]. Queue: enqueue A, enqueue B → [A, B]; dequeue removes A (first in) → [B]; enqueue C → [B, C]. Same operations, same inputs, different final contents — proof that the access rule, not the data, drives the result.

Exercise 5 — pick the data structure. For each scenario, name the best-fit structure (singly linked list, doubly linked list, stack, queue, or deque) and say why in one sentence:

1. A music player’s “previous track” / “next track” navigation.
2. A customer-support ticket system that must serve tickets in the order they arrived.
3. Undoing and redoing edits in a document editor.
4. A sliding-window algorithm that needs to drop items from the front and the back as a window moves.

Answer

1. Doubly linked list (or a deque acting as one) — you need O(1) movement in both directions from the current track.
2. Queue — strict FIFO fairness; first ticket in is the first one served.
3. Two stacks (or one deque) — undo/redo is LIFO in each direction, exactly like the browser Back/Forward pattern above.
4. Deque — needs O(1) removal at both ends as the window slides forward.

Exercise 6 — build an undo feature. Design a TextEditor class with type(ch) and undo() methods, using a stack to hold history.

Answer

class TextEditor:
    def __init__(self) -> None:
        self.history: list[str] = []

    def type(self, ch: str) -> None:
        self.history.append(ch)

    def undo(self) -> None:
        if self.history:
            self.history.pop()

    def text(self) -> str:
        return "".join(self.history)

Each keystroke is a push, O(1); each undo is a pop, O(1). The whole feature is a direct application of LIFO.

Exercise 7 — validate balanced brackets. Write is_balanced(s) that returns True if every ()[]{} in s is matched and correctly nested.

Answer

def is_balanced(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

O(n) time, O(n) space. See Worked Example 3 above for a full trace.

Exercise 8 — build a queue from two stacks. Implement enqueue/dequeue using only two stacks (no other structure).

Answer

class QueueFromStacks:
    def __init__(self) -> None:
        self.in_s: list[int] = []
        self.out_s: list[int] = []

    def enqueue(self, x: int) -> None:
        self.in_s.append(x)

    def dequeue(self) -> int:
        if not self.out_s:
            while self.in_s:
                self.out_s.append(self.in_s.pop())
        return self.out_s.pop()

Every element crosses from in_s to out_s exactly once, so while a single dequeue can occasionally cost O(n), the cost amortized over n operations is O(1) per call.

Exercise 9 — bonus: reverse a string with a stack.

Answer

def reverse(s: str) -> str:
    stack = list(s)
    out: list[str] = []
    while stack:
        out.append(stack.pop())
    return "".join(out)

Pushing every character then popping them all naturally reverses the order — LIFO undoes the original FIFO order the characters arrived in.

AI Code Critique

The AI proposes this queue. At a glance it works correctly, but there is a hidden cost — find it.

class Queue:
    def __init__(self) -> None:
        self.items: list[int] = []

    def enqueue(self, x: int) -> None:
        self.items.append(x)      # O(1) — good

    def dequeue(self) -> int:
        return self.items.pop(0)  # ❓ what does this cost?

Question: what is the complexity of list.pop(0)? If there are n items, what does dequeuing all of them become?

Answer

list.pop(0) is O(n) because Python’s list is a contiguous array, and every remaining element must shift up to fill the gap at the front. So dequeuing all n items becomes O(n²) — dramatically slower as data grows, and the kind of bug that passes every unit test (correct output) while silently failing every performance test at scale.

Fix it with collections.deque, which is backed by a doubly linked list of blocks, so popleft() is O(1) — no shifting, just rewiring a pointer:

from collections import deque

class Queue:
    def __init__(self) -> None:
        self.items: deque[int] = deque()

    def enqueue(self, x: int) -> None:
        self.items.append(x)         # O(1)

    def dequeue(self) -> int:
        return self.items.popleft()  # O(1)

A good “judge” habit here: whenever an AI reaches for list and calls .pop(0), .insert(0, x), or slices from the front in a loop, ask what sits underneath that list — contiguous array, always — and whether the operation touches the front. If it does, collections.deque is almost always the fix.

🎮 Game Dev: Undo Stacks & Input/Turn Queues

A level editor’s undo/redo history is the same LIFO problem as the browser Back/Forward pattern above: the last edit you made is the first one you want to unwind. A fighting game’s input buffer or a turn-based game’s action queue is the FIFO mirror image — commands must fire in the order the player pressed them, and that “just use a list” naivety is exactly where the pop(0) trap from this lesson bites hardest, because input buffers are read every single frame.

Worked example — an undo stack for a level editor, and a deque-backed input queue.

class LevelEditor:
    """Placing tiles pushes onto a stack; undo pops the most recent one."""

    def __init__(self) -> None:
        self.tiles: list[str] = []
        self.undo_stack: list[str] = []
        self.redo_stack: list[str] = []

    def place(self, tile: str) -> None:
        self.tiles.append(tile)
        self.undo_stack.append(tile)   # push — O(1)
        self.redo_stack.clear()        # a new edit kills the redo history

    def undo(self) -> None:
        if not self.undo_stack:
            return
        tile = self.undo_stack.pop()   # LIFO — undo the *last* placement first
        self.tiles.remove(tile)
        self.redo_stack.append(tile)

    def redo(self) -> None:
        if not self.redo_stack:
            return
        tile = self.redo_stack.pop()
        self.tiles.append(tile)
        self.undo_stack.append(tile)

A plain list is the right tool here — every push and pop touches only the end, which is already O(1). Nothing to fix; the discipline of “only touch one end” is the whole reason it works.

The input buffer is a different story. A naive first draft:

class InputBuffer:
    """Naive: works, but re-checked every frame — where's the cost hiding?"""

    def __init__(self) -> None:
        self.queue: list[str] = []

    def press(self, action: str) -> None:
        self.queue.append(action)      # enqueue — O(1)

    def next_action(self) -> str | None:
        return self.queue.pop(0) if self.queue else None   # ❓ O(n)!

At 60 frames per second, this pop(0) shifts every remaining buffered input left by one slot, every frame, for as long as the buffer has contents — the exact O(n) trap from the AI Code Critique above, just moved into a hot loop. The scaled fix is the same one: swap to collections.deque.

from collections import deque

class InputBuffer:
    def __init__(self) -> None:
        self.queue: deque[str] = deque()

    def press(self, action: str) -> None:
        self.queue.append(action)          # enqueue — O(1)

    def next_action(self) -> str | None:
        return self.queue.popleft() if self.queue else None  # dequeue — O(1)

Input queue (FIFO) jump dash attack dequeue front → replay in order pressed

Figure: an undo stack pops its most recent change first (LIFO); an input queue replays buffered commands in the order they arrived (FIFO).

Not every game ordering is plain FIFO, though — a turn-based game where a faster character should always act first, regardless of when their turn was queued, needs a queue ordered by priority (speed stat) instead of arrival time. Try it below: it’s the same “who goes next” question, just with a different rule for what “next” means.

Exercises

Exercise G1 — stack or queue? For each feature, name stack or queue and justify in one sentence:

1. A crafting station that must finish items in the order the player queued them.
2. A “rewind” mechanic that lets the player step backward through their last few moves.
3. An NPC dialogue system that must show lines in the order they were triggered.
4. A level editor’s Ctrl+Z.

Answer

1. Queue — first requested, first crafted; FIFO fairness.
2. Stack — rewinding means undoing the most recent move first; LIFO.
3. Queue — dialogue lines must play in the order they were triggered, not reversed.
4. Stack — same reasoning as the level editor above; Ctrl+Z is a pop.

Exercise G2 — predict the undo/redo output.

ed = LevelEditor()
ed.place("torch")
ed.place("chest")
ed.undo()
ed.place("door")
ed.undo()
ed.redo()
print(ed.tiles)

Answer

Trace: place torch → [torch]; place chest → [torch, chest]; undo pops chest → [torch] (redo_stack = [chest]); place door → [torch, door], which clears redo_stack; undo pops door → [torch] (redo_stack = [door]); redo pops door back → [torch, door]. Final: ['torch', 'door'] — note that chest is gone for good, because placing door cleared the redo history that used to hold it.

Exercise G3 — why not just re-scan the whole history? A junior programmer suggests storing every editor action in a single list and, for undo, finding the last action by scanning from index 0 up to len(list) - 1. Why is a stack still the better framing even though list[-1] is already O(1) in Python?

Answer

list[-1] and list.pop() are indeed both O(1) in CPython — a plain list is a perfectly good stack when you only ever touch the end. The value of naming it a “stack” isn’t a performance fix here; it’s a correctness discipline: it forces you to never reach into the middle (e.g. “undo the 3rd-to-last action”) or you lose the guarantee that redo history stays consistent. The push/pop vocabulary is a contract, not just an optimization.

Exercise G4 — input buffer, deque vs. list. A rhythm game reads one buffered input per frame at 60 FPS, and the buffer can hold up to 200 queued inputs during a busy passage. Estimate the total shifting work list.pop(0) does over one second of buffered input compared to deque.popleft().

Answer

With list.pop(0), each dequeue shifts up to ~200 elements, and this happens up to 60 times a second — a worst case around 60 × 200 = 12,000 element shifts per second, growing quadratically with buffer size. deque.popleft() does the same 60 dequeues at O(1) each — a small, constant number of pointer rewires per second regardless of buffer size. The difference is invisible at 5 buffered inputs and very visible (dropped frames) at 200.

Challenge problems

Challenge 1 — combo-input recognizer. Build a fighting-game input buffer that remembers only the last 5 button presses and detects when they match a special-move sequence, e.g. ["down", "down-forward", "forward", "punch"].

Approach

Use collections.deque(maxlen=5) — appending past the limit automatically drops the oldest entry, so you never manually trim the buffer. After every append, compare the last len(sequence) entries (a slice of the deque cast to a list) against the target sequence:

from collections import deque

class ComboBuffer:
    def __init__(self, size: int = 5) -> None:
        self.buffer: deque[str] = deque(maxlen=size)

    def press(self, action: str) -> None:
        self.buffer.append(action)

    def matches(self, sequence: list[str]) -> bool:
        recent = list(self.buffer)[-len(sequence):]
        return recent == sequence

maxlen is the key idea: it turns the deque into a fixed-size sliding window with O(1) push and automatic eviction, instead of manually slicing a growing list every frame.

Challenge 2 — delayed action scheduling. A turn-based RPG needs “poison: 3 damage per turn, for 3 turns” and similar delayed/repeating effects. Design a system that, each turn, fires every effect whose timer has reached zero, using only queue-like structures.

Approach

Keep a queue of (turns_remaining, effect) pairs. Each turn: dequeue everything currently in the queue, decrement each timer, apply the effect, and re-enqueue anything with turns_remaining > 0:

from collections import deque

def process_turn(effects: deque[tuple[int, str]]) -> None:
    for _ in range(len(effects)):
        turns_left, effect = effects.popleft()
        apply_effect(effect)                 # e.g. deal poison damage
        if turns_left - 1 > 0:
            effects.append((turns_left - 1, effect))

This works because everything in the queue is checked every turn — fine for a handful of effects. If effects instead fired at different future turns (e.g. “cast a spell that lands in 5 turns” mixed with “poison ticks every turn”), scanning the whole queue every turn wastes work; you’d want a priority queue ordered by trigger turn instead, so you only ever look at the soonest one — the same idea as the speed-ordered turn queue above, just keyed by “when” instead of “how fast.”

Going deeper

• MIT 6.006 — Introduction to Algorithms (Lecture 2: data structures)
• Harvard CS50 — Data Structures (stacks, queues, linked lists)
• VisuAlgo — Linked List and Stack/Queue (interactive animations)
• CLRS — Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (4th ed.), Chapter 10: Elementary Data Structures — the canonical formal treatment of stacks, queues, and linked lists, including pointer-based implementations without a garbage collector.
• Sedgewick & Wayne — Algorithms (4th ed.), Section 1.3: Bags, Queues, and Stacks — clean Java implementations and a good discussion of linked-list vs. resizing-array trade-offs.
• Weiss — Data Structures and Algorithm Analysis, Chapter 3: Lists, Stacks, and Queues — careful treatment of singly/doubly/circularly linked lists and amortized analysis.
• Goodrich, Tamassia & Goldwasser — Data Structures and Algorithms in Python, Chapters 6–7: Stacks, Queues, and Deques; Linked Lists — Python-native implementations that map directly onto the code in this lesson.