Data Structures & Algorithms (DSA): start here

A program that works on ten items can crawl on ten million. Whether it does depends on two choices: how the data is kept in memory, and the steps used to answer questions about it. Data Structures & Algorithms (DSA) is the study of those two choices, of how to tell that a choice is correct, and of how to predict what it costs before you run it.

This first lesson sets out the words the track uses, shows one idea stored three ways, and explains how to use the examples and exercises.

Algorithm, abstract data type, data structure

Three words come up in every lesson, and they mean different things.

• A problem says which inputs are allowed and what the right output is for each of them. “Given the tickets in the order people took them, call them in that order” is a problem.
• An algorithm is a finite list of precise steps that a computer could carry out to turn an input into an output. It solves a problem when, for every allowed input, it stops and its output is right. A recipe that works only for the examples you tried, or that never finishes on some input, does not solve the problem yet.
• An abstract data type (ADT) is a promise about behaviour. It names the operations and says what each one does, and says nothing about how the data is stored. A queue is an ADT: enqueue adds an item at the back, dequeue removes and returns the item that has waited longest, size says how many are waiting. First in, first out.
• A data structure is one concrete way of laying the data out in memory, together with the code of its operations. A Python list, a collections.deque and a ring buffer (a fixed row of slots whose start moves round) are three data structures that can all keep that promise.

The split matters because the algorithm above only needs the queue’s operations. Swap one data structure for another and the algorithm stays exactly as it is; only the cost of each operation changes.

One queue, three data structures

Here is the ticket counter as code. queues.py holds three classes with the same three operations (in Python the size is asked for with len(queue)), and check_queues.py runs the same sequence of operations against each of them: three tickets join, two are served, a fourth joins, and two more are served. Then it tries to add a fourth ticket to a ring that already holds three.

from queues import DequeQueue, ListQueue, RingQueue

for queue in (ListQueue(), DequeQueue(), RingQueue(capacity=3)):
    for ticket in ("A1", "A2", "A3"):
        queue.enqueue(ticket)
    served = [queue.dequeue(), queue.dequeue()]
    queue.enqueue("A4")  # in the ring, A4 goes into slot 0, which A1 left free
    served += [queue.dequeue(), queue.dequeue()]
    print(f"{type(queue).__name__:<10} served {served}, {len(queue)} waiting")

ring = RingQueue(capacity=3)
for ticket in ("B1", "B2", "B3"):
    ring.enqueue(ticket)
try:
    ring.enqueue("B4")  # a fourth ticket while three are waiting
except OverflowError as error:
    print(f"RingQueue  with {len(ring)} waiting refused B4: {error}")

ListQueue  served ['A1', 'A2', 'A3', 'A4'], 0 waiting
DequeQueue served ['A1', 'A2', 'A3', 'A4'], 0 waiting
RingQueue  served ['A1', 'A2', 'A3', 'A4'], 0 waiting
RingQueue  with 3 waiting refused B4: the queue is full

"""One contract, three data structures: a queue of tickets kept in three different ways."""

from collections import deque


class ListQueue:
    """A Python list: new tickets join at the end, the oldest leaves from the front."""

    def __init__(self):
        self._items = []

    def enqueue(self, ticket):
        self._items.append(ticket)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from an empty queue")
        return self._items.pop(0)  # every ticket still waiting moves one place to the left

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


class DequeQueue:
    """collections.deque: adding or removing at either end takes the same short time."""

    def __init__(self):
        self._items = deque()

    def enqueue(self, ticket):
        self._items.append(ticket)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from an empty queue")
        return self._items.popleft()

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


class RingQueue:
    """A list of fixed size used as a ring: the tickets stay put and the front index moves."""

    def __init__(self, capacity):
        self._slots = [None] * capacity
        self._front = 0  # where the oldest ticket is
        self._size = 0

    def enqueue(self, ticket):
        if self._size == len(self._slots):
            raise OverflowError("the queue is full")
        back = (self._front + self._size) % len(self._slots)  # wraps round to slot 0
        self._slots[back] = ticket
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from an empty queue")
        ticket = self._slots[self._front]
        self._slots[self._front] = None
        self._front = (self._front + 1) % len(self._slots)
        self._size -= 1
        return ticket

    def __len__(self):
        return self._size

All three serve A1, A2, A3, A4 in that order, so all three behave as a queue. Look at what happens inside the ring when A4 arrives. Its three slots are full of A1, A2 and A3 at first; after two tickets leave, the front index points at slot 2, and the back of the queue wraps round to slot 0, which A1 left empty. Nothing is moved.

What they do not share is cost. This is how the cost of each operation grows when n tickets are waiting:

The notation O(n) is the subject of a later lesson; for now read it as “grows in step with n” and O(1) as “does not grow with n”. Python’s documentation gives the reason for the first row: removing the item at position k of a list of n items moves the n − k − 1 items after it, so position 0 is the worst place to remove from. The deque documentation draws the same contrast: a deque appends and pops at either end in about the same O(1) time, while a list pays O(n) to pop or insert at position 0. The ring buffer, also called a circular queue, gets the same speed from a plain list by never moving anything, and pays for it with a fixed capacity: as the last line of the output shows, RingQueue(capacity=3) refuses a fourth waiting ticket with OverflowError.

Choosing a data structure is choosing which operations will be cheap. A ticket counter that serves thousands of people should not use ListQueue.

Measuring: the same work at different speeds

The other way to compare two solutions is to time them. This program adds up a million numbers twice, once with a for loop and once with the built-in sum(), and keeps the fastest of five runs of each:

import time

numbers = list(range(1_000_000))


def loop_sum(values):
    total = 0
    for value in values:
        total += value
    return total


def fastest_ms(function, repeats=5):
    """The fastest of several runs, in milliseconds: slower runs were held up by something else."""
    best = float("inf")
    for _ in range(repeats):
        start = time.perf_counter()
        function(numbers)
        best = min(best, time.perf_counter() - start)
    return best * 1000


assert loop_sum(numbers) == sum(numbers) == 499_999_500_000
loop_ms = fastest_ms(loop_sum)
builtin_ms = fastest_ms(sum)
print(f"for loop: {loop_ms:6.1f} ms")
print(f"sum():    {builtin_ms:6.1f} ms")
print(f"sum() was {loop_ms / builtin_ms:.1f} times as fast")

for loop:   82.3 ms
sum():       6.0 ms
sum() was 13.6 times as fast

Both versions do one addition per number, so the time of both grows in step with n: a list twice as long would take each of them about twice as long. What differs is the cost of each step, which analysis calls the constant factor: on the computer that recorded this output, sum() was many times as fast. time.perf_counter() is the clock to use for this: it has the highest resolution available, and on CPython it never runs backwards.

Timings move with the computer, with whatever else it is doing and with the Python version, which is why most lessons here count steps instead: a count is the same on every computer and on every run. Timings return when the constant factor is the point.

How this track works

• Python first. Lessons teach in Python 3.14, and the examples run with CPython 3.14.8. Where a JavaScript version helps, the example has a second tab, run with Node.js 24.21.0. You need the basics of the Python track (variables, loops, functions and lists); nothing else is assumed.
• Real output. Each example is a real file, and the panel under it shows what it printed and which version printed it. When an output can change from run to run, such as the timing above, the panel says so.
• Run it yourself. Examples with a Run button also run in your browser, on your own device: Python in Pyodide 314.0.7, which contains CPython 3.14.2, and JavaScript in QuickJS. The first run downloads that runtime. You can edit the code and run it again.
• Exercises and quizzes. Most lessons end with an exercise: starter code, a prompt and sample tests you can run in the browser. A pass there is feedback for you, not a grade. The quiz after it shows the answer and the reasoning once you have answered.

The Python Online Compiler and the JavaScript Online Compiler are handy for trying your own variations of any example.

The method this track teaches

Every module uses the same habit, and the next lesson works through it in full:

1. Restate the problem: what goes in, what must come out, and how large the input can be.
2. Write the obviously correct solution first, even if it is slow. This is the brute force.
3. Find its bottleneck: the step that is repeated far more often than necessary.
4. Remove the bottleneck with a better data structure or algorithm, and say in one sentence why the faster version still gives the right answer.
5. Keep the brute force, and check the fast version against it on many inputs.

The exercise of this lesson is step 2 on its own: a brute force, written carefully.

Choose a route

Whatever your goal, start with this module. Complexity, correctness and testing are used in every lesson after it. Then follow the modules in order, or take the route that fits:

• Coding interviews. Arrays and strings, hashing, recursion, sorting, binary search, linked lists, stacks and queues, trees, heaps, graphs, greedy algorithms and dynamic programming, then tries and bit manipulation. Choose this if you want to recognise a problem’s type quickly.
• University exams. The same core modules, with extra care for the proofs and the exact step counts, then maths for DSA, shortest paths and spanning trees, and hard problems. Choose this if you follow a course or prepare for a written exam.
• Programming contests. All the core modules, then maths for DSA, range queries and string algorithms. Choose this if you want to solve timed contest problems.

This track explains each structure and algorithm once, in full. The Coding Interview Patterns track builds timed drills on top of it, and the Competitive Programming track covers contest-level variants.

Key takeaways

• An algorithm solves a problem when it stops with the right output on every allowed input; an abstract data type promises operations and their behaviour; a data structure is one way to store the data and carry out those operations.
• One ADT can have several data structures behind it, all correct, with different costs: a list, a deque and a ring buffer all make a queue, but only list.pop(0) moves every waiting item.
• Timings show constant factors and change from computer to computer; step counts are the same everywhere, which is why this track counts steps first.
• Each example’s panel shows what the file printed and which version printed it; Run buttons run it again in your browser.
• Start with the Foundations module, then follow the route for interviews, exams or contests.