Data Structures: The Intuition-First Guide
Data structures answer one fundamental question:
How should I organize information so that the operations I care about become easy?
The same data can be stored in many ways.
Suppose we have:
Alice → 92
Bob → 81
Carol → 95
If we frequently ask:
"What is Bob's score?"
a hash map is excellent.
If we repeatedly ask:
"Who has the highest score?"
a heap / priority queue may be better.
If we need:
"Keep everyone sorted by score while people are continuously added."
a balanced search tree may make more sense.
If these people were locations connected by roads, suddenly the natural representation becomes a graph.
So don't memorize data structures as isolated definitions.
Think:
Data
↓
What operations do I need?
↓
What structure makes those operations cheap?
1. Arrays
An array is probably the most fundamental data structure.
Imagine numbered lockers:
index: 0 1 2 3 4
+----+----+----+----+----+
value: | 12 | 27 | 5 | 91 | 33 |
+----+----+----+----+----+
If you want element 3, the computer can directly calculate where it lives in memory.
numbers[3]
returns:
91
This is why array indexing is approximately:
O(1)
The computer does not search from the beginning.
It effectively calculates:
address = start_address + index × element_size
That is the important intuition.
Arrays are good when
You want:
fast random access
compact storage
sequential processing
good CPU cache performance
matrices, images, sensor buffers, tensors, etc.
For example, an RGB image is essentially structured arrays:
image[row][column][channel]
A LiDAR scan may also begin life as an array of measurements.
The weakness of arrays
Suppose:
[10, 20, 30, 40]
and you want to insert 15 after 10.
You may need:
[10, _, 20, 30, 40]
↓
[10, 15, 20, 30, 40]
Elements may have to move.
So inserting in the middle is usually:
O(n)
2. Strings
A string is essentially a sequence of characters.
"ROBOT"
can be thought of approximately as:
['R', 'O', 'B', 'O', 'T']
Strings deserve special treatment because text-processing operations appear everywhere.
Examples:
robot_name = "atlas"
We might ask:
length?
contains "las"?
starts with "at"?
find a pattern?
split words?
compare strings?
Important intuition
A string may look like one object to us:
"autonomous"
but algorithms often see a sequence:
a u t o n o m o u s
0 1 2 3 4 5 6 7 8 9
Therefore many string algorithms are really clever ways of processing sequences.
This becomes important in:
parsers
compilers
search engines
NLP
log processing
communication protocols
3. Linked Lists
Imagine train cars.
[A] → [B] → [C] → [D]
Each node contains:
value
+
pointer to next node
Unlike an array, the nodes do not need to sit next to each other in memory.
A node might conceptually be:
class Node:
value
next
Why linked lists exist
Suppose:
A → B → C
and you want:
A → X → B → C
You don't shift every element.
You simply change pointers.
A → X
X → B
Insertion can therefore be extremely cheap when you already know the location.
But there is a tradeoff
Want the 500th element?
An array says:
jump directly there
A linked list says:
start at node 1
follow pointer
follow pointer
follow pointer
...
So random access is:
O(n)
Doubly linked lists
Sometimes nodes point both directions:
A ⇄ B ⇄ C ⇄ D
Each node stores:
previous
value
next
Useful when traversal or removal is needed in both directions.
4. Stacks
A stack follows:
Last In, First Out — LIFO
Think of plates.
┌───┐
top → │ C │
├───┤
│ B │
├───┤
│ A │
└───┘
We added:
A
B
C
but remove:
C
B
A
Main operations:
push
pop
peek/top
usually:
O(1)
Why stacks matter
Stacks appear naturally whenever things must be completed in reverse order.
Examples:
Function calls
main()
A()
B()
The runtime remembers:
main
A
B ← currently executing
When B finishes:
pop B
then return to A.
This is essentially the call stack.
Undo
You perform:
type "hello"
delete word
paste text
An editor can push each operation onto a stack.
Undo pops the most recent operation.
Depth-first search
DFS naturally uses a stack.
5. Queues
A queue follows:
First In, First Out — FIFO
Think of people waiting for coffee.
OUT ← [A][B][C][D] ← IN
A arrived first, so A gets served first.
Operations:
enqueue
dequeue
front
usually:
O(1)
Where queues appear
Queues are everywhere in systems:
network packets
job scheduling
ROS messages
event processing
task queues
printer jobs
And one famous algorithm:
Breadth-First Search uses a queue.
Stack vs Queue
This distinction is worth permanently remembering.
STACK
Last thing added comes out first.
A B C
↑
remove C
QUEUE
First thing added comes out first.
A B C
↑
remove A
That tiny behavioral difference creates very different algorithms.
6. Hash Maps
A hash map stores:
key → value
Example:
student_scores = {
"Alice": 95,
"Bob": 82,
"Carol": 91
}
Then:
student_scores["Bob"]
quickly returns:
82
Average lookup is approximately:
O(1)
This makes hash maps incredibly important.
How does that work?
Suppose we have a key:
"Bob"
A hash function transforms it into a number:
hash("Bob") → 739182...
That number determines approximately where the value should be stored.
Conceptually:
"Bob"
↓
hash()
↓
739182
↓
bucket 2
↓
82
So instead of searching:
Alice?
Carol?
Dave?
Bob!
we calculate where Bob should probably live.
Collision
Two keys can sometimes map to the same bucket.
hash("Bob") → bucket 3
hash("John") → bucket 3
This is called a collision.
Real hash tables have strategies for handling this.
You don't normally need to think about the implementation details when using one, but understanding collisions explains why hash-map operations are described as:
average O(1)
rather than magically guaranteed constant time in every conceivable case.
Use hash maps when
You need:
ID → object
name → user
word → count
coordinate → cached value
sensor ID → sensor state
Example word frequency:
{
"robot": 14,
"sensor": 8,
"camera": 5
}
7. Sets
A set stores unique values.
visited = {"A", "B", "C"}
There are no duplicates conceptually.
A
B
C
not:
A
A
A
B
C
The main question a set answers efficiently is:
Have I seen this before?
Example:
if node in visited:
...
Usually average:
O(1)
with a hash-based set.
Hash map vs set
Think:
Hash map:
key → value
Set:
key → exists
Example:
phone_numbers["Alice"] = "..."
versus:
blocked_users = {"Alice", "Bob"}
8. Heaps
A heap is a special tree designed around one important question:
What is the smallest or largest item right now?
Consider a min-heap.
2
/ \
5 8
/ \ / \
9 12 10 20
The rule is:
parent ≤ children
Therefore the smallest element is always at the root.
2
Importantly:
A heap is NOT completely sorted.
For example:
5 and 8
9 and 12
don't need a global ordering.
Only the parent-child heap rule matters.
Why not just sort everything?
Suppose autonomous navigation has candidate actions:
path A cost = 91
path B cost = 12
path C cost = 43
path D cost = 20
You repeatedly need:
Give me the lowest-cost candidate.
Sorting everything again and again would be wasteful.
A min-heap lets us maintain the smallest candidate efficiently.
Typical complexity:
peek minimum O(1)
insert O(log n)
remove minimum O(log n)
9. Priority Queues
A priority queue is an abstract behavior:
Items leave according to priority, not necessarily arrival time.
Example:
Task Priority
Emergency stop 100
Obstacle avoidance 80
Map update 30
Logging 10
The next item should be:
Emergency stop
not whichever arrived first.
A heap is one common implementation of a priority queue.
So:
Priority Queue = what behavior we want
Heap = one data structure used to implement it
This distinction is important.
10. Trees
Trees represent hierarchy.
Think about a filesystem:
home
├── documents
│ ├── notes.txt
│ └── project.pdf
└── pictures
├── robot.png
└── map.png
Or an organization:
CEO
├── Engineering
│ ├── Robotics
│ └── AI
└── Operations
Unlike a simple list, one item can lead to multiple children.
Core tree terminology
Consider:
A
/ \
B C
/ \
D E
A is the:
root
B is a:
child of A
A is:
parent of B
D and E are:
leaves
A path could be:
A → B → E
The tree's height roughly tells us how many levels deep it goes.
11. Binary Search Trees — BST
A Binary Search Tree adds an ordering rule.
For every node:
left subtree < node
right subtree > node
Example:
8
/ \
3 12
/ \ / \
1 6 10 15
Want 10?
Start:
8
Since:
10 > 8
go right.
12
Since:
10 < 12
go left.
10
Found.
Instead of examining every value, we eliminate large portions of the search space.
The dangerous BST problem
Suppose values arrive:
1, 2, 3, 4, 5
A naive BST may become:
1
\
2
\
3
\
4
\
5
That is technically a tree.
But algorithmically it has become almost a linked list.
Search becomes approximately:
O(n)
instead of:
O(log n)
This leads us to balanced trees.
12. Balanced Trees
A balanced tree tries to prevent the tree from becoming extremely one-sided.
Healthy:
8
/ \
4 12
/ \ / \
2 6 10 14
Height approximately:
log₂(n)
Therefore search, insertion and deletion can remain around:
O(log n)
Common examples include:
AVL trees
Red-Black trees
B-trees
B+ trees
You don't initially need to memorize every rotation and balancing rule.
The deeper intuition is more valuable:
Balanced trees preserve logarithmic search by preventing pathological shape.
13. Tries
A trie is a tree specialized for strings or sequences.
Suppose we store:
car
cat
dog
The trie looks like:
root
/ \
c d
| |
a o
/ \ |
r t g
Notice:
car
cat
share the prefix:
ca
instead of storing that prefix independently twice.
Why tries are powerful
Suppose a user types:
auto...
You want autocomplete:
autonomous
automation
automobile
A trie can quickly navigate the prefix:
a → u → t → o
and then explore everything below it.
Useful for:
autocomplete
dictionaries
routing tables
prefix matching
spell checking
14. Graphs
Trees describe hierarchy.
Graphs describe relationships.
This is one of the most important data structures in computer science, robotics, networks and AI.
A graph contains:
vertices / nodes
edges / connections
Example road network:
B
/ \
A D
\ /
C
Nodes:
A, B, C, D
Edges:
A-B
A-C
B-D
C-D
Why graphs matter so much
Many real problems are secretly graphs.
Cities → roads
Computers → network connections
People → friendships
Web pages → hyperlinks
Robot poses → constraints
Tasks → dependencies
States → transitions
Objects → relationships
A robot planning a route through an environment often ends up solving a graph-search problem.
Weighted graphs
Edges can have costs.
A ----5---- B
| |
2 3
| |
C ----1---- D
Weights might represent:
distance
travel time
energy
risk
cost
Path planning becomes:
Find a path whose total edge cost is minimal.
Algorithms such as:
Dijkstra
A*
operate on this idea.
Directed graphs
Sometimes connections have direction.
A → B
does not imply:
B → A
Examples:
web links
task dependencies
state transitions
one-way roads
Graph representation
Two very important representations are:
Adjacency list
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
Excellent for sparse graphs.
Adjacency matrix
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
Excellent when direct edge lookup matters and the graph is dense enough.
15. Disjoint Sets / Union-Find
Suppose you have:
A B C D E F
Initially every element is separate:
{A} {B} {C} {D} {E} {F}
Then you learn:
A connected to B
B connected to C
Now:
{A, B, C} {D} {E} {F}
Then:
D connected to E
giving:
{A, B, C} {D, E} {F}
A Disjoint Set Union, or Union-Find, efficiently answers:
Are X and Y in the same group?
and:
Merge these two groups.
The two core operations are:
find(x)
union(a, b)
Example
Imagine robot-map components.
Region A connected to B
Region B connected to C
Region D connected to E
Then asking:
Is A connected to C?
should quickly return:
yes
while:
Is A connected to E?
returns:
no
Union-Find is famous for algorithms like:
Kruskal's Minimum Spanning Tree
With optimizations such as:
path compression
union by rank/size
its operations become extremely close to constant time in practice.
16. Sparse Representations
This idea becomes extremely important in robotics, machine learning, scientific computing and mapping.
Imagine a huge matrix:
0 0 0 0 0 0
0 0 5 0 0 0
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 0 0
Almost everything is zero.
A dense representation stores every element.
But why store millions of zeros?
Instead, a sparse representation may store only:
(row=1, col=2, value=5)
(row=3, col=1, value=2)
This can drastically reduce:
memory
computation
bandwidth
Sparse thinking in robotics
Imagine mapping a huge 3D environment.
The world might theoretically contain billions of possible spatial cells.
But perhaps only a tiny fraction are actually occupied.
Instead of storing:
EVERY POSSIBLE LOCATION
we often store:
ONLY LOCATIONS WITH USEFUL INFORMATION
That idea leads directly into spatial data structures.
17. Spatial Data Structures
For ordinary data, we often ask:
What value has this key?
But robotics constantly asks geometric questions:
What objects are near this point?
What points lie inside this region?
What obstacle is closest to the robot?
Which 3D cells are occupied?
Which LiDAR points belong near each other?
These questions require structures designed around space.
Important ones include:
KD-trees
quadtrees
octrees
voxel grids
18. KD-Trees
KD means roughly:
k-dimensional tree
They are commonly used for organizing points in multidimensional space.
Suppose we have:
(2,3)
(5,4)
(9,6)
(4,7)
(8,1)
Instead of storing only a list and checking every point when asking:
Which point is closest to
(5,5)?
a KD-tree repeatedly divides space.
A simplified 2D intuition:
split x
|
----------+----------
|
split y | split y
---------- ---------
One node may split based on:
x-coordinate
the next level based on:
y-coordinate
then x again, and so on.
Why KD-trees matter
Suppose a LiDAR scan contains:
100,000 points
and you ask:
Which points are nearest to this coordinate?
Checking every point every time may be expensive.
A KD-tree can eliminate large regions that cannot possibly contain the nearest candidate.
This is useful for:
nearest-neighbor search
point clouds
ICP
geometric matching
clustering
collision queries
19. Quadtrees
A quadtree recursively divides 2D space into four regions.
Start with:
+-------------------+
| |
| world |
| |
+-------------------+
Divide into four:
+---------+---------+
| | |
| NW | NE |
| | |
+---------+---------+
| | |
| SW | SE |
| | |
+---------+---------+
If one region contains lots of detail, divide only that region again.
+---------+---------+
| | | |
| |----+----|
| | | |
+---------+---------+
| |
| |
+-------------------+
The important intuition is:
Spend resolution only where resolution is needed.
An empty field doesn't need hundreds of tiny cells.
A complicated obstacle-filled region might.
20. Octrees
An octree is essentially the 3D cousin of the quadtree.
A cube is divided into:
8 smaller cubes
because 3D has:
2 × 2 × 2 = 8
children.
Conceptually:
Large cube
↓
8 cubes
↓
interesting cubes subdivide again
↓
smaller cubes
Why octrees matter in robotics
Imagine representing an entire building in 3D.
A naive uniform grid could require enormous amounts of memory.
But much of the volume is:
empty air
An octree allows large empty regions to stay coarse while detailed surfaces become fine.
This is useful for:
3D mapping
collision detection
occupancy maps
point clouds
motion planning
A famous robotics representation based on this idea is OctoMap.
21. Voxel Grids
A pixel is a small cell in 2D.
A voxel is roughly the 3D equivalent.
pixel → picture element
voxel → volume element
Imagine the world as tiny cubes:
+---+---+---+
| |███| |
+---+---+---+
| |███| |
+---+---+---+
| | | |
+---+---+---+
Each voxel might store:
occupied
free
unknown
or perhaps:
density
color
probability
semantic class
distance-to-surface
Robotics example
Suppose the robot observes a chair.
Instead of representing the chair as a mathematical mesh, we might mark the 3D cells where its physical matter appears:
empty
empty
chair
chair
empty
...
This makes many geometric algorithms easier.
Voxel Grid vs Octree
This difference is important.
A normal voxel grid might divide the entire world uniformly:
every cell = 5 cm × 5 cm × 5 cm
That is simple.
But potentially huge.
An octree says:
large empty space?
keep it large.
complex geometry?
subdivide it.
Therefore:
Voxel grid
→ uniform spatial resolution
Octree
→ adaptive hierarchical resolution
Quadtree vs Octree
Easy memory trick:
QUAD → 4 children → 2D
OCT → 8 children → 3D
because:
2D:
2 × 2 = 4
3D:
2 × 2 × 2 = 8
KD-Tree vs Quadtree vs Octree vs Voxel Grid
This is worth understanding rather than memorizing.
| Structure | Main Idea | Typical Use |
|---|---|---|
| KD-tree | Organize points by coordinate splits | nearest-neighbor search |
| Quadtree | Recursively divide 2D regions | maps, 2D spatial indexing |
| Octree | Recursively divide 3D regions | 3D maps, occupancy |
| Voxel grid | Divide 3D space into cells | perception, occupancy, geometry |
Ask yourself:
Do I have POINTS?
→ KD-tree may help.
Do I need adaptive 2D REGIONS?
→ Quadtree.
Do I need adaptive 3D VOLUME?
→ Octree.
Do I want a simple regular 3D lattice?
→ Voxel grid.
Why spatial structures matter so much in robotics
A normal software application may mostly manipulate:
users
strings
database records
messages
A robot must reason about:
SPACE.
Its fundamental questions are geometric.
Where am I?
Where is the obstacle?
What exists around me?
Which point belongs to this surface?
Can my robot fit through here?
What is the nearest object?
Which region is unexplored?
Is this location occupied?
Consider a simplified autonomous robot pipeline:
Camera / LiDAR
↓
Sensor points
↓
Point cloud
↓
Spatial representation
↓
Obstacle / environment understanding
↓
Planning
↓
Robot movement
Different structures may appear throughout the pipeline.
For example:
LiDAR measurements
↓
array
Point cloud search
↓
KD-tree
3D occupancy
↓
voxel grid / octree
Navigation connectivity
↓
graph
A* frontier
↓
priority queue / heap
visited nodes
↓
set
node → metadata
↓
hash map
Notice something important:
Real systems don't choose one data structure.
They combine many structures because each solves a different problem.
The Big Picture
You don't need to ask:
"Which data structure is the best?"
There is no universal best structure.
Ask:
Which operation must be fast?
If you need:
Get element number i instantly
think:
ARRAY
If you need:
Insert/remove through links
think:
LINKED LIST
If you need:
Most recently added item
think:
STACK
If you need:
Oldest waiting item
think:
QUEUE
If you need:
key → value
think:
HASH MAP
If you need:
Have I seen this?
think:
SET
If you repeatedly need:
Give me the minimum/maximum priority
think:
HEAP / PRIORITY QUEUE
If your information is hierarchical:
parent
├ child
└ child
think:
TREE
If you need ordered searching:
smaller ← node → larger
think:
BST
and if reliable performance matters:
BALANCED TREE
If you need prefix lookup:
"auto..."
think:
TRIE
If things are connected in arbitrary ways:
A ↔ B
↕ ↕
C ↔ D
think:
GRAPH
If you repeatedly merge connected groups:
{A,B} + {C,D}
think:
DISJOINT SET / UNION-FIND
If most possible values are empty or zero:
0 0 0 0 X 0 0 0
think:
SPARSE REPRESENTATION
If the problem is geometric:
nearest point
occupied region
3D environment
start thinking about:
KD-trees
quadtrees
octrees
voxel grids
A Small Complexity Cheat Sheet
You don't need to blindly memorize this table. Understand why the operations have these costs.
| Structure | Important Operation | Typical Cost |
|---|---|---|
| Array | index access | O(1) |
| Array | middle insertion | O(n) |
| Linked list | access by position | O(n) |
| Linked list | known-position insert/remove | O(1) |
| Stack | push/pop | O(1) |
| Queue | enqueue/dequeue | O(1) |
| Hash map | lookup | O(1) average |
| Hash set | membership | O(1) average |
| Heap | minimum/maximum peek | O(1) |
| Heap | insert/remove root | O(log n) |
| Balanced BST | search/insert/delete | O(log n) |
| Trie | lookup | roughly O(length of key) |
| Graph traversal | BFS/DFS | O(V + E) |
| Union-Find | union/find | almost O(1) amortized |
For spatial structures, complexity depends heavily on:
dimension
distribution of points
tree balance
query type
so don't reduce them to one magical Big-O number.
One Deeper Lesson
Data structures are not merely containers.
They encode assumptions about the problem.
A queue says:
Order of arrival matters.
A priority queue says:
Importance matters more than arrival.
A BST says:
Ordering matters.
A hash map says:
Exact identity matters.
A graph says:
Relationships matter.
A KD-tree says:
Geometric proximity matters.
An octree says:
Space has detail at different scales.
That is the deeper way to learn data structures.
Final Mental Model
When encountering a new engineering problem, don't immediately ask:
"Which data structure should I use?"
First identify the operations:
What do I need to retrieve?
What do I need to update?
What do I need to search?
Does ordering matter?
Does priority matter?
Does connectivity matter?
Does geometric distance matter?
Is the data sparse?
How large can the data become?
Then choose the representation.
Because in computer science:
The way you represent the problem often determines how easily you can solve it.
And in robotics this becomes even more literal:
Representing the world correctly is often half the problem of understanding and navigating it.