Data Structures: Lists, Trees, and Maps

The Difference Between Software That Freezes and Software That Flies

When Spotify shuffles your 2,000-song library, it doesn't pick randomly from a pile. When Google autocompletes your search after 2 keystrokes, it doesn't scan every word in every language. When your GPS recalculates a route in 500 milliseconds, it doesn't check every road on Earth. The secret isn't faster computers -- it's smarter data organization. A data structure is how you arrange data so the operations you need are fast. Choose wrong, and your app freezes. Choose right, and it feels like magic.

This topic isn't abstract theory for interview prep. Every application you use -- every search bar, every recommendation engine, every social feed, every file manager -- is built on data structures chosen specifically because they make the operations that matter fast. Understanding data structures means understanding why some software feels instant and other software feels broken. It's the difference between a developer who builds things that work and one who builds things that work well.

We're going to cover seven structures. Each one exists because it solves a specific problem better than the others. By the end, you'll be able to look at any software feature and reason about what data structure is probably powering it -- and why.

Arrays: The Workhorse of Ordered Data

An array is the simplest data structure: a contiguous block of memory where elements sit side by side in numbered slots. Position 0 holds the first element, position 1 holds the second, and so on. Because elements are stored in a continuous strip, the computer can jump directly to any position using arithmetic -- give me position 47 means "start at the beginning, jump forward 47 slots." That jump takes the same amount of time whether the array has 10 elements or 10 million. This is O(1) access -- constant time, regardless of size.

Arrays are everywhere. A playlist is an array of songs in order. A leaderboard is an array of scores ranked from highest to lowest. A shopping cart is an array of items. The pixels on your screen are stored in a giant array -- one long strip of red, green, and blue values, row after row.

But arrays have a weakness: inserting or deleting elements in the middle is expensive. If you have a sorted list of 1,000 names and you need to insert "Garcia" between "Franklin" and "Henderson," every element from Henderson onward must shift one position to the right to make room. That's potentially hundreds of elements moving. On a list of a million items, that's a million shifts for a single insertion. This is O(n) -- the cost grows linearly with the size of the array.

Linked Lists: Flexible Chains of Data

A linked list solves the array's insertion problem by giving up the array's greatest strength. Instead of storing elements side by side in memory, a linked list stores each element as a separate node. Each node holds two things: the data itself, and a pointer to the next node. The nodes can be scattered anywhere in memory -- they don't need to be adjacent. They're connected by pointers, like a chain of paper clips where each clip is hooked to the next.

This architecture makes insertion and deletion trivially fast. Want to insert a new element between nodes B and C? Create the new node, point it to C, then update B's pointer to point to the new node. Two pointer changes. Done. No shifting, no matter how large the list is. That's O(1) for insertion and deletion once you're at the right position.

The trade-off: you can't jump directly to position 47. There's no formula to calculate where the 47th element lives, because nodes are scattered throughout memory. To reach position 47, you start at the beginning and follow 47 pointers, one by one. That's O(n) access -- the opposite of arrays.

Real-world uses: your browser's back/forward history is conceptually a linked list (each page points to the previous and next page). The undo stack in a text editor uses a linked list of states. Music players use linked lists to implement queues where you can insert "play next" songs anywhere in the queue without reshuffling everything.

Stacks and Queues: Controlled Access Structures

Stacks and queues are not new data structures at the implementation level -- they can be built on top of arrays or linked lists. What makes them distinct is their access rules. They restrict how you interact with the data, and those restrictions turn out to be exactly what many problems require.

Stacks: Last In, First Out

A stack works like a pile of plates in a cafeteria. You add plates to the top and remove plates from the top. The last plate you placed on the pile is the first one you take off. This is called LIFO -- Last In, First Out.

Two operations define a stack: push (add an element to the top) and pop (remove the element from the top). Both are O(1). You never access elements in the middle -- only the top.

Stacks are everywhere in computing. When you press Ctrl+Z to undo, your editor pops the last action from an undo stack. When your browser tracks your back-button history, it pushes each new page onto a stack and pops the last page when you go back. When a program calls a function that calls another function that calls another function, the computer tracks where to return using a call stack -- every programming language relies on this internally. If that call stack gets too deep (too many functions calling each other), you get the infamous "stack overflow" error -- which is also where the website gets its name.

Queues: First In, First Out

A queue works like a line at a coffee shop. The first person in line gets served first. You join at the back and leave from the front. This is FIFO -- First In, First Out.

Two operations define a queue: enqueue (add to the back) and dequeue (remove from the front). Both are O(1). Like stacks, you never access elements in the middle.

Queues power every system that processes requests in order. When you send a document to a printer, it enters a print queue. When customers contact support, they enter a queue. When a web server receives more requests than it can handle simultaneously, excess requests wait in a queue. Message queues like RabbitMQ and Kafka are critical infrastructure at companies like LinkedIn and Uber -- they handle millions of events per second, ensuring every message gets processed in order even when traffic spikes.

Hash Maps: The Fastest Lookup Structure Known

A hash map (also called a dictionary, associative array, or hash table) stores key-value pairs and can look up any value by its key in O(1) average time. Not O(log n). Not O(n). Constant time. Whether the hash map has 10 entries or 10 million, looking up a value by key takes approximately the same amount of time. This property is so powerful that hash maps are built into every modern programming language: Python calls them dictionaries, JavaScript calls them objects (and Maps), Java calls them HashMaps, Go calls them maps.

How does this magic work? Through a hash function. When you store a key-value pair, the hash function takes the key (say, the string "[email protected]") and converts it into a number -- a hash code. That hash code is then mapped to an index in an internal array (called a bucket array). To retrieve the value later, the same hash function runs on the same key, produces the same index, and the value is found directly. No searching. No scanning. One calculation, one lookup.

What happens when two different keys hash to the same bucket? This is called a collision. The most common solution is chaining: each bucket holds a small linked list. If two keys land in the same bucket, both key-value pairs are stored in that bucket's list. During lookup, the hash function narrows it down to the correct bucket, then a short linear scan through the chain finds the exact key. With a good hash function and a properly sized bucket array, chains stay very short -- typically 1-2 elements -- so the average lookup remains effectively O(1).

Trees: Hierarchical Data That Searches Itself

A tree is a data structure where each element (called a node) can have zero or more children, creating a hierarchy. There's a single root node at the top, and every other node has exactly one parent. Nodes with no children are called leaves.

You interact with trees every day. Your computer's file system is a tree: the root directory contains folders, which contain subfolders, which contain files. The HTML structure of every web page is a tree called the DOM (Document Object Model): the html element contains head and body, body contains div elements, divs contain paragraphs, and so on. An organizational chart is a tree. A family tree is a tree. The taxonomy of living species is a tree.

But the most computationally useful type of tree is the binary search tree (BST). In a BST, each node has at most two children -- a left child and a right child. The key rule: every value in the left subtree is smaller than the current node, and every value in the right subtree is larger. This rule makes searching remarkably efficient.

The BST search works like looking up a word in a physical dictionary. You don't read every page -- you open to the middle, decide whether your word comes before or after, and repeat in the remaining half. Each comparison eliminates half the remaining data. For a tree with 1 million nodes, that's at most 20 comparisons. For 1 billion nodes, 30 comparisons. The formal time complexity is O(log n) -- the logarithm of the number of elements.

Insertion and deletion in a BST are also O(log n), because you follow the same left/right decision path to find where the new element belongs or where the target element lives. This makes BSTs excellent for maintaining sorted, searchable data that changes frequently -- like a database index, an in-memory sorted set, or an autocomplete dictionary.

Graphs: When Relationships Are Everything

A graph is the most general data structure on this list. It consists of nodes (also called vertices) connected by edges. Unlike trees, graphs have no hierarchy requirement -- any node can connect to any other node, and cycles are allowed (A connects to B, B connects to C, C connects back to A).

Graphs model relationships. A social network is a graph: people are nodes, friendships are edges. A road map is a graph: intersections are nodes, streets are edges. The internet is a graph: servers are nodes, cables are edges. Airline routes, molecular structures, neural networks, recommendation engines -- all graphs.

Graphs come in two main varieties. Directed graphs have edges with a direction (Twitter: you follow someone, but they don't necessarily follow you back). Undirected graphs have edges without direction (Facebook: if you're friends, it goes both ways). Graphs can also be weighted -- each edge carries a number representing cost, distance, or time. Google Maps uses a weighted directed graph: intersections are nodes, roads are directed edges (some streets are one-way), and weights represent travel time.

We'll explore graph algorithms in a dedicated topic. For now, the critical insight is that graphs are the data structure you reach for whenever the data involves connections between things. If your data is about relationships -- who knows whom, what connects to what, how to get from here to there -- you need a graph.

Choosing the Right Data Structure

Every data structure is a trade-off. There is no single structure that's fastest at everything. The skill is matching the structure to the operations your application needs most. Here's the decision framework professionals use.

The following table summarizes the time complexity of the most common operations across the major data structures. This is the cheat sheet that software engineers reference constantly.

How Real Companies Choose Data Structures

Theory is one thing. Let's look at what happens when these choices play out at scale in production systems.

Google Maps: weighted graph

The road network of the entire planet is stored as a weighted graph. Intersections are nodes. Roads are edges. Travel time (updated in real time from GPS data of millions of Android phones) is the edge weight. When you request directions, a variant of Dijkstra's algorithm traverses this graph to find the shortest-weight path. The data structure choice makes this possible -- if roads were stored in a flat list or an array, route calculation would be computationally impossible at this scale.

Redis: hash map server

Redis is an in-memory database used by Twitter, GitHub, Stack Overflow, and thousands of other companies. Its primary data structure is the hash map. That's why it achieves over 1 million operations per second -- every key-value lookup is O(1). When your Twitter feed loads instantly, a significant part of that speed comes from Redis caching pre-computed timelines in hash maps.

File systems: tree

Your computer's file system -- whether Finder on Mac, File Explorer on Windows, or the terminal on Linux -- is literally a tree. The root directory is the root node. Folders are internal nodes. Files are leaf nodes. Navigating to /home/user/documents/report.pdf means traversing the tree: root, then home, then user, then documents, then report.pdf. Every operating system on Earth uses tree structures for file organization because hierarchical containment is exactly what trees model.

Python dictionaries: hash map

Python's built-in dictionary type is a hash map. When you write user = {"name": "Alice", "age": 30} and then access user["name"], Python hashes the string "name," computes a bucket index, and retrieves "Alice" in O(1) time. This is true whether the dictionary has 5 keys or 5 million keys. Dictionaries are so central to Python that the language itself is implemented using them internally -- every object's attributes are stored in a dictionary.

The numbers above show what it takes to find one item in a collection of 1 million. Linear search checks every element. A BST narrows the search with 20 left-or-right decisions. A hash map computes the location directly. Same result, vastly different costs. This is why data structure choice matters more than hardware speed.

The Memory vs. Speed Trade-Off

Data structures don't just differ in speed -- they differ in how much memory they consume. An array is the most memory-efficient structure because it stores raw data with zero overhead. A linked list needs extra memory for every pointer (typically 8 bytes per node on a 64-bit system). A hash map needs a bucket array with empty slots to minimize collisions -- a well-tuned hash map is typically only 50-75% full, meaning 25-50% of allocated memory is intentionally wasted to maintain O(1) performance. A BST stores two pointers per node (left and right child), plus the data.

This trade-off shows up in real engineering decisions. When memory is tight (embedded systems, mobile devices, large datasets), developers lean toward arrays. When speed is critical and memory is available (servers, caching layers), hash maps dominate. When both ordered access and fast modification are needed, BSTs provide the middle ground.

Big O Notation: The Language of Data Structure Performance

Throughout this topic, we've used notation like O(1), O(n), and O(log n). This is Big O notation, and it's how computer scientists describe performance in a hardware-independent way. Instead of saying "this takes 3 milliseconds" (which depends on your specific computer), Big O says "this takes a constant amount of work" (O(1)) or "this takes work proportional to the input size" (O(n)).

The differences are staggering at scale. For 1 billion items: O(1) takes 1 operation. O(log n) takes 30 operations. O(n) takes 1,000,000,000 operations. O(n^2) takes 1,000,000,000,000,000,000 operations -- a number so large that the fastest supercomputer on Earth couldn't finish before the heat death of the universe. This is why algorithm and data structure choices matter infinitely more than buying a faster processor.

When Data Structures Combine: Real Architecture Patterns

Production systems rarely use a single data structure in isolation. They compose multiple structures, each handling the operations it's best at.

A database index is a B-tree (a type of balanced search tree optimized for disk storage) that maps column values to row locations. The data itself lives in a different structure (often a heap or clustered table). When you run SELECT * FROM users WHERE email = '[email protected]', the database doesn't scan every row. It looks up "[email protected]" in the B-tree index (O(log n)), gets the row's disk location, and fetches that specific row. Without the index, it scans all rows (O(n)). With the index on a table of 10 million rows, the lookup takes about 24 comparisons instead of 10 million. That's the difference between a 2-millisecond query and a 3-second query.

A web browser uses a hash map for its cookie storage (domain name maps to cookie data), a tree for the DOM (the page's HTML structure), a stack for the JavaScript call stack, and a queue for the event loop that handles user interactions. Each structure is chosen for the specific access pattern it serves.

A search engine uses an inverted index (a hash map where each word maps to a list of documents containing that word), a graph for PageRank (pages linked to other pages), and trees for query parsing (breaking "best restaurants near me" into a structured query).

Answers to Questions Students Actually Ask

Do I need to memorize all the Big O complexities? Not all of them, but you should know the basics by instinct. O(1) for hash map lookup. O(log n) for BST search and binary search. O(n) for scanning an unsorted array. O(n log n) for good sorting algorithms. O(n^2) for bad sorting algorithms. These five cover 90% of practical situations. The rest you can look up when you need them. What matters more than memorization is developing the intuition for why each structure has the performance it does.

Which data structure should I learn first? Arrays and hash maps. Arrays because they're the foundation -- nearly every other data structure is built on top of arrays internally. Hash maps because they're the most universally useful structure in practical programming. If you can think in terms of arrays and hash maps, you can solve the majority of real-world programming problems. Trees and graphs become important when you tackle more advanced problems like database design, compiler construction, or network analysis.

Are linked lists still relevant? I heard they're obsolete. In practice, linked lists are rarely used directly in application code -- arrays and hash maps dominate. But linked lists are critical inside other data structures. Hash maps use them for collision chaining. Memory allocators use them to track free blocks. Operating system schedulers use them for process queues. You won't write a linked list in your typical web app, but understanding them is essential for understanding how everything else works under the hood.

What's the difference between a hash map and a BST? Both seem to do lookup. Hash maps are faster for pure key-value lookup (O(1) vs. O(log n)). But hash maps don't maintain order. If you need to find all keys between "A" and "M," a hash map can't help -- you'd have to scan every entry. A BST can answer range queries efficiently because its sorted structure lets you skip irrelevant sections of the tree. Use a hash map when you need exact lookups. Use a BST (or a sorted array) when you need ordered access, range queries, or the ability to find the minimum, maximum, or nearest value.

Why does Python call it a "dictionary" instead of a "hash map"? Different languages use different names for the same concept. Python: dictionary. JavaScript: object/Map. Java: HashMap. C#: Dictionary. Go: map. Ruby: hash. They all implement the same core idea -- key-value storage with O(1) average lookup via hashing. The name varies; the underlying mechanism is identical. When you see any of these terms, think "hash map."

How do I know when to use a graph? Ask yourself: "Does my data involve connections or relationships between items?" If two items can be connected, and the connections themselves carry meaning, you have a graph problem. Social networks (who knows whom), road maps (which places connect), dependency systems (which tasks depend on other tasks), recommendation engines (which items relate to other items) -- all graph problems. If your data is purely hierarchical (parent-child, no cycles), a tree suffices. If there's no relationship structure at all, arrays and hash maps handle it.

Where Data Structures Take You Next

Data structures are the foundation of every other topic in computer science that involves performance. Algorithms are operations performed on data structures -- sorting algorithms rearrange arrays, search algorithms traverse trees and graphs, optimization algorithms fill tables. Database design is choosing which data structures to store on disk (B-trees for indexes, hash tables for key-value stores, graphs for relationship databases). System design at companies like Google and Amazon is fundamentally about choosing the right data structures for each component of a large system.

Understanding data structures transforms you from someone who writes code that works into someone who writes code that works well. It's the difference between building an app that handles 10 users and one that handles 10 million. Every software performance problem, at its root, is a data structure problem -- the wrong structure for the operations being performed. Master this topic, and you've acquired the single most important lens for understanding why software behaves the way it does.