Introduction to Data Structures
Data structures are a way of organizing and storing data so that it can be accessed and modified efficiently. They are fundamental to computer science and programming.
Why Data Structures Matter
**Efficiency**: Choose the right structure for optimal time/space complexity
**Organization**: Keep data organized for easy access
**Reusability**: Standard structures are well-tested and reliable
Arrays
An array is a collection of elements stored at contiguous memory locations.
Properties
Fixed size (in most languages)
O(1) random access
O(n) insertion/deletion
Cache-friendly
Common Operations
| Operation | Time Complexity |
|-----------|----------------|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Search (sorted, binary) | O(log n) |
| Insert at end | O(1) amortized |
| Insert at beginning | O(n) |
| Delete | O(n) |
Linked Lists
A linked list consists of nodes where each node contains data and a reference to the next node.
Types
**Singly Linked List** — Each node points to the next node
**Doubly Linked List** — Each node points to both next and previous
**Circular Linked List** — Last node points back to the first
When to Use
Dynamic size requirements
Frequent insertions/deletions
When random access is not needed
Stacks
A stack follows **LIFO** (Last In, First Out) principle.
Operations
`push()`: Add element to top — O(1)
`pop()`: Remove element from top — O(1)
`peek()`: View top element — O(1)
`isEmpty()`: Check if empty — O(1)
Applications
Function call management (recursion)
Undo operations in editors
Expression evaluation (infix to postfix)
Syntax parsing
Queues
A queue follows **FIFO** (First In, First Out) principle.
Types
**Simple Queue** — Basic FIFO
**Circular Queue** — Better memory utilization
**Priority Queue** — Elements ordered by priority
**Deque** — Insert/delete from both ends
Applications
BFS (Breadth-First Search)
Task scheduling
Print spooling
Message queues
Trees
A tree is a hierarchical data structure with a root node and child nodes.
Binary Tree
Each node has at most 2 children (left and right).
Binary Search Tree (BST)
For any node: left subtree < node < right subtree
Search: O(log n) average
Insert: O(log n) average
Delete: O(log n) average
Tree Traversals
**Inorder** (Left → Root → Right): Sorted order for BST
**Preorder** (Root → Left → Right): Tree copying
**Postorder** (Left → Right → Root): Tree deletion
**Level Order**: BFS traversal
Balanced Trees
**AVL Tree**: Self-balancing BST with height difference ≤ 1
**Red-Black Tree**: Self-balancing with color constraints
**B-Tree**: Optimized for disk storage
Graphs
A graph consists of vertices (nodes) and edges connecting them.
Representations
**Adjacency Matrix**: O(V²) space, O(1) edge lookup
**Adjacency List**: O(V+E) space, O(degree) edge lookup
Traversals
**DFS** (Depth-First Search): Uses stack/recursion
**BFS** (Breadth-First Search): Uses queue
Applications
Social networks (friendship graphs)
Maps and navigation (shortest path)
Recommendation systems
Network routing
Hashing
Hash tables store key-value pairs using a hash function.
Collision Resolution
**Chaining**: Each bucket stores a linked list
**Open Addressing**: Linear probing, quadratic probing, double hashing
Performance
Average: O(1) for insert, delete, search
Worst: O(n) with poor hash function
Key Takeaway
Choose the right data structure based on your access patterns, memory constraints, and performance requirements.