Sunday, 26 February 2017

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.


No comments:

Post a Comment

c++ - Does curly brackets matter for empty constructor?

Those brackets declare an empty, inline constructor. In that case, with them, the constructor does exist, it merely does nothing more than t...