Linked Lists vs Arrays
Before talking about stacks, it's a good idea to consider a side-by-side comparison of linked lists and arrays. An in-depth comparison like this is useful, since all other data structures are built on top of linked lists and arrays.
The plan is to go operation by operation, and compare linked lists and array in terms of reading, searching, inserting, and deleting. So without any further ado, let's proceed to our showdown!
Round 1: Reads
Reading from an Array
The virtue of an array is that you get random access to any of its indices. This is actually pretty awesome. Think about it. Just by knowing the name of an array, you automatically get O(1) access to all of its values! How does this work under the hood? Well, if you have an array named
myArray, the variable
myArray actually points to the location in memory of the first item of the array. In other words,
myArray points to index 0 of the array. For simplicity's sake, let's say that
myArray points to a location in memory with an address of 506. If you then ask the computer for
myArray, the computer will add 506 + 5. It will then know that you want the value at the address of 511. And now the computer can just go to that location in memory in one step. And this is all thanks to the fact that arrays are contiguous, meaning that all of its items sit side-by-side next to each other in one big chunk of memory. All this means that reading from an array an O(1) operation.
Reading from a Linked List
On the other hand, linked lists are made up of nodes that can be scattered all over the place in memory. The only way to get from one node to the next, is to keep a reference in each node to its successor. And this is exactly what a node is! It's just a collection of data in which some bits represent the node's own value, which can be a char or integer or whatever. And other bits represent the node's successor, which is basically another node. These properties are usually called
next holds the next node's location in memory. In practical terms, that means
next is a variable that points to the next node.
So in order to get to the last node, I need to first visit the head node, then the node after that, then the node after that, then the node after that, ... etc. until I finally get to the last node. Another way of saying this is that linked lists are a sequential access data structure, as opposed to a random access one like with arrays. And so it takes O(N) time to access any particular node in a linked list.
*Winner of Round 1: Reads take O(1) time for arrays and O(N) time for linked lists. So the winner of this round is the array.
Round 2: Search
Searching in an Array
As we saw in our last post, we only get random O(1) access to an array's items if we know the index position we're looking for. But in the case of search, we don't know the index position of what we're looking for. What we're looking for could be at index position 0 or index position 47 or anything in between. This means we basically need to visit every single index position until we find what we're looking for or get to the end of the array. This makes searching in an array an O(N) operation.
Searching in a Linked List
For linked lists, searching is also an O(N) operation, since we need to keep traversing to each next node until we find what we're looking for or reach the tail node.
*Winner of Round 2: Searching takes O(N) time for both data structures, so the result of this round is a tie.
Round 3: Insertion
When it comes to insertions, arrays and linked lists are the same but different. I know, I know.. cryptic much? What I mean is that both arrays and linked lists offer O(1) inserts in the best-case scenario, and O(N) inserts in the worst-case scenario. Where they differ is in what their respective best- and worst- case scenarios are. For arrays, the best-case scenario is inserting at the end. For linked lists, the best-case scenario is inserting at the beginning. And for worst-case scenarios, it's the opposite. For arrays, the worst-case scenario is inserting at the beginning. For linked lists, the worst-case scenario is inserting at the end.
Don't worry, you don't have to memorize all that. Just know that for arrays, the bottleneck is going to be in all the shifting and re-arranging you have to do after the insert itself. And for linked lists, the bottleneck is going to be in all the traversing you have to do to even get to the node in the first place.
Inserting into an Array
Let's apply this knowledge. When we insert at the end of an array, no shifting needs to happen because nothing comes after the last item! So we can perform our insert in a constant number of steps, which means that inserting at the end of an array takes O(1) time.
On the other hand, when we insert at the beginning of an array, we need to shift every single item that comes after it (which is basically all the items). Recall that in order to insert "bread knife" into the beginning of the array below, we had to first shift every other item in order to make room for it. This means that inserting at the beginning of an array takes O(N) time, since we need to shift all items in the array.
Inserting into a Linked List
For linked lists, if we want to insert at the end of the list, we need to first traverse through each node one-by-one until we get to the tail node. Only then can we perform our insertion by swapping some pointers. The insertion itself isn't the slow part since that takes a constant number of steps. What's slow is all the traversing we need to do to even get to that last node in the first place. And since we need to traverse through every single node to get to the tail node, inserting at the end of a list is an O(N) operation.
On the other hand, what if we want to insert at the beginning of a linked list? Remember that we always keep around a reference to the head node. This means that we can always get to the head node in one step, since we always have direct access to it! And once we're there, we just need to change some pointers around and we're done! Insertion completed. And the best part is that no traversing was needed, which makes inserting at the beginning of a linked list an O(1) operation.
Make sense? Just remember: the bottleneck for arrays is shifting, and the bottleneck for linked lists is traversing.
*Winner of Round 3:
- Inserts at the beginning: Takes O(1) time for linked lists and O(N) time for arrays. So linked lists win in this category.
- Inserts at the end: Takes O(N) time for linked lists and O(1) time for arrays. So arrays win in this category.
Round 4: Deletion
You'll be glad to hear that deletions are pretty much no different than insertions! And that makes sense doesn't it? Whether we're inserting or deleting, we still need to shift in the case of arrays or traverse in the case of linked lists. What we do with the pointers may be a little different now since we're deleting, but the bottleneck for each data structure is still the same.
*Winner of Round 4: The conclusion for this round is the same as the last.
- Deletes at the beginning: Takes O(1) time for linked lists and O(N) time for arrays. So linked lists win in this category.
- Deletes at the end: Takes O(N) time for linked lists and O(1) time for arrays. So arrays win in this category.
In conclusion, arrays are better for reads and they also outperform linked lists when it comes to inserts and deletes at the end. But linked lists have an edge over arrays when it comes to inserts and deletes at the beginning. And there's no difference between the two data structures in terms of searches.
So the next time you find yourself in need of a linear data structure, stop and ask yourself: "Will I need frequent index access? Am I going to be doing a lot of inserts/deletes at the beginning? Or perhaps at the end?" Depending on your needs, you may choose to go with either a linked list or an array. And this decision could potentially have significant consequences over the lifecycle of the app. Choose wisely, so that over and over again you'll be able to reap the benefits of your data structure of choice.