What a data structure buys you

The question nobody asks first

Students learn struct node { int data; struct node *next; }; before anyone explains why that struct exists. So here is the why.

A data structure is a deal. You pay something - extra memory, slower insertion, more code - and in return one operation you do very often becomes much faster. Choosing a data structure means deciding which operation you cannot afford to be slow.

A concrete example

You have 100,000 roll numbers. A user types one and you must say whether it is in the list.

Plan A: unsorted array. Check every element until you find it.

int contains(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return 1;
    }
    return 0;
}

Worst case: 100,000 comparisons.

Plan B: sorted array, binary search. Cut the range in half each time.

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

Worst case: 17 comparisons, because 2^17 = 131,072 which is more than 100,000.

100,000 versus 17. Same data, same machine, same language. The only thing that changed is how the data was arranged.

The price of Plan B: you had to sort first, and every new roll number must be inserted in the right place, which means shifting elements. If you look up a million times and insert twice, Plan B wins enormously. If you insert a million times and look up twice, Plan A wins.

Counting operations, not seconds

Seconds depend on the machine, the compiler and whether someone else is running a build on the lab server. So we count operations as a function of the input size n, and we ignore constants.

Read the last row carefully. A quadratic algorithm on a million items is a trillion operations. At 100 million operations per second that is about three hours. The same job in O(n log n) takes under a second. This is why your teacher keeps saying "nested loop over the same array" in a warning tone.

Memory is the other half of the deal

C does not hide memory from you, so you can measure it.

#include <stdio.h>

struct node {
    int data;
    struct node *next;
};

int main(void) {
    printf("int          : %zu bytes\n", sizeof(int));
    printf("pointer      : %zu bytes\n", sizeof(void *));
    printf("struct node  : %zu bytes\n", sizeof(struct node));
    return 0;
}

On a typical 64-bit machine this prints 4, 8 and 16. Not 12 - 16. The compiler adds 4 bytes of padding after the int so the 8-byte pointer sits at an address divisible by 8, which the CPU requires. That is called structure alignment and it is a favourite viva question.

So storing 1,000,000 ints costs:

• Array: 4,000,000 bytes, about 4 MB.
• Linked list: 16,000,000 bytes, about 16 MB, plus per-allocation

bookkeeping from malloc which is usually another 8 to 16 bytes a node.

The linked list uses four times the memory to store the same numbers. That is what you pay for being able to insert in the middle without shifting.

Cache: the cost that is not in the textbook

An array's elements sit next to each other in memory. When the CPU fetches one, it pulls a whole 64-byte cache line, so the next 15 ints arrive free. Walking an array is therefore far faster than the operation count suggests.

A linked list's nodes are wherever malloc put them. Each next jump can be a cache miss costing roughly 100 CPU cycles. Two O(n) traversals, one 5 to 10 times slower than the other. Big-O will not tell you this; the machine will.

How to choose

Ask three questions before writing any code.

1. What operation happens most often - search, insert, delete, or scanning

everything in order?

1. Does the data need to stay sorted?
2. Do I know the maximum size in advance?

If the answer to 3 is yes and to 2 is no, an array is usually right and you should not feel bad about it. Students often reach for a linked list to look serious. A plain array with a size counter is faster, shorter and easier to debug.