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.
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.
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.
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.
We simply pointed our node to "A".
Let me add it next to the letter "B" now.
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.
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.
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.
Top comments (2)
"Side note: We are not considering the time complexity of traversal here but only of the insertion operation."
But isn't that something important to consider?
The reason being that traversal itself is another operation and it also has different techniques.
While, we are only discussing insertion operation right now relatively to arrays.