DATA STRUCTURES

Beginner Onboarding Guide

From Zero to Confident — A Bottom-Up Checklist

LEVEL 1 LEVEL 2 LEVEL 3 LEVEL 4 LEVEL 5

Arrays & Linked Hash Tables &

Foundations Lists Stacks & Queues Trees & Graphs Heaps

Comprehensive | Beginner Friendly | Visual Examples | With Diagrams

Master Checklist
Your complete roadmap — print it out and check off as you go!

LEVEL 1 — Foundations

■ Understand what a Data Structure is and why it matters

■ Know the difference between primitive & non-primitive types

■ Understand Memory: RAM, addresses, bits & bytes

■ Learn Big-O Notation: O(1), O(n), O(log n), O(n squared)

■ Understand Time Complexity vs Space Complexity

■ Practice reading Big-O for simple for-loops and nested loops

LEVEL 2 — Arrays & Linked Lists

■ Understand what an Array is (fixed-size, indexed, contiguous memory)

■ Practice: access, insert, delete in an Array

■ Know Array complexities (access O(1), insert/delete O(n))

■ Understand what a Linked List is (nodes + pointers)

■ Know: Singly vs Doubly vs Circular Linked Lists

■ Practice: traverse, insert, delete a Linked List

■ Compare Array vs Linked List — when to use which

LEVEL 3 — Stacks & Queues

■ Understand the Stack concept (LIFO: Last-In-First-Out)

■ Know Stack operations: push, pop, peek, isEmpty

■ Understand real-world Stack uses (undo, browser back, call stack)

■ Understand the Queue concept (FIFO: First-In-First-Out)

■ Know Queue operations: enqueue, dequeue, front, rear

■ Know types: Simple, Circular, Priority Queue, Deque

■ Implement Stack & Queue using both Array and Linked List

Data Structures: Beginner Onboarding Guide | Page 2

LEVEL 4 — Trees & Graphs

■ Understand Tree terminology (root, parent, child, leaf, height)

■ Learn Binary Tree vs Binary Search Tree (BST)

■ Practice: BST insert, search, delete by hand first

■ Understand Tree traversals: Inorder, Preorder, Postorder, BFS

■ Learn what a Graph is (vertices + edges)

■ Know: Directed vs Undirected, Weighted vs Unweighted

■ Understand Graph representations (adjacency list vs matrix)

■ Learn BFS (Breadth-First) and DFS (Depth-First) traversal

LEVEL 5 — Hash Tables & Heaps

■ Understand what Hashing is and how hash functions work

■ Know what a Hash Table / HashMap / Dictionary is

■ Understand collision handling: chaining & open addressing

■ Know Hash Table complexities (average O(1) lookup)

■ Understand what a Heap is (Min-Heap vs Max-Heap)

■ Know Heap property and how heapify works

■ Understand Priority Queue and where heaps are used

■ Practice: insert and extract-min/max from a Heap

Data Structures: Beginner Onboarding Guide | Page 3

Level 1 — Foundations
Build a rock-solid mental model before writing any code

What is a Data Structure?

A data structure is a way of organizing and storing data in a computer so it can be accessed and modified
efficiently. Think of it like choosing the right container: you would not store soup in a paper bag or carry water in a
basket!

Real World Analogy Data Structure Best For

Numbered seats in a cinema Array Fast access by position

Chain of wagons connected

together Linked List Frequent insertions/deletions

Stack of plates (take from top

only) Stack Undo/Redo, backtracking

Queue at a movie ticket counter Queue Scheduling, order processing

Family tree with ancestors Tree Hierarchy, fast searching

Road map connecting cities Graph Networks, relationships

Physical dictionary with index Hash Table Instant key-value lookup

Big-O Notation — Measuring Efficiency

Big-O tells you HOW the running time grows as input gets bigger. We always describe the WORST CASE. Drop
constants: O(3n) = O(n). Only the dominant term matters for large inputs.

Notation Name Concrete Example Speed

O(1) Constant Getting item at array index 5 Instant

O(log n) Logarithmic Binary search in sorted list Very fast

O(n) Linear One loop through n items OK

O(n log n) Linearithmic Efficient sort (merge sort) Decent

O(n^2) Quadratic Two nested loops (bubble sort) Slow

O(2^n) Exponential All subsets of a set Avoid!

Data Structures: Beginner Onboarding Guide | Page 4

i Quick Tip
Drop constants and lower-order terms. O(3n + 100) = O(n). O(n^2 + n) = O(n^2). Only the fastest-growing
part matters when n becomes very large!

Data Structures: Beginner Onboarding Guide | Page 5

Level 2 — Arrays & Linked Lists
The two most fundamental data structures

Arrays — Seats in a Row

An array stores items in a row, one after another in memory, each with a numbered INDEX starting at 0. Like
cinema seats — you can jump directly to any seat by its number!

index 2
fruits[] (5 elements, indices 0-4)

Apple Banana Grape Strawberry Peach

0 1 2 3 4

fruits[2] = "Grape" — Direct jump using index, no searching needed! -> O(1)

Array Operations & Complexities

Operation Code Example Time Why?

Access by index fruits[2] O(1) Direct memory jump

Search (unsorted) Find "Grape" in array O(n) May check every item

Insert at end [Link]("Mango") O(1) No shifting needed

Insert at middle Insert at index 1 O(n) Must shift all right

Delete from middle Remove at index 2 O(n) Must shift all left

Linked Lists — Nodes Connected by Pointers

A linked list is a chain of NODES scattered anywhere in memory, each holding a VALUE and a POINTER (next)
to the next node. Unlike arrays, items do NOT need to be adjacent!

HEAD

10 25 37 48 60 NULL
next -> next -> next -> next -> next ->

Each box = Node (value + pointer). Last node points to NULL (end). HEAD pointer tells us where the list starts.

Array vs Linked List — Side-by-Side Comparison

Feature Array Linked List

Data Structures: Beginner Onboarding Guide | Page 6

Memory layout Contiguous (items in a row) Scattered (random locations)

Access by index O(1) — direct jump O(n) — must walk from HEAD

Insert at beginning O(n) — shift all right O(1) — just update HEAD

Insert at end O(1) amortized O(n) — walk to last node

Delete from middle O(n) — shift elements O(1) — relink pointers

More (each node stores pointer

Memory usage Less (no pointer overhead) too)

Best used when... Frequent reads by index Frequent insert/delete

Data Structures: Beginner Onboarding Guide | Page 7

 Level 3 — Stacks & Queues
Restricted but powerful — used everywhere in computing

Stack — Last In, First Out (LIFO)

A stack works like a pile of plates: you can ONLY add (push) or remove (pop) from the TOP. The LAST item
added is the FIRST to come out. You cannot access items in the middle!

STACK The Four Stack Operations (all O(1)):

push(x) — Add item x on top of the stack
pop() — Remove and return the top item
TOP <- TOP
peek() — View top item WITHOUT removing it
Code isEmpty() — Check if the stack has no items

Data Where Stacks Are Used in Real Life:

Bottom Browser back button — pages pushed; back = pop
Ctrl+Z Undo in Word/Photoshop — actions stacked
Function calls — each call pushed, return = pop
Matching brackets: ( [ { } ] ) validation

Queue — First In, First Out (FIFO)

A queue is like a line at a ticket counter: the FIRST person in line is served first. New items join at the REAR;
items leave from the FRONT. Fair and orderly!

<- DEQUEUE 1 2 3 4 5 ENQUEUE ->

FRONT REAR

Green (1) = FRONT — next to leave. Orange (5) = REAR — last to join. Middle items wait their turn.

Queue Type Description Real World Use

Simple Queue Basic FIFO, one direction Printer spooler, task queue

Rear wraps around to front when

Circular Queue full CPU scheduling, ring buffers

Priority Queue Higher priority items served first Emergency room, Dijkstra algorithm

Deque Sliding window, undo+redo

(Double-ended) Add/remove from BOTH ends combined

Data Structures: Beginner Onboarding Guide | Page 8

i Memory Trick
STACK = pile of pancakes -> LIFO (last pancake placed = first eaten). QUEUE = line at the bus stop ->
FIFO (first person in line = first on bus). The word "queue" is literally just the letter Q followed by silent
letters standing in line!

Data Structures: Beginner Onboarding Guide | Page 9

Level 4 — Trees & Graphs
Non-linear structures for hierarchical and networked data

Tree Terminology
A tree is a hierarchical structure — like an org chart or family tree. In computer science, trees grow
DOWNWARD: the ROOT is at the top, LEAVES are at the bottom.

Term Meaning In the diagram below

Root Top node — has no parent Node 50 (red)

Parent Node that has children below it 50 is parent of 30 and 70

Child Node that has a parent above it 30 and 70 are children of 50

Leaf Node with NO children 20, 40, 60, 80 (purple)

Height Longest root-to-leaf path length This tree has height 2

Subtree Any node plus all its descendants 30, 20, 40 form a subtree

Binary Search Tree (BST)

A BST follows one golden rule: LEFT child < PARENT < RIGHT child. This structure allows O(log n) search —
you eliminate half the tree at every step, just like binary search in an array!
ROOT

50

30 70

20 40 60 80

BST Rule: left child < parent < right child

Searching 60: Start at 50 -> 60>50, go right to 70 -> 60<70, go left -> Found in 3 steps! A brute force search would take up to 7 steps.

Tree Traversals — Visiting Every Node

A traversal visits every node exactly once in a specific order. Three depth-first traversals and one breadth-first:

Traversal Visit Order Result on tree above Best Used For

Data Structures: Beginner Onboarding Guide | Page 10

 Get sorted output
Inorder Left -> Root -> Right 20, 30, 40, 50, 60, 70, 80 from BST!

Copy or serialize a
Preorder Root -> Left -> Right 50, 30, 20, 40, 70, 60, 80 tree

Delete tree
Postorder Left -> Right -> Root 20, 40, 30, 60, 80, 70, 50 (children first)

Level by level, left to Shortest path, level

BFS
(Level-order) right 50, 30, 70, 20, 40, 60, 80 comparison

Graphs — The Most General Structure

A graph is a set of VERTICES (nodes) connected by EDGES. Unlike trees, graphs can have cycles (loops),
disconnected parts, and any structure of connections. Used to model real-world networks!

Type Description Real World Example

Undirected Edges go both ways (A <-> B) Friendship network, roads

Directed (Digraph) Edges have one direction (A -> B) Twitter follows, web links

Edges have a cost or distance

Weighted value GPS maps, airline routes

DAG Directed, Acyclic Graph (no loops) Task dependencies, Git history

Data Structures: Beginner Onboarding Guide | Page 11

Level 5 — Hash Tables & Heaps
The power tools of efficient computation

Hash Tables — Near-Instant Lookup

A hash table maps KEYS to VALUES using a HASH FUNCTION. The function converts a key (like a string
"apple") into an index number, then stores the value at that slot in an underlying array. Average result: O(1)
lookup — does not matter if you have 10 or 10 million items!

Hash Table (size 5)

0: "dog" -> Labrador
"apple" -> hash % 5 = 2

1: (empty)

"dog" -> hash % 5 = 0 2: "apple" -> Granny Smith

3: (empty)

"cat" -> hash % 5 = 4

4: "cat" -> Tabby

Hash function converts "apple" -> large number -> mod 5 -> index 2. Direct slot access!

Collision Handling
Two different keys can hash to the SAME index — called a collision. Two main solutions:

Method How It Works Pro / Con

Each bucket holds a linked list of all

items mapping there. Multiple items can Simple + flexible / uses extra
Chaining share a slot. memory

If slot is full, probe (check) the next Cache-friendly / can degrade with
Open Addressing available slot linearly or with a formula. many collisions

Heaps — Always Know the Min or Max

A heap is a COMPLETE BINARY TREE with one special rule: in a MIN-HEAP, every parent is smaller than its
children (root = smallest). In a MAX-HEAP, every parent is larger (root = largest). This means you can always
read the min or max in O(1)!

Feature Min-Heap Max-Heap

Root contains Smallest element Largest element

Data Structures: Beginner Onboarding Guide | Page 12

Get min or max O(1) — just read root O(1) — just read root

Insert new item O(log n) — bubble up O(log n) — bubble up

Remove min or max O(log n) — heapify down O(log n) — heapify down

Used for Dijkstra shortest path, Prim MST Finding k-th largest element

i Real World — Priority Queue

An emergency room uses a Priority Queue. A heart attack patient is treated before a sprained ankle —
regardless of arrival time. Python's heapq module implements a min-heap directly, and is used in many
algorithms like Dijkstra and A*.

Data Structures: Beginner Onboarding Guide | Page 13

Big-O Cheat Sheet
All time complexities in one place — reference this often!

Array Avg Time Space Linked List Avg Time Space

Access by index O(1) O(n) Access by index O(n) O(n)

Search (linear) O(n) O(n) Search O(n) O(n)

Insert at end O(1)* O(n) Insert at head O(1) O(n)

Insert at middle O(n) O(n) Insert at tail O(n) O(n)

Delete O(n) O(n) Delete head O(1) O(n)

Stack Avg Time Space Queue Avg Time Space

Push (add to top) O(1) O(n) Enqueue (add rear) O(1) O(n)

Pop (remove top) O(1) O(n) Dequeue (remove front) O(1) O(n)

Peek (view top) O(1) O(1) Peek front O(1) O(1)

BST (average case) Avg Time Space Hash Table Avg Time Space

Search O(log n) O(n) Search O(1) avg O(n) worst

Insert O(log n) O(n) Insert O(1) avg O(n) worst

Delete O(log n) O(n) Delete O(1) avg O(n) worst

Heap Avg Time Space

Find min/max O(1) O(n)

Insert O(log n) O(n)

Extract min/max O(log n) O(n)

Data Structures: Beginner Onboarding Guide | Page 14

When to Use What?
A practical decision guide for every situation

You Need To... Best Choice Reason

Access items by position quickly Array O(1) direct index access

Insert or delete at the beginning often Linked List O(1) head insert

LIFO perfectly models undo

Undo/redo, backtracking problems Stack history

Process tasks in arrival order Queue FIFO ensures fair ordering

Fast key-value lookup (like a

dictionary) Hash Table O(1) average lookup/insert

Keep data sorted, do range queries BST / AVL Tree O(log n) insert and search

Always need smallest or largest item

fast Min/Max Heap O(1) peek, O(log n) insert

Graphs represent any

Model a network (cities, friends, web) Graph relationship

O(m) prefix ops, m = word

Autocomplete or prefix searching Trie length

Recommended Study Timeline

Time Topic Focus

Master complexity analysis; implement arrays without

Week 1 Big-O Notation + Arrays built-in methods

Build singly and doubly linked lists from scratch;

Week 2 Linked Lists understand pointer logic

Short to learn, widely used — implement using both

Week 3 Stacks & Queues arrays and linked lists

Most common in interviews — practice all traversals by

Week 4 Trees & BST hand BEFORE coding

Data Structures: Beginner Onboarding Guide | Page 15

 Used everywhere — understand internals (hash
Week 5 Hash Tables function, collisions), not just usage

BFS and DFS are essential algorithms — draw graph

Week 6 Graphs diagrams before writing code

Heaps power Dijkstra and Prim; then revisit all

Week 7+ Heaps + Review structures with harder problems

You now have a complete roadmap! Work through each level, check items off as you go, and
always code each structure from scratch — understanding beats memorization every time.

Data Structures: Beginner Onboarding Guide | Page 16