Arrays vs Linked Lists: An In-depth Comparison and Understanding
In the programming universe, two core data structures will frequently cross your path: arrays and linked lists. They have distinct characteristics, benefits, and cases where one might outshine the other. We've previously explored arrays when we delved into binary search. If you need a refresh, don't hesitate to revisit our binary search article.
Before we dive into arrays and linked lists, make sure you're comfortable with Big O notation--it will greatly simplify the performance analysis in this tutorial. You can brush up on it here.
The Gym Locker Analogy: Computer Memory Explained
Think of computer memory as an expanse of gym lockers, each with its unique address. Want to store something? You get a locker. Need to store more? You'll need more lockers.
Similarly, when you save an item in computer memory, the computer assigns it an address. For multiple items, you'll utilize arrays or linked lists.
Arrays vs. Linked Lists: Where to Store Your Groceries?
To illustrate, let’s suppose you're building a grocery shopping app. Storing items requires either an array or a linked list. The former stores items side by side in memory.
However, arrays can pose challenges. Suppose you need to add another item, but the next memory slot is occupied. You'll need to find a larger memory region, move all items, and add the new one. Quite the hassle, right?
A possible solution is to reserve more space than required, offering room for additions. But that approach wastes memory space if unused, and if the space fills up, you're back at square one.
Linked Lists: The Treasure Hunt of Data Structures
Linked Lists offer a different approach. They allow your items to be located anywhere in memory, with each item pointing to the next one. Similar to a digital treasure hunt, you hop from one address to the next. This means you can add items anywhere in memory without relocating existing ones.
Pitfall of Linked Lists and the Edge of Arrays
You know how "top 10" websites have a sneaky tactic for getting more views? Instead of displaying the full list on a single page, they place one item per page and make you click "next" to view the subsequent item. It's annoying, but it earns them more from ad revenue.
It would be considerably more user-friendly if the entire list were on one page, and you could click on each item's name for more details.
Linked lists have a similar pitfall. Suppose you want to read the last item of a linked list. You can't do that directly as you don't know its address. Instead, you have to go to item #1 to fetch the address for item #2, then move to item #2 to get the address for item #3, and so on until you reach the last item.
Linked lists work perfectly fine if you want to read all items, one by one. However, if you want to jump from one item to another, linked lists score low on convenience.
Arrays, on the other hand, operate differently. If you want to read the last item of an array, you can directly go to the address of the last item. No need to read all the items preceding it.
In an array, elements are assigned an index. This indexing begins at 0, not 1. Take this array, for instance, the number 20 is at index 1.
[10, 20, 30, 40]
The number 10 is at index 0. This might confuse people initially, but that's how it works.
The position within an array is referred to as the index. The index of the number 20 is 1. The index of the number 10 is 0. The index of the number 40 is 3.
Here's how arrays and linked lists compare for common operations:
| Arrays | Linked Lists | |
|---|---|---|
| Reading | O(1) | O(n) |
| Insertion | O(n) | O(1) |
Inserting an Item in the Middle of the List
Imagine you want your grocery list to be alphabetically ordered. That means now, you'll want to add items in the middle of the list - simply appending the item at the end of the list might violate the alphabetical order.
What's the better choice for inserting elements in the middle of a list: arrays or linked lists? Using linked lists, you just need to adjust what address the preceding item points to.
For arrays, however, you must shift all the items below the insertion address. If there isn't enough room, you'll have to request more space and move every item over there.
In essence, linked lists have the upper hand when it comes down to inserting items in the middle of the list.
Deletions
What if you want to delete an item? Once again, linked lists make this easier as you just need to adjust what address the preceding item points to.
With arrays, everything needs to be shifted when an element gets eliminated. Unlike insertions, deleting elements will always be successful. Insertion may fail when there isn't enough memory space.
Here are the runtimes for the most common operations for arrays and linked lists:
| Arrays | Linked Lists | |
|---|---|---|
| Reading | O(1) | O(n) |
| Insertion | O(n) | O(1) |
| Deletion | O(n) | O(1) |
In Conclusion: Arrays vs Linked Lists?
Which one is more frequently used - arrays or linked lists? Clearly, it hinges on the scenario they're used in. However, arrays are more commonplace since they allow random access. There are two types of access: sequential and random.
Sequential access means reading elements one by one, starting with the first. Linked lists can only manage sequential access. If you want to read the tenth element of a linked list, you first need to read the preceding nine elements to get the tenth element's address.
Random access, on the other hand, lets you jump straight to the tenth element.
Random access is much needed in many cases, leading to wider usage of arrays. Arrays and linked lists are employed to build other data structures, such as queues, stacks, trees, and graphs.