data structures - Array versus linked-list

Why would someone want to use a linked-list over an array?

Coding a linked-list is, no doubt, a bit more work than using an array and one may wonder what would justify the additional effort.

I think insertion of new elements is trivial in a linked-list but it's a major chore in an array. Are there other advantages to using a linked list to store a set of data versus storing it in an array?

This question is not a duplicate of this question because the other question is asking specifically about a particular Java class while this question is concerned with the general data structures.

Answer

• It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.


• As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.


• Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.


• As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.