Choosing the Right Structure

Picking the right data structure is mostly about answering one question: what operations does my program do most often, and how fast does each structure do them? The wrong choice doesn't break your program — it just makes it slow.

Match the Structure to the Operation

• Need fast index access? Use an array (or vector / ArrayList). O(1) lookup by index.
• Inserting and deleting in the middle a lot? Use a linked list. O(1) insert/delete given a node, but O(n) to find one.
• Need "most recent first" behavior? Use a stack. Undo, backtracking, parsing.
• Need fair "first come, first served"? Use a queue. Job scheduling, BFS.
• Need fast membership tests? Use a set or hash table. O(1) average lookup.

Decision Walkthrough

Ask yourself, in order:

1. Do I look things up by position (index)? Array.
2. Do I look things up by identity / key (does this value exist)? Set / hash table.
3. Do I always work on the most recent item? Stack.
4. Do I always work on the oldest item? Queue.
5. Am I doing tons of inserts/deletes in the middle? Linked list.

You'll often combine these — a queue inside a graph search, a hash table alongside an array.

Common Trade-Offs

Arrays are tightly packed in memory, so iterating is cache-friendly and fast. Linked lists scatter nodes around memory, so traversal is slower in practice even though the Big O is the same.

Hash tables give you O(1) average operations but cost more memory and have unpredictable worst-case timing. Sorted arrays support O(log n) binary search but are slow to insert into.

Try It Yourself

• You're building a browser back/forward feature. Which structure(s) and why?
• You need to track which usernames are taken from a list of millions. Which structure?
• You're processing customer orders in the order they arrive. Which structure?