Handbooks / Data Structures & Algorithms / Chapter 2

Linked Lists, Stacks and Queues

7 pages · ~5 min✓ Reviewed

Builds on Arrays and Hashing. Next up: Sorting and Searching.

Data Structures & AlgorithmsPage 1

Linear Structures: The Mental Model

1. Singly vs doubly linked

Singly: node = value + next; only head is known
Index access walks from head: O(n)
Doubly: node adds prev, one extra pointer per node

	Singly	Doubly
Delete given node	O(n)	O(1)
Remove tail	O(n)	O(1)

2. Stack, queue, deque

Type	Order	Operations
Stack	LIFO	push / pop / peek, one end
Queue	FIFO	enqueue back, dequeue front
Deque	both ends	O(1) at both ends

3. Array vs list

Array: O(1) index, cache-friendly scans
List: O(1) insert/delete once you hold the node

Why is doubly delete O(1)? prev reaches the predecessor; singly must scan from head
List over dynamic array? Many inserts/deletes at held nodes, no index access needed

Remember

Index = array. Splice = list.

Data Structures & AlgorithmsPage 2

Linked List Operations and Costs

1. Costs

Operation	Cost
Insert at head	O(1)
Insert at tail, with tail pointer	O(1)
Insert at tail, no tail pointer	O(n)
Search by value	O(n)
Delete by value	O(n) find, O(1) unlink

2. Traverse and unlink

cur = head; while cur: cur = cur.next
Keep prev to unlink: prev.next = cur.next
A dummy head removes the first-node special case

python

dummy = Node(0, head)
prev, cur = dummy, head
while cur and cur.val != v:
    prev, cur = cur, cur.next
if cur: prev.next = cur.next
head = dummy.next

fragment: delete first node with value v

3. Reverse in place

Loop while cur

1Savenxt = cur.next
2Flipcur.next = prev
3Advance prevprev = cur
4Advance curcur = nxt

O(n) time, O(1) space

Flip cur.next before saving nxt and the rest of the list is lost. Return prev.

Reverse in place? Save nxt, flip next, advance prev and cur.
Why a dummy head? Head changes need no special case.
Append without tail pointer? O(n) walk to the end.

Data Structures & AlgorithmsPage 3

Stacks and Queues in Practice

1. Stack and Queue in Python

	Add	Remove	Peek	Cost
Stack (`list`)	`append`	`pop`	`[-1]`	O(1) amortized
Queue (`deque`)	`append`	`popleft`	`[0]`	O(1)
Deque	`append` `appendleft`	`pop` `popleft`	both ends	O(1) all four

Stack = list; queue = deque
Deque supports sliding-window maximum

python

stack = []
stack.append(1)  # push
stack[-1]  # peek
stack.pop()  # pop
from collections import deque
q = deque()
q.append(1)  # enqueue
q.popleft()  # dequeue

2. Where They Fit

Stack (LIFO)	Queue (FIFO)
Balanced brackets	BFS
Undo	Task scheduling
DFS	Buffering
Expression evaluation	Sliding window (deque)

3. Interview Point

Queue from two stacks? Push to in; when out is empty, pour in into it, pop from out
Amortized cost? Each item moves once: O(1) per op
Why not list.pop(0)? Shifts all items: O(n)
BFS vs DFS? BFS queue, DFS stack

Mistake

pop() or [-1] on an empty stack raises IndexError: check first.

Data Structures & AlgorithmsPage 4

Monotonic Stack

1. The Idea

Stack kept in sorted order, increasing or decreasing
Per element: pop while the top violates the order, then push
Decreasing stack of indices gives the next greater element

2. Next Greater Element

python

a = [2, 1, 5, 3]
ans, st = [-1] * len(a), []
for i, x in enumerate(a):
    while st and x > a[st[-1]]:
        ans[st.pop()] = x
    st.append(i)
print(ans)

a[i] > a[top]: pop, answer[top] = a[i]

output

[5, 5, -1, -1]

3. Cost and Indices

Need	Store	Example
Value only	value or index	next greater
Distance	index	daily temperatures
Width	index	largest rectangle

Each element is pushed once and popped once
So the pass is O(n) despite the inner while

Why is the nested while O(n)? Total pops are at most n pushes
Values or indices? Indices when you need distance or width
Next smaller? Flip to x < a[top], keep an increasing stack

Data Structures & AlgorithmsPage 5

Fast and Slow Pointers

1. Floyd's Cycle Detection

slow moves 1 step, fast moves 2 per iteration
O(n) time, O(1) space
slow == fast → cycle exists
fast or fast.next is None → no cycle

python

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast: return True
    return False

2. Middle and Cycle Start

When fast hits the end, slow is the middle
Even length: slow lands on the second middle

Meetslow == fast
Resetone pointer to head
Step both1 step each
Entrancethey meet here

Loop condition

Use while fast and fast.next, else fast.next.next raises a null error.

3. Interview Point

Why must they meet? The gap shrinks by 1 each step inside the cycle, so it reaches 0
Cycle start? Reset one pointer to head, move both 1 step; they meet at the entrance
First middle of an even list? Loop while fast.next and fast.next.next

Data Structures & AlgorithmsPage 6

Cheat Sheet: Lists, Stacks, Queues

1. Costs and Containers

Operation	Cost
Array index	O(1)
List index	O(n)
List head insert	O(1)
Doubly delete given node	O(1)
Deque both ends	O(1)

Stack = list append / pop
Queue = deque append / popleft
Never list.pop(0): O(n) shift

2. List and Stack Patterns

Dummy head removes first-node special cases
Keep a prev pointer when unlinking
Save next before rewiring
Keep a tail pointer for O(1) append

Monotonic stack: store indices, pop while violated
Each element pushed and popped once: O(n)
Decreasing stack gives next greater

while fast and fast.nextfast 2, slow 1
Meetcycle exists
Reset oneto head
Step both by 1meet at entrance

3. Marks Lost

Overwriting cur.next first loses the rest of the list
Checking only fast, not fast.next, before fast.next.next
pop() or stack[-1] on an empty stack: check first

Unlink order

Save next, then rewire, then advance.

Data Structures & AlgorithmsPage 7

Check yourself

A reversal loop runs cur.next = prev before nxt = cur.next. What is returned for 1→2→3?

nxt reads the already-overwritten next, so it is None
The loop stops after one node
Returns node 1 alone; 2 and 3 are lost

With while fast and fast.next, where does slow stop on 1→2→3→4?

Node 3, the second middle
fast goes 1, 3, None while slow goes 1, 2, 3

Next greater element on [2,1,3] with a decreasing index stack: what is the answer array?

[3, 3, -1]
3 pops index 1, then index 0
Index 2 never pops, so it stays -1

Why is q.pop(0) a poor dequeue, and what replaces it?

It shifts every remaining element, so O(n)
Use deque.popleft(), which is O(1)