Pointer Walk

Choosing a Data Structure

Looked up by key? Kept in order? Added at one end or both? A few questions that pick the structure for you.

Data StructuresBeginner9 min read

The question behind every choice

There is no best data structure. Each one makes a few operations very cheap and pays for it by making others expensive. So the useful question is never "which is fastest?". It is:

Which operations will I do most often?

Same data, different questions

Here are four structures holding the same 15 numbers. They are asked eight "is this number here?" questions, and then four "what is the next number after this one?" questions. The bars count how many items each structure had to look at.

Same data, same questions, four structuresInteractive

Items looked at so far (lower is better) · question: is X here?

0
Unsorted array
0
Sorted array
0
Search tree
0
Hash map

Start. Four structures, each holding the same 15 numbers. First question type: is this number here?

For the first kind of question the hash map is unbeatable. It goes straight to the answer. Then the question changes, and it becomes the slowest of the four, because a hash map keeps nothing in order. To find "the next number after 31" it has to look at everything.

The sorted array and the tree were never the fastest, and they never fell apart either.

What each structure makes cheap

StructureCheapExpensive
Dynamic arrayRead by position, add at the end, walk throughInsert or remove at the front or middle, search
Sorted arraySearch, find the nearest value, rangesInsert and remove, because items must shift
Hash mapFind, add and remove by keyAnything involving order
Set"Have I seen this?"Anything involving order
Search treeFind, add, remove, and stay sortedSlower than a hash map for plain lookups
HeapAdd, and remove the smallestFinding anything else
StackAdd and remove at one endReaching anything below the top
QueueAdd at one end, remove at the otherReaching the middle
Linked listInsert or remove once you are at the spotGetting to the spot

A few questions that settle it

Which data structure?Interactive

How will you find an item?

These questions cover the large majority of everyday code and interview problems.

Example

Reading a problem for clues

"Find two numbers that add up to a target." You need to ask "have I seen 7 before?" many times. That is a set or a hash map.

"Keep the 10 highest scores as new scores arrive." You repeatedly need the smallest of your top 10, to compare against. That is a heap.

"Find all bookings between 2pm and 5pm." A range, in order. That is a sorted structure.

"Process jobs in the order they arrived." First in, first out. That is a queue.

When you are not sure

Start with a dynamic array for a list of things and a hash map for looking things up. They are the right answer more often than everything else combined, and they are easy to replace later if measuring shows a problem.

Key takeaways

  • Every data structure makes some operations cheap and others expensive.
  • Choose by the operations you do most, not by a general idea of speed.
  • Hash maps are the fastest way to look up by key, and useless for anything ordered.
  • Sorted arrays and trees answer "next", "nearest" and range questions.
  • When unsure: a dynamic array for lists, a hash map for lookups.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress