What a data structure is

Introduction

A data structure is a way to store data so that the operations you need are fast. An array, a linked list, a tree and a hash table can all hold the same 1000 student marks; they differ in which operations are cheap: finding a mark, adding one, removing one, or listing them in order.

This course builds each structure in C, one node at a time, so you can watch every pointer in the visualizer. It assumes the C course up to structs and malloc.

Every useful program stores data and then asks questions about it. With ten items nearly any method feels instant. With ten million, the right structure is the difference between an answer in a moment and an answer tomorrow.

How it works

The same data, a different cost

#include <stdio.h>

int main(void) {
    int a[8] = {10, 20, 30, 40, 50};
    int n = 5;
    int value = 25;
    int i = n - 1;
    while (i >= 0 && a[i] > value) {
        a[i + 1] = a[i];
        i--;
    }
    a[i + 1] = value;
    n++;
    for (int k = 0; k < n; k++) printf("%d ", a[k]);
    printf("\n");
    return 0;
}

Inserting 25 into a sorted array keeps it sorted, but every larger value has to move one place right first. Watch the cells shift: the cost is O(n). A linked list can insert in O(1) once you are at the right place, because nothing moves; only two pointers change. Choosing a structure means choosing which costs you are willing to pay.

Abstract data types

A stack, a queue or a dictionary is an abstract data type (ADT): a list of operations, such as push and pop, with no word about how they are stored. An ADT can be implemented in more than one way. You will build a stack on an array and on a linked list, and see that the user of the stack cannot tell the difference.

Syntax

There is no new C syntax in this lesson. The notation is for talking about cost:

O(1)       the work does not grow with n
O(log n)   doubling n adds one more step
O(n)       doubling n doubles the work
O(n log n) a little more than doubling
O(n²)      doubling n makes four times the work

Example

#include <stdio.h>

int main(void) {
    int marks[] = {72, 45, 90, 38, 66, 81};
    int n = 6;
    int target = 66;
    int steps = 0;
    int found = -1;
    for (int i = 0; i < n; i++) {
        steps++;
        if (marks[i] == target) {
            found = i;
            break;
        }
    }
    printf("found at index %d after %d comparisons\n", found, steps);
    return 0;
}

To find 66, the loop compares it with each mark until it matches. The visualizer counts the work for you: watch steps grow. If the array held a million marks and the one we want were last, that would be a million comparisons.

We describe this with Big-O: the number of steps as the input size n grows, ignoring small constants.

Line by line

1. marks is the data, and n says how many items it holds.
2. target is the value to find. found starts at -1, which means "not found yet".
3. The loop looks at each mark in turn, and steps++ counts one comparison.
4. When a mark equals the target, the loop records its index and break stops the search.
5. printf reports where the value was and how many comparisons it took. Here 66 is the fifth mark, so there are 5.

Expected result

found at index 4 after 5 comparisons

In the real world

Database designers, game programmers and the authors of every language's standard library make these choices all the time. A search box that answers as you type is possible only because someone chose a structure whose lookups stay fast as the data grows.

Common mistakes

• Treating Big-O as a measure of seconds: it says how the work grows, not how long one run takes.
• Quoting only the best case: finding the item at index 0 is lucky, and says nothing about a search in general.
• Forgetting that memory has a cost too: a faster structure often uses more of it.

Best practices

• Ask which operations your program does most often before choosing a structure.
• State the worst case unless you have a reason to talk about the average.
• Count steps in a small run, as this example does, to check what you believe.

Summary

A data structure stores data so that the operations you need are fast. Big-O describes how the cost grows with the input, and an abstract data type names the operations while leaving the storage open.

Mark lesson complete