The Singly Linked List: A Flexible Alternative to Arrays

The Singly Linked List: A Flexible Alternative to Arrays

Arrays are great, but they have a weak spot. An array needs one solid, unbroken block of memory, and its size is fixed from the start. So when you want to add or remove items in the middle, you often have to shift many other items around, which is slow. We need a data structure that handles these situations better. That structure is the singly linked list.

What is a linked list?

A linked list is a linear data structure (items come one after another, in a line) that is also dynamic (it can grow and shrink while your program is running).

Here is the key idea. An array keeps all its items packed together in one continuous block of memory. A linked list does the opposite: it stores each item at a random spot in memory, wherever there is free space. To keep the items in order, each item also remembers the location of the next item. So the items form a chain.

Think of it like a treasure hunt. Each clue (item) is hidden in a different place, but every clue tells you where to find the next one. As long as you know where the first clue is, you can follow the chain all the way to the end.

A simple chain might look like this:

1 -> 4 -> 8 -> 3 -> 2

Each box holds a value and a pointer to the next box. The last box points to nothing, which marks the end.

When you want to add a new value, the list does not need a bigger block of memory in advance. It simply creates a new memory block on the spot and links it into the chain. This is what makes the list grow "at will".

Linked list vs array

Compared to an array, a linked list gives you:

• Insertion and deletion at the start and end of the list in O(1) time and O(1) space (a fixed, tiny amount of work no matter how long the list is).
• Insertion and deletion of any item without needing extra space to shift things around.

You can picture it as a stretchy, sequential container whose size you can increase or decrease whenever you like.

How insertion in the middle works

Let's say we have the chain 1 -> 2 -> 4 -> 5 -> 6 -> 7 and we want to insert 3 after 2. The list does this in clear steps:

1. Step 1 — Create the new block. A fresh memory block holding the value 3 is created on its own, not yet connected to anything.
2. Step 2 — Attach the new block to the next node. The new 3 block is pointed at node 4 (the node that used to come right after 2). Now 3 knows who comes after it.
3. Step 3 — Attach the previous node to the new block. Node 2 is changed so that it now points to 3 instead of 4.

After these steps the chain reads 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, and 3 is sitting in exactly the right place. Notice that nothing else moved. We only rewired two pointers. Deletion works the same way in reverse: to remove a node, you just make the previous node point past it to the next one.

Advantages

• Dynamic size: The size is not fixed. The list can grow or shrink during runtime, exactly when you need it to.
• Efficient performance: Inserting or deleting the first node is an O(1) operation — instant, no matter how big the list is.

Limitations

A linked list is not perfect for everything. It shines in specific situations but has trade-offs:

• Extra space: Each item needs a little extra memory compared to an array, because every node must also store the location of the next node.
• Traversal: Reaching an item is slower than in an array. An array lets you jump straight to position n using its index. A linked list cannot do that — to reach the item at position n, you must start at the front and walk through every item before it.

A linked list is the most basic but also one of the most important data structures. Almost every other data structure builds on its ideas, so if there is one structure you absolutely must master, it is the linked list.