Choosing a data structure

Introduction

No structure is best at everything. To choose, list the operations your program does most often, then pick the structure that makes those cheap.

You now have a toolbox. The skill that matters most is knowing which tool to pick up, and that choice is what many interview and design questions are really testing.

How it works

The cost table

Matching problems to structures

Syntax

No new syntax is needed. A useful way to think is to write the job as a list of operations, with an estimate of how often each happens:

Lookup by student ID     very often
Add a student            sometimes
List students in order   rarely

Example

#include <stdio.h>

int linear(int a[], int n, int key, int *steps) {
    for (int i = 0; i < n; i++) {
        (*steps)++;
        if (a[i] == key) return i;
    }
    return -1;
}

int binary(int a[], int n, int key, int *steps) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        (*steps)++;
        int mid = (lo + hi) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main(void) {
    int a[16];
    for (int i = 0; i < 16; i++) a[i] = 3 * i;   // 0, 3, 6, ..., 45
    int s1 = 0, s2 = 0;
    linear(a, 16, 42, &s1);
    binary(a, 16, 42, &s2);
    printf("linear: %d comparisons, binary: %d comparisons\n", s1, s2);
    return 0;
}

Both functions find 42 in the same 16 sorted numbers. Linear search compares from the start; binary search halves the range each time. 15 comparisons against 4. With a million numbers it would be up to a million against 20. Keeping data sorted (or in a BST) buys fast search, at the price of slower inserts.

Line by line

1. linear compares key with each item from the start, and (*steps)++ adds one to the caller's counter.
2. binary keeps a range from lo to hi, and each pass adds one step.
3. It compares the middle item. Equal means found, and otherwise half of the range is thrown away.
4. main fills 16 cells with multiples of 3, so the array is sorted.
5. Both searches look for 42, and each receives its own counter by address.
6. printf shows both counts on one line.

Expected result

linear: 15 comparisons, binary: 4 comparisons

In the real world

A database engineer picks between a B-tree index and a hash index by asking this same question: will people ask for exact matches, or ranges? Caches, routers and search engines are all designed around the operations they do most.

Common mistakes

• Picking a structure because it is familiar, without listing the operations first.
• Optimising a part of the program that runs only a few times.
• Forgetting the cost of keeping a structure sorted or balanced when it changes often.

Best practices

• Write down the operations and how often each happens.
• Prefer the simplest structure that is fast enough.
• Measure with realistic data when two choices look close.

Summary

No structure is best at everything. List the operations your program needs, compare the costs, then pick the simplest structure that makes the most common operations cheap.

Mark lesson complete