हिंदी में: डेटा को व्यवस्थित तरीके से रखने के तरीके — ऐरे, लिंक्ड लिस्ट, स्टैक, क्यू, ट्री और ग्राफ़।
What is a data structure?
A data structure is a way of organising data in memory so that it can be used efficiently. Choosing the right structure often matters more than clever code: the same task can take seconds or hours depending on it.
- Linear: array, linked list, stack, queue.
- Non-linear: tree, heap, graph.
- Hash-based: hash table / hash map.
Arrays
Elements of the same type stored in contiguous memory. Access by index is O(1), but inserting or deleting in the middle needs shifting, which is O(n). Dynamic arrays (Python list, Java ArrayList) grow automatically.
Linked lists
Each node stores data and a pointer to the next node.
- Singly linked – next pointer only.
- Doubly linked – next and previous pointers.
- Circular – the last node points back to the first.
Insertion/deletion at a known node is O(1); searching is O(n); there is no random access.
Stack (LIFO)
Last In, First Out — like a pile of plates. Operations: push, pop, peek, all O(1).
Uses: function call stack, undo/redo, expression evaluation, balanced-parentheses checking, depth-first search.
Queue (FIFO)
First In, First Out — like a ticket line. Operations: enqueue, dequeue.
Variants: circular queue, deque (insert/delete at both ends) and priority queue (highest priority served first, usually built with a heap).
Uses: CPU scheduling, printer spooling, breadth-first search.
Trees
A hierarchical structure with a root and child nodes; a node with no children is a leaf.
- Binary tree – each node has at most two children.
- Binary Search Tree (BST) – left subtree < node < right subtree. Search/insert/delete are O(log n) on average but O(n) when the tree becomes skewed.
- Balanced BSTs – AVL and Red-Black trees keep height O(log n).
- B and B+ trees – wide, shallow trees used by databases and file systems.
- Trie – stores strings character by character; used for autocomplete.
Traversals: Inorder (Left, Root, Right — gives sorted order in a BST), Preorder (Root, Left, Right), Postorder (Left, Right, Root), and Level-order (BFS).
Heaps
A complete binary tree stored in an array. – Max-heap: every parent ≥ its children. Min-heap: every parent ≤ its children. – Insert and delete-top are O(log n); reading the top is O(1). – Used for priority queues, heap sort, and Dijkstra’s algorithm.
Hash tables
A hash function maps a key to an array index, giving average O(1) insert, search and delete. Two keys mapping to the same index is a collision, handled by chaining (a list at each slot) or open addressing (linear/quadratic probing, double hashing). Python dict and Java HashMap are hash tables.
Graphs
A set of vertices connected by edges; edges can be directed or undirected, weighted or unweighted.
- Adjacency matrix: V×V table; O(1) edge check, O(V²) space.
- Adjacency list: list of neighbours per vertex; O(V + E) space — better for sparse graphs.
Uses: maps and navigation, social networks, computer networks, dependency resolution.
Complexity cheat sheet (average case)
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1)* | O(1)* |
| Stack / Queue | – | O(n) | O(1) | O(1) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash table | – | O(1) | O(1) | O(1) |
| Binary heap | O(1) top | O(n) | O(log n) | O(log n) |
* when the position/node is already known.
Quick revision
- Stack = LIFO, Queue = FIFO.
- Inorder traversal of a BST gives sorted output.
- Hash tables are O(1) on average but O(n) in the worst case.
- Use an adjacency list for sparse graphs.