DEV Community

Cover image for Are Linked Lists necessary?
Abdul Karim
Abdul Karim

Posted on

Are Linked Lists necessary?

For most beginners, linked lists and arrays are pretty much the same linear data structures. The operations are quite the same i.e. both insert, delete, and access elements. However, there are key differences that you need to consider when selecting one of the data structures and to understand the necessity of linked lists.

I will discuss these differences on the basis of worst-case scenario time complexity mainly. But, before we start, let's recall contiguity.

Contiguity

Arrays have elements that are contiguous i.e. elements are next to each other in the memory. Whether they are static or dynamic, this property always holds.

Array memory block

On the other hand, elements in linked lists are non-contiguous, instead they are generally scattered in different places of the memory. It is a node based data structure where all these nodes are linked together and each node has a reference to its previous or next node depending on the type i.e. singly linked list or doubly linked list.

Linked list diagram

Now, let's take a look at some operations and a data abstract type (DAT) to discuss the necessity of linked lists.

Insertion

Insertion means to add an element to our array or linked list. This can be done at the start (prepend), at the end (append), or at any position you like (as long as it is less than the length).

Let's see what happens when we prepend a letter "G" to an array.

Array diagram

Prepending to an array

Notice how every element moved a step forward because we decided to prepend. The indices (singular: index) also shift respectively. Imagine if we had "n" elements (could be ten, hundred or even a million), how much time would it take?
You guessed it! the time complexity will be Big O of N or O(n).

What would be the time complexity if we append? It's the end, so obviously we will not shift any elements. Therefore, it's time complexity will be O(1).

Let's discuss about linked lists now! Insertion is all about changing the references (or links :D) between the nodes. For the sake of simplicity, I will discuss it using singly linked list. We are going to prepend the letter "G" again.

Prepending to a linked list

We simply pointed our node to "A".

Let me add it next to the letter "B" now.
Inserting in a linked list

Again, we simply removed the "next" reference of "B" from "C" and moved it towards "G". And also pointed G towards the next node "C".

Therefore, the time complexity is always O(1) regardless of the insert position.

Side note: We are not considering the time complexity of traversal here but only of the insertion operation.

Deletion

It's simply the opposite of insertion. When we delete from the start of an array or any other position before the last element, the indices will shift back. Time complexity will be O(n).

Let's delete the letter "A" from our previous array.

Deletion in array

As you can see, all the elements step backwards.

Similarly in a linked list just like insertion, we simply manipulate the references but this time, we remove them.

Deletion in linked list

Deletion in linked list

Time complexity is O(1) similar to insertion.

Random Access

Lastly, let's talk about accessing (or getting) elements both in arrays and linked list.

Random access is the ability to get an element from an array in constant time complexity or O(1). Yup, you read that right it's O(1). But why is this only for arrays and not linked lists?

In linked lists we need to traverse all the nodes until we find our target node, the reason being is that the elements are non-contiguous whilst in arrays, elements are contiguous. We just need to know the offset and we can get any element instantly. Therefore, time complexity of linked lists is O(n).

Data Abstract Types (DAT)

To keep this article short, I will quickly discuss a data abstract type i.e. queue.

Queue follows First In, First Out (FIFO) principle which means we always insert elements at the end, but remove from the beginning. Now, what do you think? If we use an array, and remove an element from the beginning, all the indices will shift which is really bad for the performance. Hence, we go with linked lists.

Conclusion

So, are linked lists necessary? Well, it depends. If your priority is fetching elements frequently then you should go with arrays, however, if you are going to do multiple insertions and deletions like in queue, you should go with linked lists preferably.

Therefore, it's not about the preference, but rather your use case!
Your choice will greatly impact the performance habibi.

Below is a table showing worst-case scenarios for the respective data structures.

Comparing Table

Top comments (0)