Why not just use Arrays?

Arrays are fast for access, but they are rigid:

1. Fixed Size: You must reallocate and copy the entire array to grow it.
2. Expensive Insertions: Inserting at the beginning requires shifting every other element.

A Linked List is a sequence of Nodes scattered throughout the heap. Each node knows only two things: its data and where the next node is.

Self-Referential Structures

To build a node, we need a structure that contains a pointer to itself. This is called a self-referential structure.

struct Node {
    int data;           // The payload
    struct Node *next;  // Pointer to the next node
};

The Head Pointer

The “Head” is just a standard pointer that stores the address of the first node. If the list is empty, head is NULL.

Traversing the List

To move through the list, we use a temporary pointer. We never move the head pointer itself during traversal, or we will lose the list!

struct Node *current = head;
while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
}

Insertion at the Head

Inserting at the head is an $O(1)$ operation regardless of the list size.

1. Create a new node.
2. Set new_node->next to the current head.
3. Update head to point to the new_node.

// To delete a list, we must free every node.
struct Node *tmp;
while (head != NULL) {
    tmp = head;
    head = ;
    free(tmp);
}

The Price of Dynamicity

Linked lists are powerful but come with costs:

• No Random Access: To get the 100th element, you must visit the previous 99.
• Cache Inefficiency: Because nodes are scattered in memory, they suffer from frequent cache misses.
• Memory Overhead: Each node uses extra bytes for the next pointer.