2020-02-19

Dynamic Array vs. Linked List (or: Stop Asking This in Interviews)

I'm sure you all remember dynamic arrays and linked lists from your DS/A class(es) at school. If not (and just make sure we're all on the same page), I'll quickly summarize here.

Dynamic arrays store their elements contiguously in memory. They allocate one giant chuck of memory on the heap, and store everything one after another in that chunk of memory. This gives them good cache locality. They reallocate if they need to add more elements than they have room for. (This piece is important, remember it for later.) std::vector is a C++ example of a dynamic array.

Linked Lists store their elements in nodes (each of which is a single element and a pointer to the next element). Because each node is allocated its own chunk of memory, a linked list never has to resize like a dynamic array does. std::forward_list is a C++ example of a linked list. (Similar stuff applies to a doubly linked list as well though.)

Pros & Cons of Dynamic Array (Compared with Linked List)

Pros:

• Much better cache locality than a linked list. (Really. Cache locality is so important for performance.)
• Random access of elements (compared with linear time for linked list).
• Uses less space, because we don't need to store an extra pointer for each element.

Cons:

• Insertions and deletions invalid iterators in a dynamic array (since any insertion or deletion could cause it to resize. (Note that this is not the case with a linked list, since you never have to reallocate memory.)

And that's it. Insertion being constant time for a linked list doesn't even matter since linked lists are so slow overall. (Look up benchmarks, much smarter people than me have beaten this horse to death already.) It turns out that having a cache miss every single time you look at a new element really slows you down. (And it just gets worse as CPUs get faster.)

Conclusion

Please stop asking this question in interviews. It's a bullshit question. The only valid answers are:

• "Performance doesn't matter here but a linked list will give me cleaner code" (Probably the best reason.)
• "We benchmarked vs. a dynamic array and turns out for our super specific use case a linked list was faster." (Sure, if you say so.)
• "We needed the iterators to still be valid after inserting or deleting." (Might overlap with the "clean code" case above.)
• "We were implementing malloc." (What year is it again?)

Not: "My data-structures and algorithms prof said so but I never bothered to benchmark it..."