Introduction to Linked List

This lesson lays the groundwork for linked lists in C: how a list organizes data, what makes a linked list different from a plain array, what a node is, how memory layout differs, where linked lists win or lose compared to arrays, and where they show up in real systems. Later topics cover representation, operations, and code in detail.

1) What is a list?

In data structures, a list usually means an ordered sequence of elements: first, second, third, and so on. The order matters—you can speak of the “next” item after the current one. Lists are linear: you move along a single chain of items, not a grid.

How that sequence is stored can vary. A static array keeps elements in one contiguous block of memory with fixed size (in C, declared size or compile-time length). A dynamic array can grow by reallocating, but elements are still laid out next to each other. A linked list implements the same abstract idea—“a sequence of items”—by connecting separate pieces of memory with pointers. So: “list” describes the logical shape (ordered sequence); “linked list” describes one physical way to implement it.

2) What is a linked list?

A linked list is a linear collection of nodes. Each node typically stores:

• the data you care about (e.g. an int, a struct), and
• one or more pointers to other nodes (e.g. “next”, and for doubly linked lists, “previous”).

Unlike an array, nodes do not have to sit in adjacent memory addresses. You follow next pointers from the head (start of the list) to walk the chain. That gives you flexible size (allocate nodes as needed) at the cost of extra memory for pointers and no O(1) random access by index—you usually traverse from the head.

Common variants include singly linked lists (one pointer per node), doubly linked lists (forward and backward), and circular lists (the last node points back to the head or another node). All still share the same core idea: sequence through links, not through contiguous indices. See Types of Linked List for a structured overview.

Memory picture: array vs linked list

Same logical sequence 10 → 20 → 30, two different storage stories:

ARRAY (contiguous addresses — schematic)
index:    [0]      [1]      [2]
        ┌────────┬────────┬────────┐
values: │   10   │   20   │   30   │
        └────────┴────────┴────────┘
        └── one block; i-th element via base + offset

LINKED LIST (nodes may be anywhere in the heap)
  head
    │
    ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: ───────┼───→│ next: ───────┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
 visit by following pointers, not by index

3) What is a node?

A node is one record in the linked list: the smallest building block. In C you usually define it with a struct, for example:

• a field for the payload (value or key), and
• a field of type struct Node * (or similar) pointing to the next node.

So “node” = one unit of storage + the link(s) to its neighbor(s). The last node’s “next” pointer is often NULL, meaning “end of list.” Creating a node usually means allocating memory on the heap (malloc / calloc), filling the fields, and stitching pointers so the list stays valid—covered in Creating a Node and Linked List Representation in C.

Minimal singly linked node in C

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

The exact payload type can be char *, another struct, etc.; the pointer field is what links the sequence.

4) Real-life examples of linked lists

Linked-list ideas appear wherever you need a sequence that grows and shrinks and you mainly move forward or backward step by step, not random jumps:

• Undo / redo in editors — chains of operations or states can be modeled as linked structures.
• Playlists — each track points to what plays next; order is explicit.
• Browser history — back/forward behaves like a doubly linked walk.
• OS kernels — run queues, free lists of memory blocks, I/O lists often use intrusive linked lists inside structs.
• Hash table chaining — collisions stored as a small linked list per bucket.

Not every app exposes a “linked list” to users by name, but the pattern—small records + pointers forming a chain—is everywhere in low-level and application code. In C, mastering nodes and pointers is what makes linked lists practical.

5) Array vs linked list (quick comparison)

Use this as a cheat sheet next to the longer pros/cons below. Details depend on sorted vs unsorted data, allocator behavior, and whether you already hold the right pointers.

For a dedicated discussion, open Linked List vs Arrays.

6) Advantages of linked lists

Compared to a contiguous array, linked lists shine when the workload favors flexible size and pointer rewiring over fast random access:

• Dynamic size — Add or remove nodes with malloc / free without shifting every later element, and without a fixed maximum capacity.
• Cheap insert and delete at a known position — With a pointer to a node (or its predecessor), middle insert/delete is O(1) pointer updates vs O(n) shifts in arrays.
• No large reallocations — Growth is incremental instead of copying an entire block when capacity doubles.
• Large records — Swap or move pointers instead of copying heavy structs.
• Natural fit for many algorithms — Stacks, queues, graph adjacency lists, and hash table chaining.

7) Disadvantages of linked lists

The same design choices that help flexibility create costs you should plan for:

• No random access by index — The k-th element needs a walk from the head, typically O(n).
• Pointer overhead — Each node pays for next (and prev in doubly linked lists); for tiny data, pointers dominate.
• Cache locality — Scattered nodes hurt sequential CPU cache behavior compared to tight arrays.
• More fragile in C — Correct NULL ends, no use-after-free, no leaks, careful sharing when several pointers reference one node.
• Singly linked lists — Backward traversal or delete-without-predecessor is awkward; doubly linked lists add a pointer per node to fix some of that.

Rule of thumb: prefer linked lists when you insert/delete often in the middle or size is unpredictable; prefer arrays when you need index access, cache-friendly scans, or minimal per-element overhead.