Why Linked List Data Structure

Back to: Data Structures and Algorithms Tutorials

Why Linked List Data Structure?

In this article, we will learn why we need the linked list data structure. Please read our previous section articles where we discussed Matrices. We will discuss the following two things.

1. Problem with Arrays
2. Difference between Array and Linked list.

Problem with Arrays

The 1^st problem with an array is that it is of fixed size. Whenever you are creating an array, you have to mention the size and later on, you cannot increase or decrease the size of an array. So once the array is created its size remains the same.

Why size is the problem?

If we know the size or the number of elements then we can create an array of that particular size. If we don’t know how many elements, we are going to store during the runtime of a program then we cannot decide the size of an array. If we take some random size then that size may be either insufficient or it may be of extra size. For example, I’m not sure how many elements I’m going to store. So, in the program, if I declare an array of size 10,

int A [10];

Then in the above array, I cannot store more than 10 elements. Suppose we have more than 10 elements during runtime then we cannot store them and if we have just 2 or 3 elements then a lot of space in that array will be wasted.

Programmers write programs or applications for whom? For users who are going to use the programs. People who use other programs will decide how many elements they are going to enter into our program.

So what would be the list size or array size? We don’t know. So, at runtime, the list size will be decided but at coding time or compile time we have to give the size. This is the problem with arrays. Next, let us see the difference between Array and Linked list.

Difference between Array and Linked list

We already know that we can create an array either inside the stack or we can create it inside the heap memory. So, for creating an array inside the stack we will write

int A [5];

In this case, the array will be created inside the activation record of the main function. Then if you want to create an array inside the heap memory then we should take a pointer as follows.

int *p = new int [5];

So, the size can be taken at runtime. That’s the benefit. The benefit of creating an array inside the heap is that all these locations will be contiguous and you can access them with an integer index. So randomly you can reach any element.

Now coming to the linked list.

Why Linked List Data Structure?

We don’t want a fixed-sized array like the above one we discussed because we don’t know the size. Who is using our program and what is his requirement and how many elements does he is having? We don’t know.

Let him go on giving the elements as many elements as he wants. So let the user give as many elements as he wants. And one more thing, let the user add more elements and also remove the element.

So, we want some data structure that should grow and reduce in size. That means we want a variable-size data structure. So, for that, we are just sharing the idea of a linked list. We must create memory in the heap during runtime and we should use linking for making it a linked list.

So let us share the idea for that. See for allocating memory inside the heap, we generally used a pointer and with one pointer we have allocated five spaces. Now we will take one pointer, let us call it ‘first’. Now we want to store one element and this pointer will be pointing on that space. For a better understanding, please have a look at the below image.

So that is for storing just one element. So, with this pointer, we can point only to one element.

What about next.

If we want more, so along with this element we would also allocate space for a pointer to the next element. So right now, there is nothing so let it set to be null. Now we have one more point ready if we want one more element. Then again allocate the memory as

Here you store the element. Then the new memory will be pointed to the next one. If there is no element then set it to be null. So, we can call that block a node. Suppose we have one more element, then again create a node and it will contain the value and the pointer to the next element. So, every element will bring its own memory and point to the next element. This is how we formed a linked list inside the heap.

Now suppose you want to remove any element then change the pointer to another element and if you haven’t any element then point the previous as null. So, it’s easy to insert something in between by just changing links.

This is the data structure that is more flexible than the array and the size can be increased or decreased. You can easily insert the new elements or remove the existing elements from the linked list. There is no meaning in creating a linked list inside the stack.

We create a linked list always inside the heap, so dynamically we look at the memory. If the element is removed then memories are gone. The size is variable.

In the next article, I am going to discuss What Linked List Data Structure is with Examples. Here, in this article, I try to explain Why do we need Linked List Data Structure and I hope you enjoy this Why do we need Linked List Data Structure article.