This article was done using my notes from Aditya Y. Bhargava from grokking algorithms (2016).
Bhargava A.Y. (2016). “Grokking Algorithms”
Arrays and linked lists
Arrays
Sometimes you need to store a list of elements in memory. Should you use an array or a linked list ? Let’s say we are using a todo list. Using an array first, you would store each todo continuously in memory. It means right next to each other.
Now suppose you want to add another todo in your list, but the next space in memory is taken by something else. According to Bhargava, “It’s like going to a movie with your friends and finding a place to sit, but another friend joins you, and there’s no place for them. You have to move to a new spot where you all fit.”. In the same manner, you need to ask your computer for a different chunk of memory that can fit your todos.
Similarly, adding new items to an array can be a big pain. If you are out of space and need to move a new spot in memory every time, adding a new item will be really slow.
Linked lists
With linked lists, your items can be anywhere in memory. Each item stores the address of the next item in the list. A bunch of random memory addresses are linked together. As such, adding an item to a linked list is easy, you can add it anywhere in memory and store the address of the previous item.
With linked list, you pretty much never have to move your items.
What are arrays good for then ?
Suppose you want to access the last item in a linked list. You have to go to item #1 to get the address of the following then, then on and on and on to the last item. Linked list are great if you are going to read all the items one at a time.
Arrays are different. You know the address for every item in your array. You can access anytime more efficiently than linked list would allow you.
Big O
| Arrays | Lists | |
|---|---|---|
| Reading | O(1) | O(n) |
| Insertion | O(n) | O(1) |
| Deletion | O(n) | O(1) |
Inserting into the middle of a list
Insertion are very efficient with linked list. It is as easy as changing what the previous element points to. But for arrays, you have to shift all the rest of the elements down. And if there is no space available in memory, you might have to copy everything to a new location.
Deletions
Again, linked lists are better, because you just need to change what the previous elements points to. With arrays, everything needs to be moved up when you delete an element.
Which are used more ?
Obviously, it depends on the use case. But arrays see a lof of use because they allow random access. Linked list can only do sequential access. Arrays are often faster at reads beause they provide random access.