Linked Lists, Stacks, and Queues

Arrays store elements contiguously in memory. Linked lists scatter them across memory and connect them with pointers. Stacks and queues are abstract patterns built on top of both. Understanding all three opens up a large class of problems.

Linked Lists

A linked list is a sequence of nodes. Each node holds a value and a pointer (reference) to the next node. The last node points to None.

[3] → [7] → [1] → [9] → None

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

Because nodes are not contiguous, you cannot compute the address of element i directly. To reach the 5th node, you must follow 5 pointers from the head — O(n) access.

Key Operations

The crucial advantage: insertion and deletion given a pointer to the location are O(1), versus O(n) for arrays (which must shift elements).

Inserting at the Head

def prepend(self, val):
    node = Node(val)
    node.next = self.head
    self.head = node

Before: head → [3] → [7] → None After: head → [1] → [3] → [7] → None

One pointer reassignment. O(1).

Traversal

def traverse(self):
    current = self.head
    while current:
        print(current.val)
        current = current.next

O(n) — visits every node once.

Doubly Linked Lists

A doubly linked list adds a prev pointer to each node, enabling traversal in both directions and O(1) deletion without needing the predecessor (since you have a direct reference to it).

class DNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

Used in: LRU cache implementations, browser history (back/forward), Python's collections.deque.

When to Use Linked Lists

• You need O(1) insertions/deletions at the front or at known positions.
• You do not need random access by index.
• Implementing stacks, queues, or LRU caches.

Stacks

A stack is a Last In, First Out (LIFO) structure. Like a stack of plates — you add and remove from the top only.

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
pop()   → returns 3, stack is [1, 2]
peek()  → returns 2, stack unchanged

Implementation

Stacks are efficiently implemented with a Python list (append/pop at the end are O(1)):

class Stack:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)     # O(1) amortised

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()    # O(1)

    def peek(self):
        return self._data[-1]      # O(1)

    def is_empty(self):
        return len(self._data) == 0

Classic Stack Problems

Balanced parentheses:

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

Function call stack: every language runtime uses a stack to track function calls. When you call f() which calls g(), g's frame is pushed on top of f's. When g returns, its frame is popped.

Undo/redo: push actions onto a stack; pop to undo.

Queues

A queue is a First In, First Out (FIFO) structure. Like a line at a counter — the first person to join is the first to be served.

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
dequeue()  → returns 1, queue is [2, 3]

Implementation

Never implement a queue with a Python list and pop(0) — removing from the front of a list is O(n) because it shifts every element. Use collections.deque:

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)      # O(1) — adds to right

    def dequeue(self):
        if not self._data:
            raise IndexError("dequeue from empty queue")
        return self._data.popleft() # O(1) — removes from left

    def peek(self):
        return self._data[0]        # O(1)

    def is_empty(self):
        return len(self._data) == 0

collections.deque is implemented as a doubly linked list of fixed-size blocks — both ends are O(1).

Classic Queue Problems

BFS (Breadth-First Search): queues are the backbone of BFS for traversing trees and graphs level by level (covered in the next lesson).

Task scheduling: a queue naturally models processing jobs in the order they arrive.

Sliding window maximum: a monotonic deque (deque maintaining a decreasing order) solves this in O(n).

Stack vs Queue vs Array vs Linked List

*With tail pointer.

Key Takeaways

• Linked lists sacrifice O(1) index access for O(1) insertion and deletion at any known position.
• Doubly linked lists enable O(1) deletion without a predecessor reference.
• Stacks (LIFO) solve problems involving matched pairs, call tracking, and reversal.
• Queues (FIFO) solve problems involving ordered processing and BFS traversal.
• Use collections.deque for queues in Python — never use list pop(0), which is O(n).