Introduction to Data Structures

A data structure is a way of organising data in memory so that the operations you need — search, insert, delete, find the smallest — are fast. The same million phone numbers can be stored in an array, a linked list, a tree or a hash table; each choice makes some operations quick and others slow.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. — Linus Torvalds

#Why it matters

Imagine looking up a contact among 1,000,000 numbers:

Same data, same computer — a 1,000,000× difference, purely from how the data is organised.

#Abstract data types

An abstract data type (ADT) describes what operations a structure supports, not how they are implemented. A data structure is a concrete implementation of an ADT.

Think of an ADT as a remote control's buttons, and the data structure as the electronics inside.

#Classifying data structures

• Linear: elements form a sequence, each with at most one predecessor and successor — arrays, linked lists, stacks, queues.
• Non-linear: an element can connect to many others — trees (hierarchies) and graphs (networks).
• Static: size fixed at compile time (a C array).
• Dynamic: grows and shrinks at run time (a linked list built with malloc).

#The operations we measure

Every structure in this course is judged by the cost of a handful of operations:

1. Traversal — visit every element once.
2. Search — find an element with a given key.
3. Insertion — add an element.
4. Deletion — remove an element.
5. Sorting and merging — for collections of data.

The next lesson gives you the language for comparing those costs: Big-O notation.

#A first taste: the same job, two structures

Both programs below store marks and answer "is 72 in the list?". The array keeps data in one block; the linked list chains separate nodes together with pointers. You will build both properly in this course.

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

typedef struct Node { int data; struct Node *next; } Node;

int main(void) {
    int arr[] = {55, 72, 81, 64};
    for (int i = 0; i < 4; i++)
        if (arr[i] == 72) printf("array: found 72 at index %d\n", i);

    Node *head = NULL;                       // build list 64 -> 81 -> 72 -> 55 by inserting at the front
    for (int i = 0; i < 4; i++) {
        Node *n = malloc(sizeof(Node));
        n->data = arr[i];
        n->next = head;
        head = n;
    }
    int pos = 0;
    for (Node *p = head; p; p = p->next, pos++)
        if (p->data == 72) printf("list:  found 72 at node %d\n", pos);
    while (head) { Node *t = head; head = head->next; free(t); }
    return 0;
}

array: found 72 at index 1
list:  found 72 at node 2