CS8391

Data Structures

7 Files
•
Updated Jan 2026
Download Progress 0/7 files
Unit 1
Notes Not downloaded 316 KB
Unit 2
Notes Not downloaded 446 KB
Unit 3
Notes Not downloaded 1 MB
Unit 4
Notes Not downloaded 771 KB
Unit 5
Notes Not downloaded 1.8 MB
Important Questions
Study Not downloaded 40 KB
Question Paper
Exam Not downloaded 65 KB
Academic Study Guide

Complete Data Structures & Algorithms Comprehensive Curriculum Guide

Data Structures form the foundational cornerstone of Computer Science & Engineering. This academic guide provides in-depth conceptual breakdowns, algorithm complexities, unit-by-unit syllabus notes, and high-frequency university exam solutions aligned with Anna University (CS8391), VTU, AKTU, and the AICTE model curriculum.

Unit-by-Unit Theoretical Revision

Unit 1: Linear Data Structures - Arrays & Linked Lists

An Abstract Data Type (ADT) is a high-level specification of a set of data and the operations that can be performed on them, independent of any programming language implementation.

  • Array ADT: Contiguous memory allocation storing elements of homogeneous data type. Offers O(1) random access via index computation Address(A[i]) = Base + i * size, but suffers from fixed size capacity and expensive O(n) element shifts during arbitrary insertions or deletions.
  • Singly Linked List (SLL): Dynamic collection of nodes where each node contains a data field and a pointer (next) referencing the subsequent node. Eliminates contiguous allocation constraints and enables O(1) head insertion/deletion, but requires O(n) sequential traversal to access arbitrary elements.
  • Doubly Linked List (DLL): Each node contains two pointers (prev and next), facilitating bidirectional traversal and O(1) node deletion given a direct pointer to the target node. Trade-off is increased memory overhead per node (extra pointer storage).
  • Circular Linked List (CLL): The last node points back to the first node (head) rather than containing NULL. Used in round-robin CPU scheduling and circular buffers.
  • Applications: Polynomial addition and multiplication using linked lists, large integer arithmetic representation, and sparse matrix representations.

Unit 2: Stacks & Queues (Linear ADTs)

Stacks and Queues are restricted linear data structures governing the precise order in which elements can be inserted and retrieved.

  • Stack ADT (LIFO): Operates on a Last-In, First-Out discipline. Core primitive operations: push(x), pop(), and peek()—all operating in O(1) time complexity. Stack overflow occurs when pushing into a full static array; stack underflow occurs when popping from an empty stack.
  • Stack Applications:
    • Expression Parsing: Infix to Postfix conversion using the Shunting-Yard algorithm (maintaining operator precedence and associativity).
    • Postfix Expression Evaluation: Using a stack to evaluate operands when encountering binary operators.
    • Recursion & Function Call Management: System call stack stores stack frames, return addresses, and local parameters.
    • Backtracking Algorithms: Depth-First Search, maze solving, and syntax parenthesis matching.
  • Queue ADT (FIFO): Operates on a First-In, First-Out discipline. Elements are added at the rear and removed from the front in O(1) time.
  • Circular Queue: Overcomes false overflow in linear array implementations by wrapping pointers using modular arithmetic: rear = (rear + 1) % MAX_SIZE.
  • Double-Ended Queue (Deque): Permits insertion and deletion at both front and rear terminals. Subtypes include Input-Restricted and Output-Restricted Deques.
  • Priority Queue: Elements are dequeued based on assigned priority rather than insertion order, optimally implemented using Binary Heaps with O(log n) enqueue and extract-max/min operations.

Unit 3: Non-Linear Data Structures - Trees & Binary Search Trees

Trees represent hierarchical relationships between entities. A tree is a non-empty set of nodes connected by directed edges without cycles.

  • Binary Tree: Hierarchical structure where every node has at most two children (left child and right child). A Full Binary Tree has nodes with either 0 or 2 children; a Complete Binary Tree is completely filled at all levels except possibly the last, which is filled from left to right.
  • Tree Traversals (O(n) Time Complexity):
    • Pre-order (DLR): Visit Node (Data) → Traverse Left Subtree → Traverse Right Subtree. (Used in tree serialization/cloning).
    • In-order (LDR): Traverse Left → Visit Node → Traverse Right. (Yields sorted order in a Binary Search Tree).
    • Post-order (LRD): Traverse Left → Traverse Right → Visit Node. (Used in bottom-up deletion and expression tree evaluation).
    • Level-order (BFS): Traverses nodes level by level using a FIFO Queue.
  • Binary Search Tree (BST): For every node with key k, all keys in the left subtree are strictly less than k, and all keys in the right subtree are strictly greater than k. Search, insert, and delete take O(h) time, where height h = O(log n) in balanced trees and O(n) in degenerate skewed trees.
  • Expression Trees: Binary tree representation of mathematical expressions where interior nodes hold operators and leaf nodes hold operands.

Unit 4: Balanced Trees & Hashing Techniques

  • AVL Trees (Self-Balancing BST): Maintains the height balance invariant where the Balance Factor BF = Height(Left) - Height(Right) ∈ {-1, 0, +1} for every node. Strictly guarantees O(log n) worst-case time for search, insertion, and deletion.
  • AVL Rotations: Four restorative rotation patterns:
    • LL Rotation (Single Right): Inserted into left subtree of left child.
    • RR Rotation (Single Left): Inserted into right subtree of right child.
    • LR Rotation (Double: Left then Right): Inserted into right subtree of left child.
    • RL Rotation (Double: Right then Left): Inserted into left subtree of right child.
  • B-Trees & B+ Trees: Self-balancing m-way search trees designed for external secondary storage (disk storage and relational database indices). B+ trees store all records in linked leaf nodes, providing fast O(log_m n) range queries.
  • Hashing & Hash Functions: Maps search keys to table slots using hash functions: Division method (h(k) = k % m), Multiplication method, and Mid-square method.
  • Collision Resolution Strategies:
    • Separate Chaining (Open Hashing): Each bucket maintains a linked list of records hashing to the same slot.
    • Open Addressing (Closed Hashing): Elements stored directly in table. Probing sequences include: Linear Probing (h(k, i) = (h'(k) + i) % m, susceptible to primary clustering), Quadratic Probing (h(k, i) = (h'(k) + c₁ i + c₂ i²) % m), and Double Hashing (h(k, i) = (h₁(k) + i · h₂(k)) % m).

Unit 5: Graphs & Fundamental Graph Algorithms

  • Graph Representations: Adjacency Matrix requires O(V²) space (optimal for dense graphs with O(1) edge lookup); Adjacency List requires O(V + E) space (optimal for sparse graphs).
  • Graph Traversals:
    • Breadth-First Search (BFS): Uses a FIFO Queue to discover all vertices at distance k before moving to distance k+1. Time complexity: O(V + E). Computes shortest path in unweighted graphs.
    • Depth-First Search (DFS): Uses recursion or a LIFO Stack to explore branches deeply before backtracking. Time complexity: O(V + E). Detects cycles, topological sorting, and strongly connected components (Kosaraju's algorithm).
  • Minimum Spanning Tree (MST): A subgraph connecting all V vertices with (V - 1) edges minimizing total edge weight without cycles.
    • Prim’s Algorithm: Greedy vertex-growing approach starting from an arbitrary root. Time complexity O(E log V) using Min-Heap.
    • Kruskal’s Algorithm: Greedy edge-selection approach sorting all edges and avoiding cycles using Disjoint-Set Union-Find (DSU). Time complexity O(E log E).
  • Shortest Path Algorithms: Dijkstra’s Algorithm finds single-source shortest paths in non-negative weighted graphs in O((V + E) log V) using a priority queue. Bellman-Ford algorithm handles negative edge weights in O(V · E) time and identifies negative-weight cycles.

Data Structures Time & Space Complexity Reference

Data Structure Access (Avg / Worst) Search (Avg / Worst) Insertion (Avg / Worst) Deletion (Avg / Worst) Space Complexity
Array O(1) / O(1) O(n) / O(n) O(n) / O(n) O(n) / O(n) O(n)
Singly Linked List O(n) / O(n) O(n) / O(n) O(1) / O(1) [at head] O(1) / O(1) [at head] O(n)
Stack (Array/List) O(n) / O(n) O(n) / O(n) O(1) / O(1) [push] O(1) / O(1) [pop] O(n)
Queue (Array/List) O(n) / O(n) O(n) / O(n) O(1) / O(1) [enqueue] O(1) / O(1) [dequeue] O(n)
Binary Search Tree O(log n) / O(n) O(log n) / O(n) O(log n) / O(n) O(log n) / O(n) O(n)
AVL Tree O(log n) / O(log n) O(log n) / O(log n) O(log n) / O(log n) O(log n) / O(log n) O(n)
Hash Table N/A O(1) / O(n) O(1) / O(n) O(1) / O(n) O(n)

High-Frequency University Exam Questions

Q1: Differentiate between Linear Search and Binary Search in terms of complexity and preconditions.

Linear search checks every element sequentially in O(n) time and requires no ordering preconditions on the dataset. Binary Search repeatedly divides a sorted search interval in half in O(log n) time, requiring the prerequisite that elements reside in sorted order with O(1) random index access (such as in an array).

Q2: Why is the worst-case search complexity in a standard BST O(n), and how does an AVL tree resolve this?

In a standard BST, inserting elements in ascending or descending sorted order causes nodes to chain linearly into a skewed tree with height h = n, degrading search performance to O(n). An AVL tree resolves this by enforcing a balance factor invariant (|BF| ≤ 1) and executing automatic tree rotations (LL, RR, LR, RL) upon insertion/deletion to keep height strictly h ≤ 1.44 log₂(n), guaranteeing O(log n) worst-case search.

Q3: How does Circular Queue solve the false overflow problem of linear queues?

In a linear queue using an array, once the rear pointer reaches the final index MAX - 1, further enqueue operations trigger an overflow error even if earlier slots became empty due to successive dequeue operations. A Circular Queue wraps the pointers back to index 0 using modular arithmetic (rear + 1) % MAX, fully utilizing recycled memory slots.

Q4: Compare Prim’s and Kruskal’s algorithms for finding Minimum Spanning Trees (MST).

Prim’s algorithm is a vertex-based greedy approach that grows a single connected component edge-by-edge, performing efficiently in O(E log V) on dense graphs. Kruskal’s algorithm is an edge-based greedy approach that sorts all edges by weight and uses the Disjoint Set Union (DSU) data structure with path compression to unite disconnected trees while preventing cycles, performing exceptionally well in O(E log E) on sparse graphs.