What are Data Structures? Types, Classification & Why they matter
Foundation Module - Understand WHAT data structures are before learning them
A data structure is a way of organizing and storing data so it can be accessed and modified efficiently.
Think of it like organizing a library:
Data Structure = Data + Organization + Operations
Example:
Array = Collection of items + Indexed storage + Insert/Delete/Access
Stack = Collection of items + LIFO order + Push/Pop/Peek
Queue = Collection of items + FIFO order + Enqueue/Dequeue/Peek
The right data structure can make your code 10x to 1000x faster.
Problem: Find if a number exists in 1 million items
Unsorted Array: Check every item → O(n) = 1,000,000 checks
Sorted Array: Binary Search → O(log n) = ~20 checks
Hash Table: Direct lookup → O(1) = 1 check!
Same problem, different data structures, MASSIVE difference.
| Scenario | Bad Choice | Good Choice | Speedup |
|---|---|---|---|
| Search contacts | Unsorted list O(n) | Hash Map O(1) | 1000x |
| Undo/Redo | Array copying O(n) | Stack O(1) | 100x |
| Task scheduling | Unsorted list O(n) | Priority Queue O(log n) | 50x |
| Autocomplete | Check all words O(n×m) | Trie O(m) | 100x |
Data Structures
/ \
Linear Non-Linear
/ \ / \
Static Dynamic Trees Graphs
| | \
Array Linked Stack
List Queue
| Type | Description | Examples |
|---|---|---|
| Linear | Elements in sequence, one after another | Array, Linked List, Stack, Queue |
| Non-Linear | Elements in hierarchical/network relationships | Trees, Graphs |
| Type | Description | Examples |
|---|---|---|
| Static | Fixed size, allocated at compile time | Array |
| Dynamic | Size can grow/shrink at runtime | Linked List, Stack, Queue |
| Data Structure | What It Is | Best For |
|---|---|---|
| Array | Fixed-size indexed collection | Fast access by index, simple lists |
| Linked List | Nodes connected by pointers | Frequent insertions/deletions |
| Stack | LIFO (Last In, First Out) | Undo, recursion, expression parsing |
| Queue | FIFO (First In, First Out) | Task scheduling, BFS, buffering |
| Data Structure | What It Is | Best For |
|---|---|---|
| Tree | Hierarchical parent-child structure | File systems, databases, DOM |
| Binary Search Tree | Tree where left < root < right | Fast search/insert/delete O(log n) |
| Heap | Tree with min/max at root | Priority queues, scheduling |
| Graph | Nodes connected by edges (any pattern) | Social networks, maps, routing |
| Hash Table | Key-value pairs with hash function | O(1) lookup, dictionaries, caches |
| Trie | Tree where each node is a character | Autocomplete, spell check |
An ADT defines WHAT operations a data structure supports, not HOW it's implemented.
ADT: Stack
Operations:
- push(item) → Add item to top
- pop() → Remove and return top item
- peek() → View top item without removing
- isEmpty() → Check if stack is empty
Implementation options:
- Array-based stack
- Linked List-based stack
The USER doesn't care how it's built, just that it works!
| ADT | Key Operations | Possible Implementations |
|---|---|---|
| List | add, remove, get, search | Array, Linked List |
| Stack | push, pop, peek | Array, Linked List |
| Queue | enqueue, dequeue, peek | Array, Linked List, Circular Buffer |
| Map/Dictionary | put, get, delete | Hash Table, BST |
| Set | add, remove, contains | Hash Table, BST |
| Priority Queue | insert, extractMin/Max | Heap, Sorted Array |
What do you need?
│
├── Fast access by INDEX? → Array
│
├── Fast INSERT/DELETE? → Linked List
│
├── LIFO (undo, backtrack)? → Stack
│
├── FIFO (scheduling, BFS)? → Queue
│
├── Fast SEARCH by key? → Hash Table
│
├── Sorted data + search? → BST / AVL Tree
│
├── Priority-based access? → Heap
│
├── Relationships/connections? → Graph
│
└── Prefix matching? → Trie
| Requirement | Best Data Structure | Time Complexity |
|---|---|---|
| Access by index | Array | O(1) |
| Insert at beginning | Linked List | O(1) |
| Last-in First-out | Stack | O(1) |
| First-in First-out | Queue | O(1) |
| Key-value lookup | Hash Table | O(1) average |
| Sorted order | BST | O(log n) |
| Min/Max element | Heap | O(1) peek, O(log n) extract |
| Connected data | Graph | Varies |
| Concept | Key Point |
|---|---|
| Data Structure | A way to organize data for efficient operations |
| Linear | Sequential: Array, Linked List, Stack, Queue |
| Non-Linear | Hierarchical/Network: Tree, Graph |
| ADT | Defines WHAT (interface), not HOW (implementation) |
| Choosing | Match your most frequent operation to the right structure |
One-liner for each concept:
| Concept | Key Takeaway |
|---|---|
| Data Structure | Organized storage for efficient data access and modification. |
| Linear | Elements in sequence. Array, Linked List, Stack, Queue. |
| Non-Linear | Hierarchical or network. Trees, Graphs. |
| ADT | Interface (what), not implementation (how). Stack ADT can use Array or Linked List. |
| Array | Random access O(1), but fixed size and slow insert/delete. |
| Linked List | Dynamic size, fast insert/delete O(1), but slow access O(n). |
| Hash Table | O(1) average lookup. The most useful DS for interviews. |
| Tree/Graph | For hierarchical or connected data. |
The Golden Rules:
Video Courses:
Articles & Visualizations:
Practice Problems:
Test your understanding with step-by-step solutions
10 questions · 90s per question
Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.