Data Structures Essentials

Chapter 1: Arrays & Strings - The Sequential Basics

1.1 Arrays: The Row of Lockers

An array is the most basic way to store a list of items. It is a continuous block of memory where each item sits right next to the other.

📦 Real World: Numbered Parking Spots
Imagine a long parking lot with numbered spots: 0, 1, 2, 3...

Access is Instant: If you know your car is in spot #50, you walk straight there. You don't need to check 49 cars first.

Fixed Size: The lot has 100 spots. You can't magically make it 101 spots without building a new lot.

Hard to Move: If a car leaves spot #5 and you want to close that gap, everyone from #6 to #100 must move their car one spot down. That takes a long time!

Common Operations & Speed (Big-O)

Access (Read/Write): O(1) - Instant.
Insert at End (Append): O(1)* - Fast (usually).
Insert/Delete in Middle: O(n) - Slow! You must shift all other items.
Search (Find value): O(n) - Slow. You must check every spot.

*Amortized (average) time. Occasionally requires resizing.

1.2 Strings: Arrays of Characters

A string is basically an array of characters (letters, numbers, symbols). "Hello" is an array: ['H', 'e', 'l', 'l', 'o'].

Important Concept: Immutability
In many languages (like JavaScript, Python, Java), strings are "immutable". This means you cannot change them once created. If you want to change "Hello" to "Jello", the computer actually destroys "Hello" and creates a brand new string "Jello".

⚠️ Performance Trap: String Concatenation

If you add strings together in a loop, it gets very slow because it copies the word over and over.

// ❌ BAD: Creates new string copy every step
let result = "";
for (let char of longList) {
result += char;  // O(n²) because of copying
}
// ✅ GOOD: Collects in array, joins once
let parts = [];
for (let char of longList) {
parts.push(char);
}
let result = parts.join("");  // O(n) much faster!

1.3 Essential Techniques: Two Pointers

A smart way to solve array problems without slow nested loops is using two pointers.

👉👈 Real World: Reading a Scroll from Both Ends
imagine checking if a word is a palindrome (same forwards and backwards, like "RACEAR").

You put one finger on the first letter ('R') and one on the last ('R'). They match! Move fingers inward. Next are 'A' and 'A'. Match! Middle is 'C'. Done.

This touches each letter only once. O(n) time.

1.4 Technique: Prefix Sums

A smart way to answer "What is the sum of items from index A to B?" instantly.

📏 Real World: Cumulative Mileage
On a road trip, you write down the total distance traveled so far at each stop.

Stop A: 100 miles total

Stop B: 250 miles total

Distance between A and B? simply 250 - 100 = 150. You don't need to re-measure the road between them!

1.5 Technique: Sliding Window

Used to find something in a subarray (a slice of the array) without re-calculating everything.

🖼️ Real World: Moving a Picture Frame
You have a long strip of photos. You put a frame over 3 photos at a time. To move to the next set, you don't take the frame off. You just slide it one inch to the right.

One photo leaves the frame (on the left), and one new photo enters (on the right).

Chapter 2: Hash Maps & Sets - The Magic Lookup

2.1 Hash Maps (Dictionaries / Objects)

This is the most useful data structure in day-to-day problem solving. It allows you to find data instantly, without searching.

🏨 Real World: Hotel Reception Key Rack
You don't go room-to-room looking for "Mr. Smith". You go to the front desk. The receptionist looks up "Smith" in the computer, and it tells them exactly where he is: "Room 304".

This "look up name -> get location" is instantaneous. It doesn't matter if the hotel has 10 rooms or 10,000 rooms. It takes the same time.

How it works (Simplified)

A "Hash Function" is a math formula. You feed it a key (e.g., "Apple").

Hash("Apple") -> calculates -> Index 4

The computer puts the data directly in box #4. Next time you ask for "Apple", it does the math again and goes straight to box #4.

Common Operations & Speed

Insert: O(1) - Instant.
Lookup (Find): O(1) - Instant.
Delete: O(1) - Instant.

2.2 Hash Sets

A Set is just a Hash Map that only cares about keys, not values. It's used to check "Have I seen this before?"

Use Case: Types of fruit in a basket
Input: ["Apple", "Banana", "Apple", "Orange", "Banana"]
Set: {"Apple", "Banana", "Orange"} (Duplicates removed automatically)

2.3 The "Collision" Problem

Sometimes the math formula gives the same index for two different words! This is called a Collision.

Example: Hash("Apple") = 4, and Hash("Grape") = 4.

Good hash maps handle this by putting a Linked List (a chain) inside box #4. Both Apple and Grape sit there. The computer checks the few items in that box. It's technically slower, but happens rarely.

Chapter 3: Stacks & Queues - Controlling Order

3.1 Stacks (LIFO - Last In, First Out)

🥞 Real World: Stack of Pancakes
You put pancakes on a plate one by one. Which one do you eat first? The one you put on last (the top one).

You cannot pull a pancake from the bottom without toppling the stack!

Key Terms:

Push: Add to top.
Pop: Remove from top.
Peek: Look at top without removing.

All operations are O(1).

Common Uses: "Undo" button (reverses your last action), Browser "Back" button.

3.2 Queues (FIFO - First In, First Out)

🎫 Real World: Line for Movie Tickets
The first person to join the line is the first person to get a ticket. It's fair!

Key Terms:

Enqueue: Join the back of the line.
Dequeue: Leave the front of the line.

All operations are O(1).

Common Uses: Printer jobs (print in order), Web server requests.

Chapter 4: Linked Lists - The Flexible Chain

Arrays are rigid blocks. Linked Lists are flexible chains of scattered nodes.

🔗 Real World: Treasure Hunt
You don't have a map of all locations. You just have the first clue.

Clue 1: "Go to the big oak tree." -> You go there.
At Oak Tree: "Next clue is under the park bench." -> You go there.
At Bench: "Next clue is at the fountain."

Each item holds the data AND a pointer (address) to the next item.

4.1 Types of Lists

Singly Linked: One-way street. A -> B -> C. You can't go back.
Doubly Linked: Two-way street. A <-> B <-> C. You can go forward and backward.

4.2 Real Power: The LRU Cache

The "Least Recently Used" (LRU) Cache is used by web browsers and databases. It keeps recent items, deletes old ones.

It combines a Hash Map (for fast lookup) and a Doubly Linked List (to track order). When you use an item, you move it to the front of the list. When full, you cut off the tail.

Chapter 5: Heaps & Priority Queues - The VIP Line

Regular queues rely on arrival time. Priority Queues rely on importance.

🏥 Real World: Hospital Emergency Room
Patients are not treated based on who arrived first.

Patient A: Arrived 10am with a cold.

Patient B: Arrived 11am with a broken leg.

Patient B gets treated first because the priority (severity) is higher. The "Max" importance always wins.

5.1 The Heap Structure

A Heap is a special tree that guarantees the "most important" (largest or smallest) item is always at the top.

Max-Heap: Biggest number stays on top. Good for "Give me the most expensive item".
Min-Heap: Smallest number stays on top. Good for "Give me the cheapest price".

Performance (Big-O)

Peek (See top item): O(1) - Instant.
Push (Add item): O(log n) - Very fast.
Pop (Remove top): O(log n) - Very fast.
Search (Find random item): O(n) - Bad! Heaps are not for searching.

Chapter 6: Advanced Tools - Special Structures

6.1 Tries (Prefix Trees)

Pronounced "Try". This is a tree designed specially for words and text.

📱 Real World: Autocomplete
When you type "c-a-t" into Google:

You type 'c': System goes to 'C' branch.

You type 'a': System goes down 'A' branch. Shows "car", "cat", "cake".

You type 't': System goes down 'T' branch. Shows "cat", "catch", "cattle".

It doesn't search millions of words. It just follows the path of letters you typed.

6.2 Union-Find (Disjoint Set)

This is a clever structure used to track groups of things.

👔 Real World: Merging Companies
Imagine 100 tiny startup companies.

Company A buys Company B. They are now one group.

Company C buys Company D. Another group.

Company A (who owns B) now buys Company C (who owns D).

Now A, B, C, D are all one big family. Union-Find helps you ask: "Does Employee X work for the same parent company as Employee Y?" instantly.

Key Operations:

Find: "Who is the leader of this group?"
Union: "Merge these two groups together."

With optimizations ("Path Compression"), this is practically O(1) (inverse Ackermann function).

Chapter 7: Decision Guide - Choosing the Right Tool

You get a problem, not a data structure name. Here is how to pick.

If you need to...	Use this structure:	Because...
Find items by key / Count frequencies / Check duplicates	Hash Map / Set	O(1) lookup is unbeatable.
Stack things up / Undo actions / Process nested items	Stack	LIFO order is perfect for backtracking.
Process tasks in order / Breadth-First Search	Queue	FIFO ensures fairness.
Find the Top K items / Access Min or Max instantly	Heap	Keeps the "best" item accessible without sorting everything.
Search text prefixes / Autocomplete	Trie	Optimized for sharing word prefixes.
Connect networks / Track groups	Union-Find	Merges sets incredibly fast.

💡 The Cheat Sheet for Backends

Most of the time, you just need a List (Array).
If it's slow searching, switch to a Hash Map.
If you need order based on importance, use a Heap.
If you need to limit memory size (cache), use Linked List + Hash Map.

Quick Review

Data structures are ways of organizing data that make certain operations fast, allowing us to optimize for the dominant operations in a workload (lookup, insert, delete, ordering, min/max).

✅ Default picks

Array/List: fastest iteration and indexing; inserts in the middle are costly.
Hash Map / Set: fastest “have I seen this?” and key→value lookups (average O(1)).
Stack / Queue: enforce LIFO/FIFO ordering (great for parsing, BFS/level order, task flow).

✅ When you need priority, structure, or text tricks

Heap/Priority Queue: always pull min/max quickly (Top-K, scheduling).
Linked List + Hash Map: classic combo for LRU cache (fast move-to-front + fast lookup).
Trie: prefix search/autocomplete without scanning all words.
Union-Find: track connected components and merged groups efficiently.

✅ Two-pointer mental toolkit

Two pointers: shrink/grow from ends or chase relationships (sorted arrays, partitions).
Prefix sums: turn range-sum questions into subtraction.
Sliding window: maintain a moving subarray with incremental updates.