Monday, October 3, 2011

Array vs linked list

A few reasons why Array is better
  • In array, we the provision of random access. But in linked list, the nodes can only be sequentially accessed. 
  • Better locality - Whenever the OS brings data into memory, it loads a whole page. Hence less page fault occurs. With linked list, different parts of the linked list are stored at different parts of memory. Hence branch Prediction doesn't work as well with linked list. This causes the pipeline to be flushed more often which result in poor performance.
  • In linked list, the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element.

A few reasons why Linked List is better
  • It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
  • 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