Data structures comparison - arrays, linked lists, hash tables, tries

 

Arrays:

- insertion is bad - lots of shifting to fit an element in the middle (except for inserting at the end of the array, anywhere other than the end of the array is not so great)

- deletion is bad - lots of shifting after removing an element (except for deleting from the end of the array, unless we don't care about leaving empty gaps, which we usually don't want)

- lookup is great - random access, constant time 

- relatively easy to sort

- relatively small size-wise

- stuck with a fixed size, no flexibility

Linked lists:

- insertion is easy - just tack onto the front

- deletion is easy - once you find the element

- lookup is bad - have to rely on linear search

- relatively difficult to sort - unless you are willing to compromise on super-fast insertion and instead sort as you construct

- relatively small size-wise

Hash tables:

- insertion is a two-step process - hash, and then add

- deletion is easy - once you find the element

- lookup is on average better than with linked lists because you have the benefit of a real-world constant factor

- not an ideal data structure if sorting is the goal - just use an array

- can run the gamut of size

 

source: harvard cs50 david malan