Linked Lists

Next up is the **Linked List**. Unlike an array, a linked list's elements are not required to be stored at contiguous memory locations. Instead, each element (called a **node**) contains the data and a pointer to the next node in the sequence. Think of it as a treasure hunt. Each clue (node) tells you where to find the next one. The list has a starting point, a pointer to the first node, called the **head**. The last node points to `NULL`, indicating the end of the list.

#include <stdlib.h>

// A simple representation of a node
typedef struct Node {
  int data;
  struct Node* next;
} Node;

// Creating a simple linked list: 1 -> 2 -> 3
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = (Node*)malloc(sizeof(Node));
head->next->data = 2;
head->next->next = (Node*)malloc(sizeof(Node));
head->next->next->data = 3;
head->next->next->next = NULL;

Linked lists are very flexible. Adding or removing nodes is efficient because you only need to update a few pointers. You don't need to shift other elements like in an array, and they can grow or shrink dynamically at runtime. The downside is that you cannot directly access an element by its index. To find the 5th element, you have to start at the head and follow the pointers five times. This is called "traversal".