Linked Lists in C Explained
Introduction to Linked Lists
The Scavenger Hunt of Data
Imagine a scavenger hunt. You get the first clue, which leads you to the second, which leads to the third, and so on. You can't just jump to the final prize; you have to follow the chain of clues in order.
A linked list is a data structure that works a lot like this. Instead of storing data in one continuous block, like an array, a linked list is made up of individual elements called nodes. Each node contains two things:
- Some piece of data (an integer, a character, etc.)
- A pointer, which is like a clue pointing to the location of the next node in the sequence.
The very first node is called the head. It's our starting point for the scavenger hunt. The last node in the list doesn't point to another node; its pointer is set to NULL, signaling the end of the line.
Flexible Chains vs. Fixed Boxes
You're likely familiar with arrays, which store data in a single, contiguous block of memory. Think of an array like a pill organizer with a fixed number of compartments. It's great for quickly grabbing an item if you know its position (its index), but what happens if you need to add a new item in the middle? You have to shift everything after it down, which can be slow. And if you run out of compartments, you're out of luck unless you get a bigger organizer.
Linked lists solve these problems. Since each node is a separate object in memory, they don't need to be stored next to each other. This non-contiguous nature makes them incredibly flexible.
This flexibility gives linked lists a key advantage: inserting or removing elements is highly efficient. To add a new node, you just need to create it and then adjust the pointers of its neighbors to include it in the chain. No massive data shifting is required. This also means a linked list can easily grow or shrink as needed during program execution; it's a dynamic data structure.
The trade-off is in access speed. With an array, you can instantly access any element using its index, like my_array[5]. With a linked list, there are no indices. To find the fifth element, you must start at the head and follow the pointers one by one until you get there. This is called traversal.
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous block | Non-contiguous nodes |
| Size | Fixed (static) | Dynamic (can grow/shrink) |
| Access | Fast, direct (by index) | Slow, sequential (traversal) |
| Insertion/Deletion | Slow (requires shifting) | Fast (requires pointer changes) |
Different Kinds of Chains
Not all linked lists are the same. They come in a few common variations, each suited for different tasks.
Singly Linked List: This is the scavenger hunt we've been discussing. Each node has one pointer that directs you only to the next node in the list. Traversal is a one-way street.
Doubly Linked List: This is a more advanced scavenger hunt where each clue tells you where the next clue is and where the previous one was. Each node has two pointers: one to the
nextnode and another to theprevnode. This allows you to traverse the list both forwards and backwards.
Circular Linked List: In this version, the last node doesn't point to
NULL. Instead, it loops back and points to the very first node (the head). The list has no end! This can be useful for applications that need to cycle through a set of items continuously, like a playlist on repeat.
Understanding these structures is the first step. While they might seem abstract, linked lists are the foundation for many other complex data structures, like stacks and queues, and are used everywhere in software.
Time to check your understanding of these foundational concepts.
What is the primary structural difference between a linked list and an array?
Each element, or node, in a standard singly linked list contains which two components?
Now that you know what linked lists are and why they're useful, you're ready to see how to actually build and manage them in C.