The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

What Are Data Structures?

Next ►
►

Welcome to the Data Structures course. In this first lesson we are going to answer the fundamental question the course is named after: what exactly is a data structure? A solid grasp of this definition — and of the difference between what a structure promises to do and how it does it internally — gives you the mental framework everything else rests on. You will also meet TaskFlow, the task management application we will build piece by piece throughout the course. It will be our running thread, so every concept has a real application from day one.

Contents

  1. The formal definition: data, relationships, and operations
  2. Everyday analogies to build intuition
  3. Abstract Data Type (ADT) vs concrete implementation
  4. Introducing TaskFlow: our course project
  5. TaskFlow's data needs

The formal definition: data, relationships, and operations

A data structure is a way of organizing information in a computer's memory so that we can work with it effectively. That sentence, while correct, doesn't tell the whole story. The formal definition has three components, and all three matter equally:

  • Data: the values we want to store (numbers, text, objects...).
  • Relationships: how those values connect to one another (one after another, in a hierarchy, in a network...).
  • Operations: what actions we can perform on them (insert, find, remove, traverse...).

We can sum it up in an informal formula:

Data structure = Data + Relationships between the data + Allowed operations

Let's see what each component means with a minimal Python example:

# Data: three task titles
tasks = ["Design logo", "Write report", "Review budget"]

# Relationships: order matters. "Design logo" comes BEFORE "Write report".
# The structure (a list) maintains that ordering relationship for us.

# Operations: the structure defines what we can do
tasks.append("Send invoice")   # insert at the end
first = tasks[0]               # access by position
tasks.remove("Write report")   # remove an element

print(tasks)
# ['Design logo', 'Review budget', 'Send invoice']

Let's walk through the example line by line:

  • tasks = [...] creates the structure and stores the data (three strings).
  • The relationship here is sequential order: each task has a position, and that position means something (execution priority, for example). If order didn't matter, another structure might be a better fit.
  • append, indexing with [0], and remove are the operations this structure offers us. Every data structure offers a different catalog of operations, and that is the key to the entire course: choosing the structure whose relationships and operations match your problem.

The same set of data can be organized in many ways. Those three task titles could be stored in an ordered sequence, in an unordered set, or each one associated with an identifier. The data is the same; what changes are the relationships and operations — in other words, the structure.

Key idea: a data structure is not "a place to put things", but a contract: it defines which relationships are maintained between the data and which operations you can perform on it.

Everyday analogies to build intuition

Data structures existed long before computers. Humans have been organizing physical information for centuries, and those everyday arrangements make perfect analogies:

Everyday object How it organizes information What it makes easy What it makes hard
Shopping list Items one after another Adding at the end, reading in order Finding one specific product among hundreds
Stack of plates The last one you put down is the first one you pick up Stacking and unstacking from the top Grabbing the bottom plate without dismantling the pile
Supermarket checkout line First to arrive is first to be served Serving people in arrival order Cutting in line (and it's frowned upon!)
Phone book by letter Each name filed under its initial Jumping straight to the "M" section Listing contacts by date added
Family tree Hierarchy of parents and children Seeing ancestry and descendants Relating distant cousins directly
Road map Cities connected by roads Finding routes between points There is no single "order" of cities

Notice an important detail in the table: every arrangement makes some things easy and other things hard. The stack of plates is wonderfully convenient for what a stack does (putting down and picking up from the top), but terrible if you need the plate at the bottom. There is no perfect arrangement for everything; there is the right arrangement for each use. This principle, obvious in the kitchen, is exactly the same in programming.

Each row of that table also corresponds to a real data structure we will study in this course: the list, the stack, the queue, the hash table, the tree, and the graph. For now, just hold on to the intuition; we'll see the full landscape of types in lesson 01-03.

Abstract Data Type (ADT) vs concrete implementation

This is the most important concept in the lesson, and one that separates a developer who "uses" structures from one who understands them.

An Abstract Data Type (ADT) is the specification of a structure: it defines which operations it offers and how they behave, without saying anything about how they are programmed internally. The concrete implementation is the actual code that fulfills that specification.

The classic analogy is the car:

  • ADT: "a car has a steering wheel to turn, an accelerator to go faster, and a brake to stop". Anyone who knows how to drive can use any car, because the contract is the same.
  • Implementation: a specific car can be gasoline, electric, or hybrid. Internally they are radically different, but the steering wheel, accelerator, and brake behave the same.

Let's see it in code. We'll define the "Stack" ADT (we will study it in depth in module 3; here we only care about it as an example of a contract):

ADT Stack:
  - push(item):     adds an item to the top
  - pop():          removes and returns the item at the top
  - peek():         looks at the item at the top without removing it
  - is_empty():     tells whether there are no items

Notice that the specification says nothing about Python lists, memory, or pointers. It only states what each operation does. Now, two concrete implementations of the same ADT:

class ListStack:
    """Implementation of the Stack ADT using a Python list."""

    def __init__(self):
        self._items = []          # the internal state is a list

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()  # pop() removes the last item

    def is_empty(self):
        return len(self._items) == 0


class DictStack:
    """Another implementation of the SAME ADT, with different internal state."""

    def __init__(self):
        self._items = {}          # the internal state is a dictionary
        self._count = 0           # we keep track of positions

    def push(self, item):
        self._items[self._count] = item
        self._count += 1

    def pop(self):
        self._count -= 1
        return self._items.pop(self._count)

    def is_empty(self):
        return self._count == 0

And now, the important part: the code that uses the stack does not need to know which of the two implementations it is dealing with.

def process(stack):
    """This function works with ANY implementation of the Stack ADT."""
    stack.push("action 1")
    stack.push("action 2")
    while not stack.is_empty():
        print("Undoing:", stack.pop())

process(ListStack())   # Undoing: action 2 / action 1
process(DictStack())   # Undoing: action 2 / action 1

A detailed explanation of the example:

  • process only knows the contract: it knows that push, pop, and is_empty exist, and what they are supposed to do. It never looks inside the stack.
  • The two classes store their data in completely different ways (a list vs a dictionary with a counter), but from the outside they behave identically: both return the items in the reverse order they were pushed.
  • The leading underscore in self._items is a Python convention meaning "this is internal, don't touch it from outside". It reinforces the idea that the ADT's user should only rely on the public operations.

This separation has enormous practical consequences:

  • You can swap the implementation without breaking the code that uses it (for example, for a faster one once you learn to measure performance).
  • You can reason about your program in terms of contracts, without carrying around the internal details of every piece.
  • It is the basis of how we will study every structure in the course: first the ADT (what it promises), then one or more implementations (how it delivers).

Introducing TaskFlow: our course project

Throughout the course we are going to build, piece by piece, TaskFlow: a task and project management application written in Python. The idea is simple: instead of studying each data structure with disconnected examples, each one will solve a real need of the application, so that by the end of the course you will have both the knowledge and a tangible project.

What does TaskFlow do? What you would do with any task manager like Trello or Todoist, in a simplified version:

  • Create tasks with a title, description, priority, and status.
  • Organize them on a board and move them between statuses ("pending", "in progress", "done").
  • Undo the last action if you make a mistake.
  • Receive and process notifications.
  • Look up any task instantly by its identifier.
  • Classify tasks into categories and subcategories.
  • Declare that one task depends on another and compute the order to do them in.

Our first piece of TaskFlow can be as simple as this:

# taskflow.py — version 0.1: a task is a dictionary of attributes
task = {
    "id": 1,
    "title": "Prepare Friday's demo",
    "priority": "high",       # high / medium / low
    "status": "pending",      # pending / in_progress / done
}

print(f"[{task['id']}] {task['title']} ({task['priority']})")
# [1] Prepare Friday's demo (high)

Here a Python dictionary groups the attributes of a single task: each key ("id", "title"...) maps to a value. It is the minimal representation we will start with; in module 2 we will grow it.

TaskFlow's data needs

If TaskFlow only had one task, we wouldn't need this course. The challenge appears when there are many tasks and many ways to relate them. Let's list the application's data needs, because each one foreshadows a module of the course:

TaskFlow need What relationship exists between the data? Module where we'll solve it
A board with tasks in order Sequence: one task after another Module 2 (lists)
Undo the last action The last thing done is the first to be undone Module 3 (stacks)
Process notifications in arrival order First to arrive is first to leave Module 4 (queues)
Find a task by its id instantly Association identifier → task Module 5 (hash tables)
Categories with subcategories Hierarchy: parents and children Module 6 (trees)
"Task B can't start until A finishes" Network of dependencies between tasks Module 7 (graphs)

Notice that each row describes a different relationship between the same data (tasks). That is exactly the definition we opened the lesson with: the data is the same, but the relationships we need to maintain — and the operations we want to perform — change with the use case. That is why there is no "best data structure", only the right one for each need.

Common Mistakes and Tips

  • Confusing the data with the structure. "I have a list of customers" mixes two things: the customers (data) and the list (chosen structure). Get into the habit of asking yourself: which relationships do I need to maintain and which operations am I going to perform? That question decides the structure.
  • Believing that in Python "everything is done with lists and dictionaries". It's true that Python ships with very powerful structures, and we will use them, but if you don't understand the ADT behind them, you won't know when a list is a bad choice (you'll see this very clearly in lesson 01-02).
  • Skipping the specification and going straight to code. Before implementing, write down (even in a comment) which operations your structure must offer. That is the ADT habit: first the contract, then the code.
  • Tip: create a taskflow/ folder on your machine right now and store the course examples in it. By the end you will have a complete application built by you.

Exercises

Exercise 1: identifying the three components

For each scenario, identify the data, the relationships, and at least two operations you would need:

  1. The browsing history of a web browser.
  2. The reserved seats of a movie theater.
  3. The comments and replies (to other comments) on a video.

Exercise 2: specifying an ADT

Write the specification (just the contract, no code) of a TaskList ADT for TaskFlow with these capabilities: add a task, mark a task as done, count how many tasks are still pending, and get the next pending task. For each operation, state what it receives and what it returns.

Exercise 3: two implementations, one contract

Implement in Python the Counter ADT with the operations increment(), decrement(), and value(). Do it twice: an IntCounter class that internally stores a number, and a ListCounter class that internally stores a list, appending an element on increment and removing one on decrement. Verify that an external function works identically with both.

Solutions

Solution 1:

  1. Browser history — Data: the visited URLs. Relationship: temporal order of visits (the most recent "on top"). Operations: add the current page, go back to the previous one, clear the history.
  2. Movie theater seats — Data: the seats (row and number) and their status. Relationship: each seat is uniquely identified by its position; no relevant temporal order. Operations: check whether a seat is free, reserve it, release it.
  3. Video comments — Data: the comments (author, text, date). Relationship: hierarchical, each reply "hangs" off another comment. Operations: add a root comment, reply to a comment, list the replies of a given one.

Solution 2:

ADT TaskList:
  - add(title, priority): receives the title and priority of a new task;
      adds it as pending. Returns nothing.
  - mark_done(title): receives the title of an existing task and changes
      its status to "done". Returns True if it was found, False otherwise.
  - pending(): receives nothing. Returns the number of pending tasks.
  - next(): receives nothing. Returns the oldest pending task,
      or None if there are none left.

What matters is not the exact wording, but that you described behavior without mentioning how anything is stored internally.

Solution 3:

class IntCounter:
    def __init__(self):
        self._n = 0                   # internal state: an integer

    def increment(self):
        self._n += 1

    def decrement(self):
        self._n -= 1

    def value(self):
        return self._n


class ListCounter:
    def __init__(self):
        self._marks = []              # internal state: a list of marks

    def increment(self):
        self._marks.append(1)         # add a mark

    def decrement(self):
        self._marks.pop()             # remove a mark

    def value(self):
        return len(self._marks)       # the value is how many marks there are


def check(counter):
    counter.increment()
    counter.increment()
    counter.increment()
    counter.decrement()
    print(counter.value())            # must print 2 in both cases

check(IntCounter())    # 2
check(ListCounter())   # 2

Both classes fulfill the same contract with different internal state: that is exactly the difference between an ADT and an implementation. (Note: ListCounter wastes more memory; measuring that kind of difference is precisely what we will learn in the next lessons.)

Conclusion

In this lesson you learned that a data structure is the combination of data, relationships, and operations, and that it pays to separate the ADT (the contract: what it does) from the implementation (the code: how it does it). You also met TaskFlow, our task management application, and saw that each of its needs — board, undo, notifications, lookup, categories, dependencies — requires maintaining different relationships between the same data.

One question is still hanging in the air: if several structures can store the same data, does it really matter that much which one you choose? The answer is an emphatic yes, and in the next lesson you will verify it with real numbers: you will see how a poor choice can make TaskFlow take thousands of times longer to do the very same thing.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved