Arrays, Lists, Stacks & Queues

Before you can understand data structures, you need a mental model of computer memory. RAM (Random Access Memory) is physically organized as a single, enormous, flat array of bytes. Each byte has a numeric address — an integer from 0 up to the memory limit of your machine. When your program declares a variable, the OS assigns it an address. When you read or write that variable, the CPU sends that address to the memory controller and gets back (or sends) bytes.

The key physical fact is this: reading any address takes the same time. Whether you read address 4 or address 4,000,000,000, the latency is the same (ignoring cache effects for now). This is why it's called random access — "random" in the sense of arbitrary, not unpredictable. You can jump to any location in O(1) time.

This flat-array model has one critical implication: if you know where something is (its address), you can get to it instantly. This is the foundation of O(1) array indexing. If array A starts at address base and each element occupies size bytes, then element A[i] lives at address base + i * size. No searching required — pure arithmetic.

The corollary is equally important: things that are adjacent in memory (contiguous) play well with hardware caches. Modern CPUs load memory in cache lines of 64 bytes. If you read A[0], the hardware speculatively fetches A[1] through A[7] (for 8-byte elements) into cache. Traversing a contiguous array is therefore much faster in practice than the O(n) analysis suggests, because cache misses are rare. This spatial locality advantage of arrays over linked lists is one of the most important practical considerations in systems programming.

# Demonstrating the address arithmetic behind array indexing
import ctypes

A = [10, 20, 30, 40, 50]  # Python list (dynamic array under the hood)

# In C/C++, array indexing is literally:
#   A[i]  ==  *(base_ptr + i)
# which the compiler translates to:
#   load from address (base + i * sizeof(element))

# In C:
# int A[] = {10, 20, 30, 40, 50};
# printf("%d\n", A[3]);    // reads address of A + 3*4 bytes = A+12
# printf("%d\n", *(A+3)); // identical — pointer arithmetic

A static array allocates a fixed, contiguous block of memory at creation time. Once created, its size cannot change. This is the most primitive data structure, and it maps directly onto hardware.

Operations and their complexities:

• Access A[i]: O(1) — pure address arithmetic.
• Search (unsorted): O(n) — must examine every element in the worst case.
• Search (sorted): O(log n) — binary search exploits contiguity.
• Insert at position i: O(n) — all elements from i to end must shift right by one.
• Delete at position i: O(n) — all elements from i+1 to end must shift left.
• Insert/delete at end: O(1) — no shifting needed.

The insert/delete cost is the fundamental limitation of arrays. Because the elements must stay contiguous, any insertion in the middle requires physically moving data. If you insert at position 0 (the front), you move every element — O(n) moves.

Why does this matter? If your workload is read-heavy (lots of indexing, sorting, binary search), arrays are nearly optimal. If you need frequent insertions and deletions in the middle, you'll suffer. This trade-off motivates the linked list.

A subtler point: arrays have a fixed capacity. If you fill a static array and need one more slot, you're stuck. This limitation motivates the dynamic array (next concept).

// Static array in C — size fixed at compile time
#include <stdio.h>

void shift_insert(int A[], int n, int pos, int val) {
    // Insert val at index pos; n is current count, array has n+1 capacity
    // Shift elements right — O(n) in the worst case
    for (int i = n; i > pos; i--) {
        A[i] = A[i - 1];
    }
    A[pos] = val;
}

int main() {
    int A[6] = {10, 20, 30, 40, 50};  // static: size 6, 5 used
    int n = 5;
    shift_insert(A, n, 2, 99);  // insert 99 at index 2
    // A is now {10, 20, 99, 30, 40, 50}
    for (int i = 0; i <= n; i++) printf("%d ", A[i]);
    // Output: 10 20 99 30 40 50
}

A dynamic array (called vector in C++, ArrayList in Java, list in Python) solves the fixed-size problem by allocating extra capacity and growing when full. The key insight is the growth strategy.

Naive growth: when full, allocate one more slot. Copy everything. Cost of n appends: 1 + 2 + 3 + ... + n = O(n²). Terrible.

Doubling strategy: when full, allocate a new array of twice the current size. Copy everything. The key insight: after doubling to size 2k, you can perform k appends before the next copy. The copy cost k is spread over k future operations — just 1 unit of cost per append.

Amortized analysis (the accounting argument): Charge each element $3$ units when it is first written:

• 1 unit: pay for the current write.
• 2 units: save in a "bank" for the future copy.

When the array doubles from size k to 2k, all k elements are copied. But each element has 2 banked units — exactly enough to pay for the copy. So every append costs O(1) amortized, even though occasional appends cost O(n) actual time.

More formally, using the potential method: define potential Φ = 2·(size) − capacity. Each push maintains this potential; the amortized cost per push is O(1).

Practical implications:

• Python list.append() is O(1) amortized — this is why you can append in a loop without worrying.
• C++ std::vector::push_back() guarantees O(1) amortized.
• Deletion from the end (pop) is always O(1) actual.
• Access and modification are always O(1) actual.
• Insertion/deletion in the middle is still O(n) — dynamic arrays do not solve the shifting problem.

Load factor and shrinking: most implementations also shrink when the array is less than 25% full (halving capacity), to avoid wasting memory.

class DynamicArray:
    """A minimal dynamic array with amortized O(1) append."""
    def __init__(self):
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity  # internal fixed array

    def append(self, val):
        if self._size == self._capacity:
            self._resize(2 * self._capacity)  # double when full
        self._data[self._size] = val
        self._size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self._size):        # O(n) copy, but amortized O(1)
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_cap

    def __getitem__(self, i):              # O(1) access
        if not 0 <= i < self._size:
            raise IndexError("out of range")
        return self._data[i]

    def __len__(self):
        return self._size

# Demonstration
arr = DynamicArray()
for x in range(10):
    arr.append(x)
    print(f"size={len(arr)}, cap={arr._capacity}")
# Capacity sequence: 1→2→4→8→16 (doubles at each overflow)

A singly linked list stores elements as a chain of nodes, where each node holds a value and a pointer to the next node. There is no requirement that nodes be contiguous in memory — each one is allocated independently, wherever the allocator finds space.

Structure:

head → [val|next] → [val|next] → [val|next] → None

Why linked lists exist: the array's fundamental problem is that inserting or deleting in the middle requires shifting elements. In a linked list, inserting between nodes A and B only requires changing two pointers. No elements move. This is O(1) given a pointer to the insertion point.

Operations:

• Prepend (insert at head): O(1) — create a new node, point it to current head, update head.
• Append (insert at tail): O(n) if we only track head; O(1) if we also track a tail pointer.
• Search for value: O(n) — must traverse from head.
• Access by index i: O(n) — no address arithmetic possible; must follow pointers.
• Insert/delete given a pointer to predecessor: O(1) — just rewire two pointers.
• Delete head: O(1).

The critical trade-off: linked lists sacrifice O(1) random access in exchange for O(1) pointer-based insertion/deletion. If you have a pointer to where you want to insert, the operation is O(1). But finding that position still costs O(n) search.

Memory overhead: each node stores a pointer in addition to the value. For small values (e.g., a 4-byte int), the pointer (8 bytes on 64-bit systems) more than doubles the memory per element. Worse, nodes scattered throughout the heap destroy spatial locality — traversing a linked list causes a cache miss at nearly every step, making it 10-100× slower in practice than array traversal even for the same O(n) algorithmic complexity.

When to use a linked list:

• When you have a pointer to an arbitrary position and need O(1) insert/delete there (e.g., an LRU cache combined with a hash map).
• When element count is highly variable and you cannot predict the size.
• When elements are large (so pointer overhead is proportionally small).

class Node:
    __slots__ = ['val', 'next']  # memory-efficient
    def __init__(self, val):
        self.val = val
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def prepend(self, val):           # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def append(self, val):            # O(1) with tail pointer
        node = Node(val)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self.size += 1

    def delete_head(self):            # O(1)
        if not self.head:
            raise IndexError("empty")
        val = self.head.val
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return val

    def insert_after(self, node, val):  # O(1) given the node
        new_node = Node(val)
        new_node.next = node.next
        node.next = new_node
        if node is self.tail:
            self.tail = new_node
        self.size += 1

A doubly linked list extends each node with a prev pointer in addition to next. This seemingly small change unlocks several important capabilities:

1. O(1) delete given only the node itself — in a singly linked list, to delete a node you need its predecessor (to update prev.next). In a doubly linked list, the node already knows its predecessor via prev. So deletion of an arbitrary node is O(1) with no need to traverse.

2. Bidirectional traversal — you can iterate forward or backward, enabling efficient access to the tail without a separate pointer.

3. O(1) insert before a node — symmetric to insert_after.

The sentinel/dummy node pattern: real implementations (e.g., Python's collections.deque, the Linux kernel's list_head) almost universally use a dummy "sentinel" node at both ends (or a single circular sentinel). This eliminates special cases for empty lists and head/tail operations, making the code much cleaner and less bug-prone:

  sentinel ⇔ node1 ⇔ node2 ⇔ ... ⇔ nodeN ⇔ sentinel (circular)

Memory cost: each node now carries two pointers instead of one. For an 8-byte value with 8-byte pointers, each node is 24 bytes — the value is only 33% of the memory used.

Real-world usage: the Linux kernel uses a circular doubly linked list (struct list_head) as its universal list primitive — embedded directly inside larger structs using the container_of macro. Python's collections.deque is a doubly linked list of fixed-size arrays (a 'deque of arrays' hybrid for better cache performance). LRU caches in operating systems and language runtimes use doubly linked lists combined with hash maps.

class DNode:
    __slots__ = ['val', 'prev', 'next']
    def __init__(self, val=None):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    """Circular sentinel-based doubly linked list."""
    def __init__(self):
        self._sentinel = DNode()           # dummy node; never holds real data
        self._sentinel.next = self._sentinel
        self._sentinel.prev = self._sentinel
        self.size = 0

    def _insert_between(self, val, before, after):  # O(1)
        node = DNode(val)
        node.prev = before
        node.next = after
        before.next = node
        after.prev = node
        self.size += 1
        return node

    def append(self, val):   # insert before sentinel = append to back
        return self._insert_between(val, self._sentinel.prev, self._sentinel)

    def prepend(self, val):  # insert after sentinel = prepend to front
        return self._insert_between(val, self._sentinel, self._sentinel.next)

    def delete(self, node):              # O(1) — no search needed!
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None     # help GC
        self.size -= 1

    def move_to_front(self, node):       # O(1) — key for LRU cache
        self.delete(node)
        self.prepend(node.val)  # re-insert at front

A stack is an abstract data type (ADT) defined by its interface, not its implementation: elements are added and removed from only one end, called the top. The ordering discipline is LIFO — Last In, First Out. Think of a stack of cafeteria trays: you always take from the top, and always add to the top.

Core operations:

• push(x): add x to the top. O(1).
• pop(): remove and return the top element. O(1). Error if empty.
• peek() / top(): return the top element without removing. O(1).
• is_empty(): return true if size is 0. O(1).

Implementation: stacks can be implemented with either a dynamic array or a linked list. The array implementation is almost always preferred in practice because of better cache performance and lower overhead. Push = array.append(); pop = array.pop() — both O(1) amortized.

Why stacks are everywhere:

1. Function call stack: the CPU maintains a stack of stack frames, one per active function call. Each frame stores local variables, return address, and saved registers. When you call f(), its frame is pushed; when f returns, its frame is popped and control resumes at the saved return address. Recursion is literally a stack at the hardware level.

2. Expression evaluation: to evaluate 3 * (4 + 5), a compiler pushes operands and pops when it encounters an operator. This underpins every expression parser ever written.

3. Balanced parentheses / bracket matching: push open brackets; when you see a close bracket, pop and check if it matches. O(n) time, O(n) space.

4. DFS (Depth-First Search): an iterative DFS replaces recursion with an explicit stack.

5. Undo/redo: every text editor maintains an undo stack. Each edit is an operation pushed onto it; undo pops and reverses.

# Stack implementation using Python's dynamic array (list)
class Stack:
    def __init__(self):
        self._data = []

    def push(self, x):          # O(1) amortized
        self._data.append(x)

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

    def peek(self):             # O(1)
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._data[-1]

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

    def __len__(self):
        return len(self._data)

# Classic application: balanced parentheses checker
def is_balanced(s: str) -> bool:
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.push(ch)
        elif ch in ')]}':
            if stack.is_empty() or stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()

print(is_balanced("({[]})"))   # True
print(is_balanced("({[}])"))   # False

A queue is an ADT where elements are added at one end (the back or rear) and removed from the other end (the front). The ordering discipline is FIFO — First In, First Out. Think of a checkout line: the first customer to arrive is the first to be served.

Core operations:

• enqueue(x) / push(x): add x to the back. O(1).
• dequeue() / pop(): remove and return the front element. O(1). Error if empty.
• peek(): return the front element without removing. O(1).
• is_empty(): return true if size is 0. O(1).

Naive array implementation problem: if you implement a queue with a plain array using append() for enqueue and pop(0) for dequeue, the dequeue is O(n) because it shifts every element left. This is terrible.

Circular buffer (ring buffer): the standard O(1) array-based queue uses two indices, front and back, into a fixed-size array, wrapping around with modular arithmetic. When back reaches the end of the array, it wraps to 0. This gives O(1) enqueue and dequeue with no shifting. Used in OS kernel ring buffers, audio drivers, and network packet queues.

Linked list implementation: a linked list with both head and tail pointers gives O(1) enqueue (append to tail) and O(1) dequeue (remove from head). Python's collections.deque uses this approach (with blocked chunks for cache efficiency).

Why queues matter:

1. BFS (Breadth-First Search): the queue disciplines the order of exploration — level by level.
2. OS process scheduling: the ready queue holds processes waiting for CPU time.
3. Network buffers: packets are queued at routers when the link is busy.
4. Producer-consumer systems: one thread produces work items; another consumes them via a shared queue (with appropriate synchronization).

from collections import deque

class Queue:
    """FIFO queue backed by Python's deque (doubly linked list of arrays)."""
    def __init__(self):
        self._data = deque()  # O(1) appendleft AND pop

    def enqueue(self, x):     # O(1) — add to back
        self._data.append(x)

    def dequeue(self):        # O(1) — remove from front
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

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

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

# Circular buffer queue in pure Python (fixed capacity)
class CircularQueue:
    def __init__(self, capacity):
        self._buf = [None] * capacity
        self._cap = capacity
        self._front = 0
        self._size = 0

    def enqueue(self, x):                        # O(1)
        if self._size == self._cap:
            raise OverflowError("queue is full")
        back = (self._front + self._size) % self._cap
        self._buf[back] = x
        self._size += 1

    def dequeue(self):                           # O(1), no shifting!
        if self._size == 0:
            raise IndexError("queue is empty")
        val = self._buf[self._front]
        self._front = (self._front + 1) % self._cap
        self._size -= 1
        return val

A deque (pronounced "deck", short for double-ended queue) supports O(1) insertion and deletion at both ends. It generalizes both stacks and queues: a stack is a deque where you only use one end; a queue is a deque where you enqueue at one end and dequeue at the other.

Operations (all O(1) amortized):

• push_front(x) / append_left(x)
• push_back(x) / append(x)
• pop_front()
• pop_back()
• peek_front(), peek_back()

Implementation: a doubly linked list trivially supports O(1) operations at both ends. The more cache-friendly implementation (used by std::deque in C++ and Python's collections.deque) is a deque of arrays (also called a segmented array or unrolled linked list): elements are stored in fixed-size arrays ("chunks"), and the chunks are linked together. This gives both O(1) amortized push/pop at both ends AND better cache performance than a pure linked list.

Python's collections.deque uses this approach with a block size of 64 elements per chunk. It is the go-to data structure when you need a queue in Python — never use a plain list with pop(0).

Applications:

1. Sliding window algorithms: maintain a deque of indices for the maximum in a sliding window of size k — a crucial technique in competitive programming.
2. Work-stealing schedulers: each thread has a deque of tasks; it pushes/pops from its own deque, and idle threads steal from the front of others' deques.
3. Palindrome checking: push all characters, then simultaneously pop from both ends and compare.
4. Implementing undo with bounded history: maintain a deque of bounded length; push new states at back, pop old states from front when over limit.

from collections import deque

# Sliding window maximum — O(n) using a deque
def sliding_window_max(nums, k):
    """
    Return max of each window of size k.
    Deque stores indices; front always holds index of current window max.
    Invariant: deque is decreasing (by value). We discard smaller elements
    eagerly because they can never be the maximum of a future window.
    """
    dq = deque()   # stores indices, not values
    result = []

    for i, x in enumerate(nums):
        # Remove indices no longer in window
        while dq and dq[0] < i - k + 1:
            dq.popleft()              # O(1)

        # Maintain decreasing invariant: discard all smaller elements
        while dq and nums[dq[-1]] < x:
            dq.pop()                  # O(1)

        dq.append(i)                  # O(1)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example:
print(sliding_window_max([1,3,-1,-3,5,3,6,7], k=3))
# Output: [3, 3, 5, 5, 6, 7]

Understanding why each complexity is what it is is more important than memorizing a table. Here is the full picture:

*if capacity not exceeded. **with tail pointer. ***given pointer to predecessor. ****need to find predecessor. *****given direct pointer to node.

The two big trade-offs:

1. Array: O(1) index access vs. O(n) middle insert/delete. Contiguous memory enables arithmetic addressing. But contiguity requires shifting on insertion.

2. Linked list: O(1) pointer-based insert/delete vs. O(n) index access. Flexibility of scattered allocation eliminates shifting. But no address arithmetic, no random access.

Practical rule of thumb:

• Read/search-heavy, rarely modified → Array or sorted array with binary search.
• Frequent insert/delete at arbitrary positions with direct pointers → Doubly linked list.
• Frequent insert/delete at ends only → Deque (circular buffer or collections.deque).
• The 'LRU cache' pattern → Hash map + doubly linked list (O(1) for everything).

Cache matters: in practice, arrays often outperform linked lists even on operations where linked lists have better asymptotic complexity, because cache miss penalties (~100 cycles) dominate the cost of O(n) pointer traversals in linked lists.