A data structure decides what is quick and what is slow in your program. Pick the right one, and many classic problems (recursion, bracket matching, graph search, taking turns) all but solve themselves.
What a data structure is
A data structure is a way to store and organise data so a program can use it efficiently. It is not a language, a piece of hardware or an algorithm. An algorithm is a set of steps; a data structure is the shape of the data those steps work on.
The shape matters because it decides which operations are cheap. A Python list gives you any item by its index in one step, but inserting at the front means shifting every other item along. A linked list is the other way round: adding at the front is instant, but finding the 500th item means walking past the first 499.
So the useful question is rarely 'which structure is best?' It is 'which operations does this problem do most?' The rest of this page looks at three structures and the jobs they fit: stacks, queues and circular linked lists.
Stacks: last in, first out
A stack only lets you touch its top. You push an item onto the top and pop the top item off. The last item in is the first one out, which is why it is called LIFO. Both operations take the same short time however big the stack gets.
In Python, a plain list works as a stack: append pushes and pop pops, both at the end of the list.
stack = []
stack.append("a") # push
stack.append("b") # push
stack.pop() # "b", the last one inStacks fit any problem where the most recent unfinished thing must be dealt with first.
How recursion uses the call stack
Every time a function is called, the language pushes a frame onto the call stack: the function's arguments, its local variables and where to carry on when it returns. When the function returns, its frame is popped and the caller picks up where it left off.
Recursion is a function calling itself, so it relies on this completely. Take a factorial:
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)Calling factorial(3) pushes a frame for n = 3, which calls factorial(2) and pushes another, which pushes one for n = 1. That last call returns 1 straight away and its frame is popped. Then the n = 2 frame finishes with 2, and the n = 3 frame finishes with 6. The calls finish in the reverse order they started: last in, first out.
This is also why runaway recursion crashes. Each call adds a frame, and the stack has a limit. Forget the base case and the frames pile up until Python raises a RecursionError (its default limit is 1,000 frames) or another language reports a stack overflow.
Checking balanced brackets
A string like ([]) is balanced: every closing bracket matches the most recent opening bracket that is still open. 'Most recent' is the clue that a stack fits.
The rule is short. Read the text one character at a time. Push every opening bracket. For every closing bracket, pop the top of the stack and check it is the matching opener. At the end, the stack must be empty.
Here it is on a balanced string, then on one that fails:
Checking brackets with a stack
Step 1 of 7: The text is '([])'. The first bracket, '(', opens, so it is pushed.
In code:
PAIRS = {")": "(", "]": "[", "}": "{"}
def is_balanced(text):
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in PAIRS:
if not stack or stack.pop() != PAIRS[ch]:
return False
return not stackThere are three ways to fail, and the code catches each one: a closer with nothing open ()(), a closer that doesn't match the top ((]), and openers left over at the end (((). Code editors, compilers and JSON parsers all do a version of this check.
Queues: first in, first out
A queue is the opposite of a stack. Items join at the back (enqueue) and leave from the front (dequeue), so the first item in is the first one out: FIFO. It is a queue at a shop, and it is how printers, message queues and web servers keep jobs in arrival order.
In Python, use collections.deque for a queue rather than a list. deque.popleft() takes the front item in one step, while list.pop(0) has to shift every remaining item along.
Breadth-first search
Breadth-first search (BFS) visits a graph level by level: the start node, then all its neighbours, then all of theirs, and so on. That order is exactly what a queue gives you. Nodes found early are visited early, and nodes found later wait their turn at the back.
The loop takes a node from the front, visits it, and adds any neighbours not seen yet to the back. Here it is on a small graph where A links to B and C, B links to D, and C links to E:
Breadth-first search with a queue
Step 1 of 6: Start at A: mark it as seen and put it in the queue.
The same search in Python:
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return order
graph = {"A": ["B", "C"], "B": ["D"],
"C": ["E"], "D": [], "E": []}
print(bfs(graph, "A")) # ['A', 'B', 'C', 'D', 'E']Swap the queue for a stack and the same loop becomes a depth-first search: it follows one branch all the way down before backing up. Because BFS works outwards one level at a time, it finds the shortest path, in number of edges, in a graph where every edge counts the same. That is why it sits behind 'degrees of separation' features and maze solvers.
Linked lists and circular linked lists
A linked list stores each item in a node that holds the value and a pointer to the next node. The nodes can live anywhere in memory; the pointers keep them in order. The last node usually points to nothing, which marks the end.
In a circular linked list, the last node points back to the first. There is no end: keep following next and you go round and round.
class Node:
def __init__(self, name):
self.name = name
self.next = None
a, b, c = Node("editor"), Node("browser"), Node("music")
a.next, b.next, c.next = b, c, a # c links back to a
current = a
for _ in range(5):
print(current.name)
current = current.next
# editor, browser, music, editor, browserTaking turns on the CPU
A circle is the natural shape for anything that takes turns forever, and the classic example is sharing a CPU. In round-robin scheduling, each running program gets a short slice of CPU time, then the scheduler moves on to the next one, and after the last it comes back round to the first.
Keep the programs in a circular linked list and the scheduler only needs one pointer. Give the current program its slice, then step to next. There is no 'reached the end, jump back to the start' check, because the list has no end. A new program is linked in beside the current one, and a finished one is unlinked by pointing its neighbour past it, both without shifting anything else.
Turn-based games and playlists on repeat use the same idea. Round-robin is the textbook example, not a description of every modern operating system; real schedulers often weigh priorities too.
Common mistakes
- Mixing up LIFO and FIFO. If the newest item should go first (undo, nested calls, brackets), you want a stack. If the oldest should go first (jobs, BFS), you want a queue.
- Using a Python list as a queue.
list.pop(0)moves every other item along, so a long queue gets slow. Usecollections.deque. - Forgetting the empty checks. Popping an empty stack is an error, and a bracket checker that doesn't check the stack is empty at the end calls
((balanced. - Looping forever over a circular list. A plain
while current is not Nonenever stops, because nothing isNone. Stop when you get back to the node you started from. - Recursion with no base case. Every call adds a frame to the call stack until it overflows.
For more questions across data structures and algorithms, try the DSA Quiz.
Key takeaways
- A data structure is a way to store and organise data, and it decides which operations are cheap.
- A stack is last in, first out: it powers the call stack behind recursion and the classic balanced-bracket check.
- A queue is first in, first out: breadth-first search uses one to visit a graph level by level.
- A circular linked list has no end, which suits anything that takes turns, such as round-robin CPU scheduling.
