Why Arrays Struggle: The Problem That Leads Us to Linked Lists

Why Arrays Struggle: The Problem That Leads Us to Linked Lists

Before learning about a linked list, it helps to first understand a real problem that programmers run into. Once you feel the pain of that problem, the solution makes a lot more sense.

A simple, everyday need

When we write programs, we often need to store a group of related items that we can read one after another, in order. For example, the names of all the students in a class:

Ram Shyam Hari Krishna Neha Nirav

At first this looks easy. Why not just use an array? An array is a row of boxes placed side by side in memory, where each box holds one item. If there are 6 students, we make an array of size 6 and put one name in each box.

This works perfectly... as long as nothing changes.

Problem 1: A new student joins

Imagine a new student, Sundar, joins the class. Now we want 7 names, but our array only has 6 boxes. Can we just add one more box at the end?

No. This is the key limitation: an array's size is fixed when it is created and cannot be changed later. The boxes sit in one continuous stretch of memory, and there is no guarantee that the box right after our array is free.

So the only way to "grow" the array is to do all of this:

1. Create a brand new array, one box bigger (size 7 instead of 6).
2. Copy every existing name from the old array into the new array, one by one.
3. Put the new name Sundar into the last box.
4. Throw away the old array and use the new one.

That is a lot of work just to add one name.

Problem 2: A student leaves

Now imagine Ram leaves the class. We have the same trouble in reverse. We cannot simply remove a box from the middle and have the array close the gap by itself.

Instead we must:

1. Create a new, smaller array (size 5 instead of 6).
2. Copy over every name except Ram.
3. Use the new, smaller array.

Again, removing one name forces us to rebuild the whole collection.

Problem 3: Inserting or deleting in the middle

The examples above added or removed items at the ends. But what if we need to insert or delete a name somewhere in the middle? An array cannot make space in the middle or close a gap in the middle on its own. The items live in side-by-side memory boxes, so you would have to shift many items around or copy everything again. In short, you cannot insert or delete an item in place in an array.

Why this is inefficient

Let's measure how bad this is. We use time complexity (how much work the steps take) and space complexity (how much extra memory we use). Here n means the number of items.

• Space complexity O(n): To add or remove just one item, we build a whole new array the size of all the data. Reserving memory for n items when we really needed room for just one is wasteful.
• Time complexity O(n): We walk through the entire array and copy every element into the new array, even though only one item actually changed. The more students we have, the slower this gets.

The fundamental problems with arrays

Putting it all together, an array is a poor choice when items are added and removed often, because of two built-in limits:

• Fixed size: The size is decided when the array is created and cannot be changed afterward.
• Insertion and deletion: Array items sit in contiguous (next-to-each-other) memory blocks. Because the size is fixed, we cannot truly insert or delete items — we can only overwrite what is already there.

So here is the question that points us forward: what if we had a "magical" data structure that could grow, shrink, and let us insert or delete items anywhere — quickly and without wasting memory? That data structure is the linked list, and that is what we will build next.