Data Structures Fundamentals — The Containers That Hold Your Data

What Are Data Structures?

A data structure is a method for efficiently storing and managing data. The performance of an algorithm is largely determined by the choice of data structure.

Big-O Notation (time complexity):
O(1):      Constant time — instant, regardless of size
O(log n):  Logarithmic time — binary search
O(n):      Linear time — one full traversal
O(n²):     Quadratic time — bubble sort

→ When data grows from 1,000 to 1,000,000 items:
O(1):   Still instant
O(n):   1,000× slower
O(n²):  1,000,000× slower

Array

Properties:
→ Stores data in contiguous memory locations
→ O(1) random access via index
→ Fixed size (static array) or variable size (dynamic array)

Time complexity:
Access:          O(1)
Search:          O(n)
Insert (at end): O(1) amortized
Insert (middle): O(n) — all elements after must shift
Delete:          O(n) — shifting required

Best for: ordered data, frequent index-based access

Linked List

Properties:
→ Node = data + pointer to next node
→ Non-contiguous memory (dynamic allocation)

Time complexity:
Access:                        O(n) — must traverse from head
Insert/Delete (known position): O(1)
Search:                        O(n)

Singly Linked List:  one-directional connection
Doubly Linked List:  connected in both directions

Best for: frequent insertions/deletions, unpredictable size

Stack & Queue

Stack (LIFO — Last In First Out):
→ The last item added is the first one removed
Operations: push (add), pop (remove), peek (look at top)
Time complexity: O(1) for all operations

Use cases:
→ Browser back button (history stack)
→ Function call stack (recursion)
→ Parenthesis / bracket validation

Queue (FIFO — First In First Out):
→ The first item added is the first one removed
Operations: enqueue (add), dequeue (remove)
Time complexity: O(1)

Use cases:
→ Printer job queue
→ Breadth-First Search (BFS)
→ CPU process scheduling

Hash Table

How it works:
Key → hash function → index → store Value

Time complexity:
Insert, delete, search: O(1) average ← biggest advantage
Worst case (many collisions): O(n)

Collision resolution:
Chaining:       attach a linked list at the same index
Open Addressing: find an empty slot by probing

Use cases:
→ Dictionaries / maps in most languages (Python: dict, JS: Object/Map)
→ Caching (browser cache, Redis)
→ Database indexes

Tree

Structure:
Root → parent-child hierarchical relationships
Node: data + child pointers
Leaf: a terminal node with no children

Binary Tree: each node has at most 2 children
Binary Search Tree (BST):
→ Left child < Parent < Right child
→ Search, insert, delete: O(log n) average

Balanced Trees (AVL, Red-Black):
→ Guarantee O(log n)
→ Used in database indexes

Heap:
→ Complete binary tree
→ Max-Heap: parent ≥ children (root = maximum value)
→ Used for priority queues and heap sort

Data Structure Selection Guide

Situation	Best Data Structure
Fast index access	Array
Frequent insertions/deletions	Linked List
Last-In-First-Out (undo)	Stack
First-In-First-Out (queue)	Queue
Fast key-value lookup	Hash Table
Searching sorted data	BST / Balanced Tree
Fast access to min/max value	Heap

Array: O(1) access, O(n) insert/delete / Linked List: O(n) access, O(1) insert/delete Stack = LIFO (back button) / Queue = FIFO (job queue) Hash Table: O(1) average search — the core of caches and dictionaries BST: left < parent < right → O(log n) search