Linked Lists, Stacks & Queues

These data structures test your ability to work with pointers and understand LIFO/FIFO ordering -- skills that come up in many interview problems.

Linked Lists

A linked list stores elements in nodes connected by pointers. Key differences from arrays:

Feature	Array	Linked List
Access by index	O(1)	O(n)
Insert at beginning	O(n)	O(1)
Insert at end	O(1)*	O(n) or O(1) with tail
Memory	Contiguous	Scattered
Cache performance	Better	Worse

Essential Linked List Patterns:

# Definition
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Pattern 1: Reverse a linked list
def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# Pattern 2: Fast/Slow pointers (Floyd's cycle detection)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Pattern 3: Find middle of linked list
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Interview Tip: The fast/slow pointer technique solves many linked list problems: cycle detection, finding the middle, finding the nth node from the end, and detecting intersection points.

Stacks (LIFO)

Stacks follow Last-In-First-Out ordering. They are essential for:

• Matching parentheses -- the classic interview question
• Monotonic stack -- next greater/smaller element
• Expression evaluation -- postfix, infix conversion
• DFS traversal -- iterative DFS uses a stack

# Valid parentheses (classic interview question)
def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

# Monotonic stack: next greater element
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []  # stores indices
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

Queues (FIFO)

Queues follow First-In-First-Out ordering. They are essential for:

• BFS traversal -- level-order tree traversal, shortest path
• Sliding window maximum -- using deque (double-ended queue)
• Task scheduling -- process ordering

from collections import deque

# BFS level-order traversal
def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

When to Use What

Problem Type	Data Structure	Example
Matching/nesting	Stack	Valid parentheses, HTML tags
Next greater/smaller	Monotonic Stack	Stock prices, temperatures
Level-by-level processing	Queue	Tree BFS, shortest path
Reverse order	Stack	Reverse string, undo operations
Cycle detection	Linked List + Fast/Slow	Linked list cycle, loop detection

---

Next, we'll explore trees and graphs -- the most complex data structures you'll face in interviews. :::