What are the main differences between an array and a linked list, and when would you choose each?

An array stores items side by side, so access by index is O(1) and it is cache friendly, but inserting or deleting in the middle is O(n) because items have to shift. A linked list stores nodes connected by pointers, so inserting or deleting at a known node is O(1), but reaching the i-th item is O(n) and each node carries pointer overhead. Choose an array (or dynamic array) by default, and a linked list when you insert and remove at known positions often, such as the recency list inside an LRU cache.

Design a data structure that supports insert, delete and getRandom, all in O(1) average time.

Combine a dynamic array with a hash map from value to its index in the array. Insert appends to the array and records the index. getRandom picks a random index. Delete looks up the index, moves the last array element into that slot, updates its index in the map, then pops the last element and removes the deleted value from the map. Every operation is O(1) on average.

Given a list of words, return the k most frequent. Which data structures would you use and why?

Count frequencies with a hash map in O(n). Then keep a min-heap of size k keyed by frequency: push each word, and pop the smallest whenever the heap grows past k. The heap always holds the current top k. This is O(n log k) time and O(n) space. Bucket sort by frequency is an O(n) alternative because frequencies are bounded by n.

Implement an LRU cache with get and put in O(1).

Use a hash map from key to a node in a doubly linked list. The list is ordered by recency, most recent at the head. get finds the node through the map and moves it to the head. put either updates and moves an existing node, or inserts a new node at the head, and if the cache is over capacity removes the node at the tail and deletes its key from the map. All operations are O(1).

Numbers arrive one at a time. After each one, return the median of everything seen so far.

Keep two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced so their sizes differ by at most one. Insert into the correct heap, then move the top element across if the sizes become unbalanced. The median is the top of the larger heap, or the average of both tops when they are equal in size. Insert is O(log n) and finding the median is O(1).

Data Structures & Algorithms: The Big Picture

You don't need to memorise 50 data structures

Most people learn data structures as a long list of names to remember. Interviewers are not testing the list. They are testing whether you can answer one question:

Which operations does this problem need to be fast, and what am I willing to pay for that?

Every data structure is just a different answer to that question. Once you see it that way, the list stops being a list and becomes a small set of trade-offs you can reason about.

Try it: the data structure race

Pick a scenario and watch six data structures handle the same sequence of operations on 1,000 items. Each bar is the total work done so far. Notice that the winner changes with the scenario.

Data structure race

Step 18 of 18 · Press Space to play, arrow keys to step

Mostly lookups by name, a few new contacts

Final totals

Total steps so far, on a log scale. Green means fewest steps for this operation, red means most.

Finished. Hash map did the least work (16 steps) and Min-heap the most (14,046 steps), about 878 times more. Change the scenario and the winner changes too.

items:: 1,000
operations:: 16 / 16
winner:: Hash map

Speed

Things to try:

Phone book (mostly lookups): the hash map wins by a mile, because finding by key is O(1) on average.
Leaderboard (smallest first, then a sorted list): now the hash map struggles. It has no idea about order, so getting the smallest item means checking every entry.
Task queue (always take the most urgent): the heap and the balanced tree pull ahead. This is exactly the job a priority queue is built for.

The five facts that matter most

1. Every data structure is a trade-off

There is no best data structure. Each one makes some operations cheap by making others expensive, or by using more memory. A hash map gives O(1) lookups but forgets order. A sorted array gives O(log n) search but O(n) inserts.

2. Know the cost of the core operations

For any structure, you should be able to say the cost of these operations without thinking:

Structure	Access by index	Find by value	Insert	Delete	Smallest item
Array (unsorted)	O(1)	O(n)	O(1) at the end, amortised	O(n)	O(n)
Sorted array	O(1)	O(log n)	O(n)	O(n)	O(1)
Linked list	O(n)	O(n)	O(1) at the head	O(1) once found	O(n)
Hash map	Not supported	O(1) average	O(1) average	O(1) average	O(n)
Balanced BST	O(log n) with subtree sizes	O(log n)	O(log n)	O(log n)	O(log n)
Binary heap	Not supported	O(n)	O(log n)	O(log n) for the top	O(1)

"Amortised" means a dynamic array occasionally copies everything into a bigger block, but averaged over many appends each one costs O(1). A balanced BST only supports access by index if every node also stores the size of its subtree.

3. Memory layout: contiguous or linked

Everything in memory is either stored side by side (arrays) or connected by pointers (linked lists, trees, graphs).

Contiguous storage gives O(1) access by index and is fast in practice because the CPU cache loads neighbouring items together.
Linked storage makes inserting and removing cheap once you are at the right spot, but you cannot jump to the 500th item directly.

Most other structures are built from these two building blocks. A hash map is usually an array of buckets. A heap is a tree stored inside an array.

4. Every structure keeps one rule (its invariant)

A data structure is defined by the rule it promises to keep true after every operation:

A sorted array keeps items in order.
A binary search tree keeps smaller values on the left and larger on the right.
A min-heap keeps every parent smaller than or equal to its children. A max-heap does the opposite.
A hash map keeps every key in the bucket its hash points to.

The operations exist to restore that rule after a change. If you can state the invariant, you can usually work out the operations yourself in an interview.

5. What you need versus how it is built

Separate the abstract data type (what operations you need) from the data structure (how you implement them):

You need (abstract type)	Typical implementations
List	Dynamic array, linked list
Stack (last in, first out)	Dynamic array, linked list
Queue (first in, first out)	Circular buffer, linked list
Map or set (find by key)	Hash table, balanced BST
Priority queue (always the smallest or largest)	Binary heap

In an interview, say it in that order: "I need a priority queue here, so I'll use a binary heap."

How to categorise data structures

The most common way is by shape:

Category	Members	Reach for it when
Linear	Array, dynamic array, linked list, stack, queue, deque	Order of items matters, or you process items one after another
Hash-based	Hash map, hash set	You look things up by key and do not care about order
Trees	BST, balanced trees (AVL, red-black), heap, trie, B-tree	You need order, hierarchy, the minimum or maximum, or prefix search
Graphs	Adjacency list, adjacency matrix	Items are connected to each other: roads, friends, dependencies

A second lens, which is often more useful when solving a problem, is how you get to an item:

You get items by...	Use
Position	Array
Key	Hash map (or a BST if you also need order)
Order or priority	Heap, BST, sorted array
Most recent first	Stack
Oldest first	Queue
Relationship	Graph or tree

How to categorise algorithms

Algorithms can be grouped by the problem they solve (sorting, searching, graphs, strings). For interviews, it is far more useful to group them by technique, because the problem statement usually hints at the technique.

Technique	Core idea	Signals in the problem	Classic examples
Hashing	Store what you've seen so you can check it in O(1)	"pairs that sum to", "duplicates", "count frequency"	Two Sum, group anagrams
Two pointers	Move two indexes towards or alongside each other	Sorted array, "pair", "reverse", "palindrome"	Container with most water
Sliding window	Keep a moving range and update it in O(1)	"contiguous subarray or substring", "longest", "at most k"	Longest substring without repeats
Binary search	Halve the search space each step	Sorted input, or "find the minimum value that works"	Search in rotated array
Divide and conquer	Split, solve the halves, combine	Problem splits cleanly into independent halves	Merge sort, quicksort
Tree and graph traversal (BFS, DFS)	Visit everything reachable	Grid, network, tree, "connected", "shortest steps"	Number of islands
Heap or top-k	Keep only the best k items	"k largest", "k closest", "merge k sorted"	Top k frequent elements
Greedy	Take the best local choice	Scheduling, intervals, and you can argue the local choice is safe	Meeting rooms, jump game
Dynamic programming	Reuse answers to overlapping subproblems	"number of ways", "minimum cost", "longest", choices at each step	Coin change, edit distance
Backtracking	Try a choice, recurse, undo	"all combinations", "all permutations", constraints to satisfy	N-Queens, subsets

A good habit: before writing code, say out loud which category the problem belongs to and why. Interviewers reward that reasoning even if your first guess changes.

A study order that works

Each step builds on the previous one:

Arrays, strings and hashing
Two pointers and sliding window
Stacks and queues
Linked lists
Recursion, trees and binary search trees
Heaps and top-k problems
Graphs: BFS and DFS
Binary search on the answer (guess a value, check it, halve the range)
Greedy, then dynamic programming and backtracking

How to talk about data structures in an interview

Start from the operations: "I need fast lookup by id and the ability to get the oldest item."
Pick the structure that makes those operations cheap, and name the trade-off you are accepting.
Give time and space complexity for the main operations, including average versus worst case for hash maps.
If no single structure fits, combine two. Many classic problems are solved with a hash map plus something else.

Where you meet these ideas in real systems

The same trade-offs from the lesson show up everywhere in the software you use every day.

Undo in your editor is a stack

Every change you make is pushed onto a stack. Pressing undo pops the most recent change. Redo usually keeps a second stack of the changes you undid.

Message queues and print queues are queues

Systems like RabbitMQ, Amazon SQS and the print queue on your computer process work in the order it arrived, first in, first out. A queue is what makes "fair" processing possible.

Caches combine a hash map with a linked list

A least-recently-used (LRU) cache needs two things to be fast: find an item by key, and know which item was used longest ago. No single structure does both, so caches pair a hash map with a doubly linked list. Java's LinkedHashMap can work this way, and Python's functools.lru_cache uses the same idea.

Database indexes are trees

When a database looks up rows by a column, it usually walks a B-tree index, a tree with many children per node, designed so each node fits in one disk page. The ordering is what makes range queries such as "all orders this month" fast.

Maps and navigation are graphs

Roads are edges and intersections are nodes. Route planners run shortest-path algorithms such as Dijkstra's algorithm or A* over that graph, usually with a heap to always expand the closest unexplored point next.

Autocomplete uses prefix trees

A trie stores words character by character, so every word starting with "inte" sits under the same branch. That makes "suggest words starting with what I typed" fast.

The takeaway

Real systems are rarely one data structure. They are a few simple structures combined so that every operation the product needs is cheap.