Data Structures Introduction

What is a data structure?#

A data structure is simply a way of organizing data in memory so that it can be used efficiently. That's it — no more mysterious than that. An array, a list, a stack of plates, a phone book sorted alphabetically — these are all ways of arranging information so that specific operations (finding something, adding something, removing something) are fast, or at least predictable.

Here's the key insight this entire course is built on: the same data, organized differently, can make the same operation take wildly different amounts of time. Choosing the right data structure for the job you actually need to do is one of the highest-leverage skills in programming — it's frequently the difference between code that runs instantly and code that grinds to a halt as your input grows.

A concrete example: why the "container" you pick matters#

Suppose you have a list of one million user IDs, and you need to repeatedly check "is this ID in our system?" Let's compare two ways of storing that data.

Option 1: a plain list. To check whether an ID exists, you have to look at every single element until you either find it or reach the end.

user_ids = list(range(1_000_000))  # a plain Python list

def exists_in_list(target, ids):
    for uid in ids:
        if uid == target:
            return True
    return False

exists_in_list(999_999, user_ids)  # has to check nearly all 1,000,000 entries

Option 2: a set (Python's hash-table-backed structure). The same check becomes almost instant, regardless of how large the collection is.

user_ids_set = set(range(1_000_000))  # a Python set — built on a hash table

def exists_in_set(target, ids):
    return target in ids  # a hash table computes roughly where to look directly

exists_in_set(999_999, user_ids_set)  # checks essentially one location, not a million

Both functions return the same correct answer. But exists_in_list might have to inspect up to a million elements one by one, while exists_in_set computes a location mathematically and jumps straight there. If you called this check a thousand times in a row, the list version could take genuinely noticeable time — seconds — while the set version would still feel instantaneous. Same data. Same question. Wildly different performance. The only thing that changed was the data structure. This is the whole point of studying data structures: learning to recognize which structure turns a slow operation into a fast one.

Big-O notation: a language for talking about "how fast"#

To compare data structures and algorithms precisely (instead of just saying "this one feels faster"), computer scientists use Big-O notation. Big-O describes how the number of steps an operation takes grows as the input size (conventionally called n) grows — not the exact time in seconds (which depends on your CPU, your language, a dozen other factors), but the shape of how work scales up.

Don't worry about formal mathematical definitions yet — what matters at this stage is building an intuition for the handful of growth rates you'll see constantly. Here they are, from fastest to slowest, each with a real-world analogy and a tiny code example.

O(1) — Constant time#

The operation takes the same amount of time no matter how big the input is. One step, always.

Analogy: Looking up a word in a dictionary when you already know the exact page number. Doesn't matter if the dictionary has 100 pages or 100,000 — you flip straight to the page.

def get_first_element(items):
    return items[0]  # always exactly one step, regardless of len(items)

O(log n) — Logarithmic time#

The operation gets slightly slower as input grows, but incredibly slowly — doubling the input adds only one extra step. This shows up whenever an algorithm can throw away half the remaining possibilities at each step.

Analogy: Looking up a name in a phone book by repeatedly flipping to the middle and deciding "is my name before or after this page?" — each flip eliminates half of what's left. Finding a name among a billion entries this way takes only about 30 flips.

def binary_search(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # each loop iteration cuts the search space in half

O(n) — Linear time#

The operation's steps grow directly in proportion to the input size. Double the input, double the work.

Analogy: Reading every page of a book to find one specific sentence — no shortcuts, you check each page once.

def find_max(items):
    current_max = items[0]
    for item in items:          # one pass over every element
        if item > current_max:
            current_max = item
    return current_max

O(n log n) — "Linearithmic" time#

A very common and very good growth rate for anything that has to look at every element (that's the n) but also does something logarithmic along the way (that's the log n) — most notably, efficient sorting.

Analogy: Sorting a huge stack of exam papers by repeatedly splitting the stack in half, sorting each half, then merging the sorted halves back together — you touch every paper (n), but the "splitting in half" structure (log n) keeps the total work far below checking every paper against every other paper.

sorted_items = sorted([5, 3, 8, 1, 9, 2])  # Python's built-in sort runs in O(n log n)

O(n²) — Quadratic time#

The steps grow proportional to the square of the input size — for every element, you do roughly n more work. This is the classic "nested loop over the same data" pattern, and it gets painfully slow, painfully fast.

Analogy: Everyone at a party of n people shaking hands with everyone else — the number of handshakes doesn't grow with the number of people, it grows with the number of pairs of people, which grows much faster.

def has_duplicate_naive(items):
    for i in range(len(items)):
        for j in range(len(items)):
            if i != j and items[i] == items[j]:
                return True         # for every item, we re-scan the whole list again
    return False

Putting it side by side#

Look closely at that last column. At a million items, an O(n²) algorithm is doing roughly a trillion steps, while an O(n) algorithm does a million and an O(1) algorithm does exactly one. This table is the entire reason Big-O matters in practice: a difference that's invisible on tiny test data becomes the difference between "instant" and "never finishes" once real-world data gets large.

Two small notes on how Big-O is normally used:

• We describe the worst case unless stated otherwise — how many steps could this take in the least convenient scenario? (Some structures have an average case that's better than their worst case — you'll see this explicitly with hash tables later.)
• Constants and lower-order terms are dropped. An algorithm that takes 2n + 100 steps is still called O(n) — Big-O describes the shape of growth as n gets large, not the exact count.

Why this page exists#

Every page after this one in this course will describe a data structure's operations using exactly this vocabulary — "insertion is O(1) at the end of a dynamic array but O(n) at the front," "search in a balanced binary search tree is O(log n)," and so on. If a sentence like that reads naturally to you by the end of this page, you're ready for everything that follows. If it doesn't yet, re-read the table above — it's worth it, because literally every remaining page leans on it.

Common mistakes#

• Assuming Big-O tells you exact runtime. It describes growth rate, not seconds. An O(n) algorithm can absolutely be slower than an O(n²) one for small n — the crossover only matters as n gets large.
• Ignoring the difference between average case and worst case. A structure that's "usually O(1)" but occasionally O(n) (like a hash table under bad conditions) is a very different promise than one that's always O(1).
• Reaching for the data structure you already know, out of habit, rather than the one the problem actually needs. The rest of this course is about building a big enough toolbox that the right choice becomes obvious rather than accidental.