C++ Linked Lists Explained
Introduction to Linked Lists
Beyond the Array
Arrays are incredibly useful, but they have a rigid personality. Once you create an array, its size is set in stone. If you need more space, you have to create a whole new, bigger array and copy everything over. Adding or removing an item from the middle is just as clumsy—you have to shift all the other elements to make room or close a gap.
Imagine a train where all the cars are welded together. To add a car in the middle, you'd have to cut the train apart and re-weld it. That's an array. Now, what if each car was connected by a simple coupler? You could easily add or remove cars anywhere. That's the idea behind a linked list.
A linked list is a data structure where elements are not stored in back-to-back memory locations. Instead, each element points to the next one in the sequence, forming a chain.
The Building Blocks
Every linked list is built from a few key components. Understanding them is essential before you start writing any code.
Node
noun
The basic unit of a linked list. Each node contains two pieces of information: the actual data it's holding and a pointer.
Think of a node as a single train car. It holds cargo (the data) and has a coupler to connect to the next car (the pointer).
Pointer
noun
A reference that stores the memory address of the next node in the list. This is what connects the nodes into a chain.
The list is held together by these pointers. The last node in the list has a special pointer, called a null pointer, which indicates the end of the chain. It's like the last train car, which has a coupler but nothing attached to it.
We also need a way to find the beginning and end of the list. That's where the
headandtailcome in.
Head: This is a pointer that always points to the very first node in the list. Without the head, you'd have no way to access the list. It's your entry point, like knowing where the engine of the train is.
Tail: This pointer marks the last node in the list. While not strictly necessary for a basic linked list, having a tail pointer makes it much faster to add new nodes to the end.
Key Differences
So when should you use a linked list instead of an array? It depends on what you need to do. Here’s a quick comparison.
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous (all together) | Non-contiguous (scattered) |
| Size | Fixed | Dynamic (can grow/shrink) |
| Insertion/Deletion | Slow (requires shifting) | Fast (requires changing pointers) |
| Element Access | Fast (random access by index) | Slow (sequential access from head) |
The main takeaway is flexibility. Linked lists shine when you have a list of items that changes frequently. Because nodes can be stored anywhere in memory, you don't have to worry about finding a big, continuous block of space. Adding or removing a node is as simple as updating a couple of pointers, no matter how large the list is.
The trade-off is access speed. With an array, you can jump directly to any element using its index, like myArray[10]. With a linked list, if you want the 10th element, you have to start at the head and follow the pointers nine times to get there. There are no shortcuts.
Unlike arrays, where everything sits together in one continuous block of memory, linked lists are scattered each node living wherever it finds space, linked by pointers.
Let's review these core concepts.
Time to check your understanding.
What is the primary advantage of a linked list over an array?
In a linked list, what is the role of the head pointer?
Now that you understand what a linked list is and why it's useful, you're ready to see how it's built in code.