Data Structures Notes
Subject Overview
Data Structures covers linear structures (stacks, queues, linked lists) and their applications in expression evaluation, non-linear structures (trees, heaps) with traversal algorithms, searching/
Subject at a glance
4
Units
27
Topics
4
Credits
4
Infographics
Unit-wise Syllabus
4 units — open any unit for detailed topic-wise notes, diagrams and important exam questions
- Contiguous implementation of stacks
- polish notations (infix/prefix/postfix conversion and evaluation)
- linear and circular queue implementation
- linked implementation of stacks and queues
- singly/doubly/circular linked lists and their operations
Infix
A + B * C
Precedence rules and brackets
Prefix (Polish)
+ A * B C
Scan right to left with a stack
Postfix (reverse Polish)
A B C * +
Scan left to right with a stack
Study guide
This unit covers stack implementations, polish notations and conversions, linear and circular queues, linked stacks and queues and singly, doubly and circular linked lists. Practise infix-to-postfix conversion.
- Tree definitions (height, depth, order, degree, parent-child relationships)
- binary trees and theorems
- complete and almost-complete binary trees
- tree traversals (preorder, inorder, postorder) and recursive/non-recursive implementations
- expression trees
- threaded binary trees
- forests
- heap definition
- Root
- Top node with no parent
- Leaf
- Node with no children
- Height
- Longest path from root to a leaf
- Degree
- Number of children of a node
- Complete binary tree
- All levels full except maybe the last, filled left to right
- Heap
- Complete tree where parent ≥ children (max-heap)
Study guide
You study tree terminology, binary trees and theorems, complete trees, traversals (recursive and non-recursive), expression trees, threaded binary trees, forests and heaps. Practise traversals and expression tree construction.
- Sequential/binary/indexed sequential/interpolation search
- hashing basics
- collision resolution and chaining
- internal sorting — bubble
- selection
- insertion
- quick
- merge (linked and contiguous)
- shell
- heap and tree sort
Bubble / selection / insertion
O(n²)
O(n²)
Quick sort
O(n log n)
O(n²)
Merge sort
O(n log n)
O(n log n)
Heap sort
O(n log n)
O(n log n)
Shell sort
About O(n^1.3)
O(n²)
Study guide
You study sequential, binary, indexed sequential and interpolation search, hashing, collision resolution and chaining and internal sorts: bubble, selection, insertion, quick, merge, shell, heap and tree sort. Compare the complexity of each sort.
- Graph representations (adjacency matrix, adjacency list, adjacency multilist)
- depth-first and breadth-first traversal
- minimum spanning tree
- shortest path algorithms — Kruskal's and Dijkstra's
Uses
Queue
Stack or recursion
Explores
Level by level
As deep as possible first
Finds
Shortest path in unweighted graphs
Cycles, topological order
Memory
Can be high for wide graphs
Lower for wide graphs
Study guide
You study graph representations, depth-first and breadth-first traversal, minimum spanning trees and shortest paths with Kruskal's and Dijkstra's algorithms. Trace both algorithms on a small graph.
Why Data Structures Matters
Data structures are the main subject of coding interviews at technology companies and the foundation of efficient software.
How to Prepare for Data Structures
- Implement each structure and algorithm from scratch.
- Memorise the time complexity table for common operations.
- Solve interview-style problems each week.
Data Structures: Frequently Asked Questions
What is hashing?
Hashing maps keys to positions in a table using a hash function, allowing very fast average-time search and insertion.