⚡ TL;DR: Arrays are fast and compact. Linked lists are not as compact, but adding or removing elements from them can be more efficient!
You probably already know how to use arrays and are familiar with methods like push, pop, etc. The purpose of this issue is to give you an understanding of arrays as a data structure and how they differ from lists.
**Why would you care?* For those who are preparing for a technical interview or would like to deepen your knowledge of computer science, this is the article for you.*
Arrays and lists are easy to mix up, so let’s try to make sense of what the differences are and how they work! ⚙️
You can think of memory as a bookshelf:
Now imagine you got the first four volumes of Game of Thrones 🐉:
This is your array. Now you wouldn’t want to store these volumes separately: if you find volume 1 you want to be able to find volume 2 easily. So you’ll find a place were you can put the four of them together. Luckily, our top shelf has room for exactly four volumes:
You found a spot for these, great. But, surprise! A friend comes over and gives you volume 5 📕
You run to your bookshelf, only to realize, you don’t have any room left next to volume 4 🙁
Reorganizing the bookshelf to make more room near volume 4 would work, but that seems like a lot of effort…
Instead, we’re going to move the first four volumes to a larger empty space. Now we can add the fifth volume!
Phew, that wasn’t easy! 🥵 These volumes are heavy, and you don’t want to go through the hassle of moving all of them every time you don’t have enough room for a new one.
So what are your options here? Well, we tried to do it the array way: put each volume next to each other, and move the entire series when you don’t have enough room for another volume. What if we tried to do it the list¹ way instead?
We’ll need a little bit of setup before getting into this. We are going to assign a letter to each shelf, and a number to each column of book:
Now, each location on our bookshelf has a set of coordinates. For example, the third book of the top shelf is at position A2.
Instead of storing our volumes next to each other, we are going to put the first volume anywhere in the bookshelf:
And now, we’re going to do the same with the second volume. Once we’ve found a location for it, we’re going to add a note next to the first volume with the coordinates of the second volume:
We can do this until we reach the fourth volume, where the note will be empty since we don’t have our fifth volume yet:
We just made a singly linked list: we have a single note next to each book that tells us where to find the next one.
Now you might be thinking, this is great, but why do I have to waste so much space storing those notes?
And you would be right: linked lists take up more space than arrays²! You give up some space, but you don’t have to worry about moving things around to add a volume to your series. As long as you have space for a book and a note, everything’s fine! Removing a volume in the middle is also a lot simpler: if you want to remove volume 2, just change the note after volume 1 with the coordinates of volume 3.
Key takeaway: trade-offs. When discussing the differences between arrays and lists, it is important to understand when and why to use one or the other — knowing this will make you stand out during any technical interview! ✨
[1]: Usually, people use **list* to mean linked list, and more specifically singly linked lists. There are other types of lists, but singly linked lists are the most common type.*
[2]: Technically this might not always be true, because of the way programming languages handles memory allocation for arrays. You can read more about this here.
💡 Tip of the week
You can use git switch - to switch back to your previous branch:
(main) git switch other-branch
(other-branch) git switch -
(main)
🔗 What else is going on in tech?
If you are starting to learn about flexbox in CSS, this might be for you: https://knightsoftheflexboxtable.com/
For all the Rubyist around here, Stripe had some exciting news! https://sorbet.org/blog/2021/07/30/open-sourcing-sorbet-compiler
A beautiful and free library of UI components for Tailwind: https://daisyui.com/
Finally, if GitHub is your daily driver, checkout this new awesome feature! https://twitter.com/DynamicWebPaige/status/1425502379777019909
PS: We would love to know how you felt about this article, did you find it helpful, and are there topics you’d love to see covered? Tag @nspiredTech on Twitter if there’s anything you want to share :-)
Top comments (0)