December 20, 2017 · Computer Science Data Structures

Linked Lists vs Arrays, pt2

Read part 1.

We can also compare linked lists and arrays through the lens of dynamic vs static data structures. Linked lists are a dynamic data structure, meaning it has the flexibility to keep growing in size. As long as there's still enough memory for just one more extra node, you can keep growing a linked list. On the other hand, arrays are a static data structure, which means its size is fixed. If you program in Javascript or Ruby or Python, this fact may come as a surprise to you. High-level languages hide the implementation details of the array from you, but all arrays have a fixed size under the hood.

A more nuanced look at inserting into an array

Remember when we said last time that adding to the end of an array is an O(1) operation? Well this is true, as long as we still have room in our array. But what if the size of our array is fixed at 20 items, and there are already 20 items in there? In that case, we need to find another chunk of contiguous space in memory that can accomodate more than 20 items. Let's say we want to expand our array size to 40 items just to be safe. Once we find enough space to accomodate 40 items, we have to copy over all the array items in the old space into our new space. Now we can insert our new item (the 21st one) into the new and expanded space. And finally, we can delete all the array items from the old space since we now have another copy of the array elsewhere.

The thing is, this copying over process is an O(N) operation. Moreover, we need enough space to accomodate both arrays (a total of 60 items) while we're performing this copying over process. That's pretty expensive, and we might not always have that much space available. Compare this to a linked list, where all that's required to add a new item is enough space and memory to accomodate just one more node.

The takeaway of all this is that memory allocation may play a significant role in considering which data structure to use. In some cases, it may be more advantageous to use a linked list if you can't afford to pay the costs of the copying over process that you periodically must perform with arrays. This is especially true if you're dealing with very large datasets. Keep this in mind whenever you have to make a choice between using a linked list or an array.

That's it!

This concludes our short foray into the differences between linked lists and arrays. I hope you found this discussion useful. We'll resume our exploration of data structures next time by talking about stacks.