Arrays vs linked lists

An array is an address plus arithmetic

int marks[5] = {72, 65, 88, 41, 91};
printf("%d\n", marks[3]);      // 41

marks[3] is not a search. The compiler turns it into "start address of marks, plus 3 times 4 bytes, read the int there". One multiplication, one addition, one memory read. That is O(1) and it does not get slower when the array has a million elements.

You can see the arithmetic yourself:

#include <stdio.h>

int main(void) {
    int marks[5] = {72, 65, 88, 41, 91};
    printf("%p\n", (void *)&marks[0]);
    printf("%p\n", (void *)&marks[1]);
    printf("%d\n", *(marks + 3));    // same as marks[3], prints 41
    return 0;
}

The two addresses differ by exactly 4. marks[3] and *(marks + 3) are the same expression to the compiler. That is also why 3[marks] compiles - a piece of trivia that occasionally appears in a quiz.

The two things an array cannot do

It cannot grow. int marks[5] is 5 forever. To hold a sixth you must allocate a bigger block and copy everything across.

It cannot insert in the middle cheaply. To put a value at position 0 of an n-element array, all n elements shift right.

void insert_at(int arr[], int *n, int pos, int value) {
    for (int i = *n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;
    (*n)++;
}

That loop is O(n). For 100,000 elements, inserting at the front 100,000 times is 5 billion moves.

A linked list is a chain of separate boxes

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

Each node holds a value and the address of the next node. The last node's next is NULL. The nodes are not next to each other in memory - they are wherever malloc found space.

Inserting at the front is three lines and does not touch any other node.

struct node *push_front(struct node *head, int value) {
    struct node *n = malloc(sizeof(struct node));
    if (n == NULL) return head;      /* out of memory */
    n->data = value;
    n->next = head;
    return n;                        /* the new head */
}

That is O(1) regardless of list length. Nothing shifts.

The price: to reach element 5000 you must follow 5000 pointers. There is no arithmetic shortcut, because there is no pattern to the addresses.

The honest comparison

Two rows deserve comment.

"Binary search: not possible." Binary search needs to jump to the middle in O(1). A list cannot do that, so a sorted linked list gives you no search advantage at all. If you need fast search on sorted data, you need an array or a tree.

"Insert after a node you already hold: O(1)." This is the linked list's real strength and it is usually stated wrongly. The list is only fast if you are already at the position. Searching for the position first costs O(n), which cancels the benefit. Linked lists win when you are walking the list anyway and deleting as you go.

The measurement students never see

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int n = 20000000;
    int *a = malloc((size_t)n * sizeof(int));
    if (a == NULL) return 1;

    for (int i = 0; i < n; i++) a[i] = i;

    clock_t start = clock();
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    double secs = (double)(clock() - start) / CLOCKS_PER_SEC;

    printf("sum = %lld in %.3f s\n", sum, secs);
    free(a);
    return 0;
}

Run that, then write the same sum over a 20-million-node linked list. Both are O(n). The array version typically finishes several times faster because of cache lines. Put both timings in your lab record; it is the kind of detail that separates a report from a copy.

When to choose which

Use an array when the size is known or bounded, when you index by position, when you need binary search, or when you will scan the whole thing repeatedly. This covers most college assignments.

Use a linked list when the size is unpredictable and can grow large, when you insert and delete constantly at known positions, or when you are building a stack or a queue whose size you cannot bound.