Data Structures: Arrays to Queues

Prerequisite: Python from Scratch

Choosing the right data structure is one of the most consequential decisions you make when writing code. A poor choice can turn a fast program into a slow one, or make clean logic look tangled. This post walks through the foundational linear data structures - arrays, linked lists, stacks, and queues - and shows when each one earns its place.

Why Data Structure Choice Matters

Every data structure makes a trade-off. It gives you fast access to some operations at the cost of making others slower. Understanding these trade-offs is what separates a programmer who can write code from one who can write good code.

The two resources we care about most are time (how many operations does this take?) and memory (how much space does this consume?). We describe time cost using Big-O notation: $O(1)$ is constant time (instant regardless of size), $O(n)$ scales with input size, $O(\log n)$ is in between.

Arrays and Lists

A Python list is backed by a contiguous block of memory. Every element sits next to the next one. This gives you:

• $O(1)$ random access - my_list[42] is instant because Python can compute the memory address directly from the index.
• $O(1)$ append - adding to the end is cheap (amortised).
• $O(n)$ insert or delete at the front - everything after the insertion point must shift.

fruits = ["apple", "banana", "cherry"]
print(fruits[1])      # O(1) - "banana"
fruits.insert(0, "avocado")  # O(n) - shifts all elements right

Lists shine when you access elements by index often and modify the end of the list, not the front.

Linked Lists

A linked list stores data in nodes, where each node holds a value and a pointer to the next node. There is no contiguous memory block.

• $O(1)$ insert or delete at the head - just update a pointer.
• $O(n)$ access by index - you must walk from the beginning.

Python has no built-in linked list, but collections.deque is implemented as a doubly-linked list and is the practical tool you reach for when you need efficient front insertions. Linked lists beat arrays when you are constantly inserting or removing at the front or the middle and never need random access.

Stacks

A stack follows LIFO (Last In, First Out): the last item pushed is the first one popped. Think of a stack of plates - you can only add or remove from the top.

Python lists work perfectly as stacks:

stack = []
stack.append("first")
stack.append("second")
stack.append("third")

top = stack.pop()   # "third"
print(top)

Both .append() and .pop() are $O(1)$. The call stack in your program is literally this: when you call a function, its frame is pushed; when it returns, it is popped. Recursive functions can overflow the stack if they go too deep.

Queues

A queue follows FIFO (First In, First Out): the first item enqueued is the first one dequeued. Think of a line at a coffee shop.

Do not use a plain list as a queue. Removing from the front (list.pop(0)) is $O(n)$ because every element shifts. Use collections.deque instead:

from collections import deque

queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")

front = queue.popleft()   # O(1) - "first"
print(front)

deque supports $O(1)$ appends and pops from both ends, making it a double-ended queue (deque). You can use it as a stack, a queue, or slide a window across data efficiently.

Priority Queues and heapq

Sometimes the “first out” item should be the one with the highest priority, not the one that arrived earliest. That is a priority queue, and Python provides it through heapq, which implements a min-heap.

In a min-heap, the smallest element is always at the top. heapq.heappush and heapq.heappop both run in $O(\log n)$.

import heapq

tasks = []
heapq.heappush(tasks, (3, "low priority task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (2, "normal task"))

priority, task = heapq.heappop(tasks)
print(task)   # "urgent task" - lowest number = highest priority

Use priority queues for task scheduling, Dijkstra’s shortest path, and anywhere you need the “smallest” or “most important” item quickly.

Useful Collections

Two more tools from the collections module are worth knowing:

from collections import defaultdict, Counter

# defaultdict: never raises KeyError for missing keys
word_lists = defaultdict(list)
word_lists["fruits"].append("apple")   # no need to initialise the list first

# Counter: count occurrences in one line
text = "mississippi"
counts = Counter(text)
print(counts.most_common(2))   # [('s', 4), ('i', 4)]

Examples

Balanced Parentheses Checker

This classic problem uses a stack: push every opening bracket, and pop when you see a closing bracket. If the popped bracket does not match, the string is invalid.

def is_balanced(s: str) -> bool:
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}

    for char in s:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return len(stack) == 0

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

BFS Using a Queue

Breadth-first search explores a graph level by level. The queue guarantees that you visit all neighbours at distance 1 before distance 2.

from collections import deque

def bfs(graph: dict, start: str) -> list:
    visited = set()
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in graph.get(node, []):
            queue.append(neighbour)

    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D']

Choosing the Right Structure

Start with the simplest structure that fits your access pattern, and only reach for a more complex one when you have a clear reason.

Read Next: Trees, Heaps, and Hierarchical Data