Data Structures: From a Shelf of Plates to a Map of Friends

Start with the simple question

Before data structure, look at the word data: it is just information, like numbers, names or messages.

A data structure is a way of arranging that information so that the thing you do most often is quick.

That is all it is. A kitchen is a good example:

• Spices go on a rack, so you grab any one instantly.
• Plates go in a stack, so you always take the top one.
• Customers wait in a line, so the first one is served first.

Same kitchen, three arrangements, three different jobs. Nobody argues about which is the best shelf. It depends on what you are doing.

How do we measure "quick"?

We don't use seconds, because a fast laptop would win every time. We ask: if the data grows, how much more work do I do? This is Big O.

I keep only that much in my head. The rest I look up when I need it.

1. Array: things side by side

An array stores items next to each other in memory, and each one has a number (an index) starting from 0.

Because they sit side by side, the computer can compute where item number 2 lives and jump right there. That is why reading is instant. But adding something in the middle means everything after it has to shift to make room.

nums = [10, 20, 30, 40, 50]
print(nums[2])   # 30, instantly
nums.append(60)  # adding at the end is cheap

2. Linked list: a treasure hunt

Here the items are not side by side. Each node holds its value plus a note saying where the next one is. Like a treasure hunt, you can only follow the clues one by one.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None   # the clue to the next node

Adding at the front is cheap, because you only change one clue. But to reach the 50th item you must walk through 49 nodes first.

3. Stack: a pile of plates

You add on top and you remove from the top. The last one in is the first one out (LIFO).

stack = []
stack.append("a")   # push
stack.append("b")
stack.pop()         # gives back "b"

You already use stacks every day. The undo button remembers your actions in a stack. Browser back does the same. Even your code uses one: when a function calls another function, the computer stacks them up and unwinds in reverse.

4. Queue: a line at the counter

Same idea as a stack, but fair. The first one in is the first one out (FIFO).

from collections import deque
queue = deque()
queue.append("a")     # enqueue at the back
queue.append("b")
queue.popleft()       # dequeue from the front, gives "a"

Print jobs, task schedulers and breadth-first search all use queues.

5. Hash table: a locker with a formula

This one felt like magic when I first learned it. You store key → value pairs. A function called a hash function turns the key into a slot number, so you never search. You compute where it is and go there.

ages = {"Ana": 30, "Bilal": 25}
print(ages["Bilal"])   # 25

What if two keys land on the same slot? That is a collision, and real hash tables have tricks to handle it (like keeping a small list in each slot). Still, on average lookup, insert and delete are all $O(1)$.

6. Tree: a family tree that keeps order

A tree has one root at the top and children below it. In a binary search tree the rule is simple: smaller goes left, bigger goes right.

To find 6, you start at 8. Six is smaller, so go left to 3. Six is bigger, so go right. Found it in three steps instead of checking everything. Each step throws away half the tree, which is where $O(\log n)$ comes from.

Trees show up in file folders, the HTML DOM, databases and autocomplete. A heap is a special tree that keeps the biggest (or smallest) item at the top, and it powers priority queues.

7. Graph: a map of connections

A graph is things (nodes) connected by lines (edges). Roads between cities, friends on a social app, links between web pages.

I wrote more about this in Graphs. Walking through a graph is done with BFS (level by level, using a queue), DFS (deep first, using a stack), and Dijkstra for the shortest weighted path. Notice that the earlier structures are helping build this one.

So which one do I pick?