Data Structures using C++ - Comprehensive B.Sc. Second Year Notes

Course Overview & Exam Preparation

Course Title: Data Structures using C++ (B.Sc. Second Year Notes)
Academic Year: 2026-27
Coverage Scope: Introduction to Data Structures, Types of Data Structures, Space Complexity, Arrays and Operations, Analysis of Algorithms, Time Complexity and Asymptotic Notations, Structured Programming, Recursion, Stacks, Queues, Circular Queues, Linked Lists, Dynamic Memory Allocation, and Stack/Queue implementation using Linked Lists.
Programming Language: C++ (designed for clarity, dry runs, and direct exam application).
Suggested Study Methodology: Read the concept, study the diagram, trace the example, type and run the C++ program, and complete the review/viva questions without looking at the notes.
Core Learning Outcomes:
- Explain the necessity of data structures and classify them into primitive/non-primitive, linear/non-linear, static/dynamic, and homogeneous/non-homogeneous.
- Analyze algorithms in terms of time and space complexity using Big-O ( $O$ ), Omega ( $\Omega$ ), and Theta ( $\Theta$ ) notations.
- Implement insertion, deletion, and update operations on arrays in C++.
- Trace recursive calls using the runtime call stack.
- Implement stacks, linear queues, and circular queues using arrays and apply them to problem solving.
- Use dynamic memory allocation (new / delete) to build and manipulate singly linked lists.
- Implement stacks and queues using linked lists and contrast them with array representations.
Exam Focus Framework: For every data structure, memorize:
1. Definition
2. Representation
3. Operations
4. Algorithm / Program
5. Time & Space Complexity
6. Applications

Unit 1 - Introduction to Data Structures and Arrays

1.1 What is Data?
- Data is defined as a collection of raw facts, values, symbols, or observations (e.g., student roll number, name, marks, temperature readings, product prices).
- A computer program becomes useful when it stores, organizes, processes, and retrieves data efficiently.
1.2 What is a Data Structure?
- A systematic method of organizing and storing data in memory so that operations such as insertion, deletion, searching, updating, and traversal can be performed efficiently.
- Conceptual Formula: Data Structure = Data Arrangement + Operational Rules.
- Need for Data Structures:
- Efficient utilization of memory.
- Accelerated processing and information retrieval.
- Better organization of large volumes of data.
- Reusable design patterns for standard programming tasks.
- Foundational component for operating systems, databases, compilers, networks, and AI.
- Common Operations on Data Structures:
- Traversal: Visit and process each element exactly once.
- Insertion: Add a new element to the structure.
- Deletion: Remove an existing element from the structure.
- Searching: Find the location/index of a specified key.
- Updating: Modify an existing element's value.
- Sorting: Rearrange elements in ascending or descending order.
- Merging: Combine two distinct structures into one.
1.3 Types of Data Structures
- A. Primitive vs. Non-Primitive:
- Primitive: Basic data types directly supported by the language syntax (e.g., int, char, float, double, bool).
- Non-Primitive: Advanced structures built using primitive types (e.g., array, stack, queue, linked list, tree, graph).
- B. Linear vs. Non-Linear:
- Linear: Elements are organized sequentially in a linear sequence where one element follows another (e.g., Array, Linked List, Stack, Queue).
- Non-Linear: Elements form hierarchical or interconnected network relationships (e.g., Tree, Graph).
- C. Static vs. Dynamic:
- Static: Memory size is fixed prior to or during structure creation (e.g., standard standard fixed-size array).
- Dynamic: Memory size can expand or shrink at run time (e.g., Linked list, dynamic array using new/delete).
- D. Homogeneous vs. Non-Homogeneous:
- Homogeneous: All stored elements are of identical data type (e.g., integer array).
- Non-Homogeneous: Fields/elements can store distinct data types (e.g., a C++ struct containing roll number, name, and marks).
1.4 Space Complexity
- Definition: Total memory required by an algorithm to execute to completion.
- Components of Space Complexity:
- Fixed Part: Memory for program code, constants, and simple variables.
- Variable Part: Memory for dynamic allocation, size-dependent arrays, and recursion call stack frame.
- Illustrative Examples:
- Swapping two numbers using a temporary variable: $O(1)$ extra space (requires a constant number of variables).
- Creating an auxiliary array of $n$ integers: $O(n)$ space (memory scales linearly with $n$ ).
- Recursive function with $n$ nested call stack frames: $O(n)$ space.
- Time vs. Space Distinction:
- Time Complexity asks: "How does execution time scale as input size increases?"
- Space Complexity asks: "How does total memory allocation scale as input size increases?"
1.5 Arrays
- Definition: A collection of homogeneous elements stored in contiguous memory locations, accessed via 0-based integer indices.
- C++ Declaration Example: int a[5] = {10, 20, 30, 40, 50};
- a[0] = 10, a[1] = 20, a[2] = 30, a[3] = 40, a[4] = 50.
- Direct Access Time: $O(1)$ due to direct contiguous offset arithmetic.
- Advantages:
- Direct random access using index.
- Simple traversal and memory layout.
- Excellent CPU cache performance owing to physical contiguity.
- Limitations:
- Fixed capacity at allocation time.
- Insertions and deletions in middle locations require $O(n)$ element shifting.
- Memory waste occurs if allocated size greatly exceeds actual element count.
- Requires homogeneous data types.
1.6 Array Traversal
- C++ Program (Traversal): ```cpp
include
using namespace std;
int main() { int a[] = {10, 20, 30, 40, 50}; int n = 5; for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } ```
- Analysis: Loop runs $n$ times; time complexity is $O(n)$ .
1.7 Insertion in an Array
- Concept: To insert at index pos, elements from index n - 1 down to pos must shift right by one position to open a slot.
- Algorithm:
1. Read current count $n$ , target insertion index pos, and new element x.
2. Validate that pos is in range ( $0 \le pos \le n$ ) and array has spare capacity.
3. Loop $i$ from $n - 1$ down to pos, copying a[i] to a[i + 1].
4. Assign a[pos] = x.
5. Increment element count $n$ by 1.
- C++ Program (Insertion): ```cpp
include
using namespace std;
int main() { int a[10] = {10, 20, 30, 40}; int n = 4, pos = 2, x = 25; if (pos < 0 || pos > n) { cout << "Invalid position"; return 0; } for (int i = n - 1; i >= pos; i--) a[i + 1] = a[i]; a[pos] = x; n++; for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } ```
- Time Complexity: $O(1)$ for insertion at the end (no shifting); worst-case $O(n)$ for insertion at index 0.
1.8 Deletion from an Array
- Concept: To delete at index pos, shift all elements from index pos + 1 up to n - 1 left by one position to overwrite the targeted element.
- C++ Program (Deletion): ```cpp
include
using namespace std;
int main() { int a[10] = {10, 20, 30, 40, 50}; int n = 5, pos = 2; if (pos < 0 || pos >= n) { cout << "Invalid position"; return 0; } for (int i = pos; i < n - 1; i++) a[i] = a[i + 1]; n--; for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } ```
- Time Complexity: $O(1)$ for last element deletion; worst-case $O(n)$ when deleting the element at index 0.
1.9 Updating an Array Element
- Concept: Overwrite value at target index directly without element shifting.
- C++ Program (Update): ```cpp
include
using namespace std;
int main() { int a[] = {10, 20, 30, 40, 50}; int n = 5, pos = 2, newValue = 99; if (pos >= 0 && pos < n) a[pos] = newValue; else cout << "Invalid index"; return 0; } ```
- Time Complexity: $O(1)$ (direct memory location lookup).
1.10 Array Operations - Complexity Summary
- Access by Index: Best $O(1)$ , Worst $O(1)$ (Direct address formula).
- Traversal: Best $O(n)$ , Worst $O(n)$ (Visits all $n$ elements).
- Insert at End (with space): Best $O(1)$ , Worst $O(1)$ (No shifting needed).
- Insert at Beginning/Middle: Best $O(n)$ , Worst $O(n)$ (Elements shift right).
- Delete at End: Best $O(1)$ , Worst $O(1)$ (Decrements logical size counter).
- Delete at Beginning/Middle: Best $O(n)$ , Worst $O(n)$ (Elements shift left).
- Update by Index: Best $O(1)$ , Worst $O(1)$ (Direct write access).

Unit 2 - Analysis of Algorithms and Recursion

2.1 What is an Algorithm?
- An algorithm is a finite sequence of unambiguous steps designed to complete a specific task or solve a problem.
- Essential Characteristics:
- Input: Accepts zero or more inputs.
- Output: Produces at least one output result.
- Definiteness: Every step is clearly defined and precise.
- Finiteness: Terminates after a finite number of operations.
- Effectiveness: Each step consists of basic, doable operations.
- Correctness: Yields accurate outputs for all valid inputs.
2.2 Why Analyze Algorithms?
- Enables machine-independent evaluation of efficient solutions.
- Focuses on the scaling behavior of basic operations relative to input size $n$ , examining time and space resource usage.
2.3 Time Complexity
- Mathematical growth model representing how operational runtime scales with input size n$.\n * Standard Hierarchy of Growth Rates:\n * O(1): Constant time (e.g., Array element access by index).\n * O(\log n): Logarithmic time (e.g., Binary search on sorted lists).\n * O(n): Linear time (e.g., Single-pass array traversal).\n * O(n \log n): Linearithmic time (e.g., Merge sort, Quick sort average case).\n * O(n^2) $: Quadratic time (e.g., Nested loops over$ n elements, Bubble sort).\n * O(2^n): Exponential time (e.g., Recursive power set generation).\n * O(n!): Factorial time (e.g., Brute-force Traveling Salesperson Problem).\n\n* **2.4 Asymptotic Notations**\n * **Big-O Notation (O):** Defines an upper bound on performance (worst-case scenario).\n * Example: If T(n) = 3n + 5 $, then$ T(n) = O(n).\n * **Omega Notation (\Omega):** Defines a lower bound on performance (best-case scenario).\n * Example: Inspecting at least 1 element has lower bound \Omega(1).\n * **Theta Notation (\Theta):** Defines an asymptotically tight bound (upper and lower bounds match).\n * Example: If T(n) = 3n + 5 $, then$ T(n) = \Theta(n).\n * Complexity Expression Simplification Example:\n * Given T(n) = 4n^2 + 3n + 10 $, as$ n \to \infty $, the$ n^2 $term dominates. Lower-order terms and constant coefficients drop out, yielding$ O(n^2) $and$ \Theta(n^2).\n\n* **2.5 How to Find Time Complexity from C++ Code**\n * *Example 1 (Single Loop):*\n ```cpp\n for (int i = 0; i < n; i++)\n cout << i;\n ```\n Loop runs n $times$ \implies O(n).\n * *Example 2 (Nested Loops):*\n ```cpp\n for (int i = 0; i < n; i++)\n for (int j = 0; j < n; j++)\n cout << i + j;\n ```\n Inner block runs n \times n = n^2 $times$ \implies O(n^2).\n * *Example 3 (Halving Loop):*\n ```cpp\n for (int i = n; i > 1; i = i / 2)\n cout << i;\n ```\n Sequence: n, n/2, n/4, \dots, 1 $. Number of iterations is proportional to$ \log_2 n \implies O(\log n).\n * *Example 4 (Consecutive Loops):*\n ```cpp\n for (int i = 0; i < n; i++) cout << i;\n for (int j = 0; j < n; j++) cout << j;\n ```\n Total execution: O(n) + O(n) = O(2n) = O(n).\n\n* **2.6 Best, Average, and Worst Case**\n * Performance metrics for linear search across an array of size n.:\n * **Best Case:** Minimum runtime. Key found at index 0 \implies 1 $comparison$ \implies O(1).\n * **Average Case:** Expected runtime on typical data. Key found near middle \implies n/2 $comparisons$ \implies O(n).\n * **Worst Case:** Maximum runtime. Key located at index n-1 $or absent$ \implies n $comparisons$ \implies O(n).\n\n* **2.7 Structured Approach to Programming**\n * Program design strategy organizing code with structured control flow modules rather than arbitrary jumps (e.g., `goto`), enhancing readability, testability, and maintainability.\n * Three Foundational Control Structures:\n * **Sequence:** Step-by-step sequential execution (e.g., Read \to $Calculate$ \to Output).\n * **Selection:** Conditional branching paths (e.g., `if`, `if-else`, `switch`).\n * **Iteration:** Controlled repetitions (e.g., `for`, `while`, `do-while`).\n * **Modular Programming:** Splitting a system into clear functions doing single tasks (e.g., `insertElement()`, `deleteElement()`, `updateElement()`, `display()`).\n\n* **2.8 Recursion**\n * Definition: A computational technique where a function calls itself with a reduced sub-problem until a stopping condition is reached.\n * Essential Components:\n * **Base Case:** Direct conditional answer that halts recursive execution.\n * **Recursive Case:** Problem-reduction step calling the function recursively.\n * Mathematical Definition of Factorial: 0! = 1 $; and$ n! = n \times (n-1)! $for$ n > 0$.
- C++ Program (Recursive Factorial):
```
#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n == 0 || n == 1) // Base case
        return 1;
    return n * factorial(n - 1); // Recursive case
}

int main() {
    int n = 5;
    cout << factorial(n);
    return 0;
}
&nbsp;&nbsp;&nbsp;&nbsp;```
* Dry Run Trace for `factorial(4)`:
* Call Phase: `factorial(4)`  $\to$  `4 * factorial(3)`  $\to$  `factorial(3)`  $\to$  `3 * factorial(2)`  $\to$  `factorial(2)`  $\to$  `2 * factorial(1)`  $\to$  `factorial(1)` returns 1.
* Return Phase: `2 * 1 = 2`  $\to$  `3 * 2 = 6`  $\to$  `4 * 6 = 24` (Final Answer).
* Complexity: Time Complexity =  $O(n)$ , Space Complexity (Call Stack Depth) =  $O(n)$ .
* Sum of First  $n$  Natural Numbers (Recursive C++ Function):
```
cpp int sumN(int n) { if (n == 0) return 0; return n + sumN(n - 1); } ```
- Execution for sumN(4): $4 + 3 + 2 + 1 + 0 = 10$ .\n * Recursion vs. Iteration Comparative Breakdown:\n * **Mechanism:** Function self-calls vs. Loop constructs.\n * **Termination:** Handled by Base Case vs. Handled by Loop condition.\n * **Memory Usage:** High (utilizes function call stack frames) vs. Low (uses fixed loop variables).\n * **Readability:** High elegance for recursive problems vs. Straightforward counting flow.\n * **Risk:** Stack Overflow on excessive depth vs. Potential infinite loops.\n * Critical Programming Pitfall: Omission of a base case leads to infinite self-invocation resulting in Stack Overflow.\n\n\n# Unit 3 - Stacks and Queues\n\n* **3.1 Stack - Introduction**\n * A linear data structure adhering strictly to the **LIFO (Last In, First Out)** principle.\n * Real-world analogy: A stack of cafeteria plates where the top plate is placed last and removed first.\n\n* **3.2 Stack as an Abstract Data Type (ADT)**\n * ADT defines abstract operational behavior without dictating low-level implementations.\n * Key Operations & Operational Complexities:\n * `push(x)`: Insert element `x` at top position $\implies O(1)$ .\n * `pop()`: Remove top element from stack $\implies O(1)$ .\n * `peek()` / `top()`: Inspect value of top element without removal $\implies O(1)$ .\n * `isEmpty()`: Check if stack is empty $\implies O(1)$ .\n * `isFull()`: Check if stack capacity is exhausted $\implies O(1)$ .\n\n* **3.3 Array Representation of a Stack**\n * Implemented using a 1D array accompanied by an integer tracking variable `top` initialized to `-1`.\n * Operational Mechanics: On `push`, increment `top` and store data at `a[top]`; on `pop`, retrieve `a[top]` and decrement `top`.\n * Boundary Conditions:\n * **Overflow:** Attempting to `push` when `top == MAX - 1`.\n * **Underflow:** Attempting to `pop` when `top == -1`.\n\n* **3.4 C++ Implementation of Stack using Array**\n ```cpp\n #include \n using namespace std;\n \n class Stack {\n static const int MAX = 5;\n int a[MAX];\n int top;\n public:\n Stack() { top = -1; }\n bool isEmpty() { return top == -1; }\n bool isFull() { return top == MAX - 1; }\n \n void push(int x) {\n if (isFull()) {\n cout << "Stack Overflow\n";\n return;\n }\n a[++top] = x;\n }\n \n void pop() {\n if (isEmpty()) {\n cout << "Stack Underflow\n";\n return;\n }\n cout << "Deleted: " << a[top--] << "\n";\n }\n \n void peek() {\n if (isEmpty())\n cout << "Stack is empty\n";\n else\n cout << "Top: " << a[top] << "\n";\n }\n \n void display() {\n for (int i = top; i >= 0; i--)\n cout << a[i] << " ";\n cout << "\n";\n }\n };\n \n int main() {\n Stack s;\n s.push(10);\n s.push(20);\n s.push(30);\n s.display();\n s.pop();\n s.peek();\n return 0;\n }\n ```\n\n* **3.5 Applications of Stacks**\n * Program Execution Call Stack (tracking function scope and recursion).\n * Undo/Redo mechanisms in text editors.\n * Browser back-button history navigation.\n * Parenthesis / bracket balanced matching in compilers.\n * Expression conversion (Infix to Postfix/Prefix) and Postfix/Prefix evaluation.\n * Depth-First Search (DFS) graph/tree traversal algorithms.\n * Application Trace (Checking Balanced Parentheses):\n * Iterate across expression string left to right: push open brackets `(`, `{`, `[` onto stack.\n * When closing bracket `)`, `}`, `]` is encountered, compare with `top` element.\n * If match succeeds, execute `pop()`; if mismatch occurs or stack is empty prematurely, expression is unbalanced.\n * Expression is valid if stack is completely empty at end of string parsing.\n * `{(a+b)*[c-d]}` \implies$ Balanced; `{(a+b]` $\implies Unbalanced.\n\n* **3.6 Queue - Introduction**\n * A linear data structure adhering strictly to the **FIFO (First In, First Out)** principle.\n * Real-world analogy: A ticket counter queue where the first person in line is served first.\n\n* **3.7 Queue as an Abstract Data Type (ADT)**\n * Key Operations & Complexities:\n * `enqueue(x)`: Append element `x` at rear index $\implies O(1)$ .\n * `dequeue()`: Remove element from front index $\implies O(1)$ .\n * `front()` / `peek()`: Inspect element at front index without removing $\implies O(1)$ .\n * `isEmpty()`: Check if queue is empty $\implies O(1)$ .\n * `isFull()`: Check if array storage is full \implies O(1)$.\n\n* **3.8 Linear Queue using Array**\n * Employs two index variables: `front` (points to element removal site) and `rear` (points to element insertion site).\n * State Initialization: `front = 0`, `rear = -1`.\n * The False Overflow / Wasted Space Defect: In a basic linear queue, `rear` moves strictly rightward. Once `rear == MAX - 1`, subsequent `enqueue` attempts trigger an overflow state even if prior `dequeue` calls left initial array slots vacant.\n\n* **3.9 C++ Implementation of Linear Queue**\n ```cpp\n #include \n using namespace std;\n \n class Queue {\n static const int MAX = 5;\n int a[MAX];\n int front, rear;\n public:\n Queue() { front = 0; rear = -1; }\n bool isEmpty() { return front > rear; }\n bool isFull() { return rear == MAX - 1; }\n \n void enqueue(int x) {\n if (isFull()) {\n cout << "Queue Overflow\n";\n return;\n }\n a[++rear] = x;\n }\n \n void dequeue() {\n if (isEmpty()) {\n cout << "Queue Underflow\n";\n return;\n }\n cout << "Deleted: " << a[front++] << "\n";\n }\n \n void display() {\n if (isEmpty()) {\n cout << "Queue is empty\n";\n return;\n }\n for (int i = front; i <= rear; i++)\n cout << a[i] << " ";\n cout << "\n";\n }\n };\n ```\n\n* **3.10 Circular Queue**\n * Overcomes false overflow by treating array indices logically as a circle, connecting index `MAX - 1` back to `0`.\n * Index Increment Rule (Modulo Arithmetic): `nextIndex = (currentIndex + 1) % MAX`.\n * Circular Queue Operational Criteria:\n * **Empty State:** `front == -1`.\n * **Full State:** `(rear + 1) % MAX == front`.\n\n* **3.11 C++ Implementation of Circular Queue**\n ```cpp\n #include \n using namespace std;\n \n class CircularQueue {\n static const int MAX = 5;\n int a[MAX];\n int front, rear;\n public:\n CircularQueue() { front = rear = -1; }\n bool isEmpty() { return front == -1; }\n bool isFull() { return (rear + 1) % MAX == front; }\n \n void enqueue(int x) {\n if (isFull()) {\n cout << "Queue Overflow\n";\n return;\n }\n if (isEmpty())\n front = rear = 0;\n else\n rear = (rear + 1) % MAX;\n a[rear] = x;\n }\n \n void dequeue() {\n if (isEmpty()) {\n cout << "Queue Underflow\n";\n return;\n }\n cout << "Deleted: " << a[front] << "\n";\n if (front == rear)\n front = rear = -1; // Queue becomes empty\n else\n front = (front + 1) % MAX;\n }\n \n void display() {\n if (isEmpty()) {\n cout << "Queue is empty\n";\n return;\n }\n int i = front;\n while (true) {\n cout << a[i] << " ";\n if (i == rear) break;\n i = (i + 1) % MAX;\n }\n cout << "\n";\n }\n };\n ```\n\n* **3.12 Applications of Queues**\n * CPU Task Scheduling / Process Management.\n * Print spooler request scheduling.\n * Web server request management queues.\n * Hardware I/O / Keyboard / Network buffers.\n * Breadth-First Search (BFS) algorithm in Graph/Tree structures.\n * Circular Queue Application: Round-Robin CPU scheduling and cyclic streaming buffers.\n\n* **3.13 Stack vs. Queue Comparison**\n * **Rule:** LIFO (Stack) vs. FIFO (Queue).\n * **Insertion Point:** `push` at `top` (Stack) vs. `enqueue` at `rear` (Queue).\n * **Deletion Point:** `pop` from `top` (Stack) vs. `dequeue` from `front` (Queue).\n * **Tracking Variables:** `top` (Stack) vs. `front` and `rear` (Queue).\n * **Primary Applications:** Backtracking & Recursion (Stack) vs. Resource Scheduling & Buffering (Queue).\n\n\n# Unit 4 - Linked Lists\n\n* **4.1 Introduction to Lists and Linked Lists**\n * A linked list is a dynamic linear structure where elements (nodes) are stored in arbitrary memory locations linked together via pointer addresses.\n * Anatomy of a Singly Linked List Node:\n * `data`: Holds stored payload value.\n * `next`: Holds memory address of subsequent node (`Node*`).\n * Logical Layout vs. Memory Reality:\n * Logical: `HEAD -> [10 | next] -> [20 | next] -> [30 | next] -> NULL`\n * Memory Reality: Node 10 could reside at address 1000 with `next = 3400`, Node 20 at address 3400 with `next = 2150`, and Node 30 at address 2150 with `next = nullptr`.\n * Advantages:\n * Dynamic sizing at runtime (no fixed pre-allocated capacity limits).\n * Flexible memory usage (does not require contiguous memory blocks).\n * Efficient O(1) insertion and deletion at the beginning.\n * Disadvantages:\n * No random access; accessing element at index i $requires sequential$ O(n) traversal.\n * Pointer overhead (extra memory allocated for address pointers).\n * Risk of memory leaks or dangling pointers if unhandled during operations.\n\n* **4.2 Node Representation in C++**\n ```cpp\n struct Node {\n int data;\n Node* next;\n };\n \n // Initial empty list representation\n Node* head = nullptr;\n ```\n\n* **4.3 Dynamic Memory Allocation: new and delete**\n * Dynamic Node Creation:\n ```cpp\n Node* newNode = new Node;\n newNode->data = 10;\n newNode->next = nullptr;\n ```\n * Dynamic Node Deallocation:\n ```cpp\n delete newNode;\n newNode = nullptr; // Recommended safeguard against dangling pointers\n ```\n * Memory Leak Warning: Disconnecting a node from a list without calling `delete` leaves memory unreleased and unreachable.\n\n* **4.4 Creating a Three-Node Linked List Step by Step**\n * Target Sequence: `10 -> 20 -> 30 -> NULL`\n * Step 1 (Create Node 1): `Node* first = new Node{10, nullptr}; Node* head = first;`\n * Step 2 (Create Node 2 & Link): `Node* second = new Node{20, nullptr}; first->next = second;`\n * Step 3 (Create Node 3 & Link): `Node* third = new Node{30, nullptr}; second->next = third;`\n\n* **4.5 Traversing a Singly Linked List**\n * C++ Traversal Function:\n ```cpp\n void display(Node* head) {\n Node* temp = head;\n while (temp != nullptr) {\n cout << temp->data << " ";\n temp = temp->next;\n }\n }\n ```\n * Dry Run Trace (`10 -> 20 -> 30 -> NULL`):\n * Iteration 1: `temp` points to 10; print 10; advance `temp = temp->next` (points to 20).\n * Iteration 2: `temp` points to 20; print 20; advance `temp = temp->next` (points to 30).\n * Iteration 3: `temp` points to 30; print 30; advance `temp = temp->next` (`temp == nullptr`).\n * Loop terminates. Complexity = O(n).\n\n* **4.6 Insertion at the Beginning**\n * Logic:\n 1. Instantiate new node `newNode` with data value `x`.\n 2. Assign `newNode->next = head`.\n 3. Update `head = newNode`.\n * C++ Function:\n ```cpp\n void insertBeginning(Node*& head, int x) {\n Node* newNode = new Node{x, head};\n head = newNode;\n }\n ```\n * Time Complexity: O(1).\n\n* **4.7 Insertion at the End**\n * Logic:\n 1. Allocate `newNode = new Node{x, nullptr}`.\n 2. If `head == nullptr`, set `head = newNode` and return.\n 3. Otherwise, traverse using `temp` until `temp->next == nullptr`.\n 4. Assign `temp->next = newNode`.\n * C++ Function:\n ```cpp\n void insertEnd(Node*& head, int x) {\n Node* newNode = new Node{x, nullptr};\n if (head == nullptr) {\n head = newNode;\n return;\n }\n Node* temp = head;\n while (temp->next != nullptr)\n temp = temp->next;\n temp->next = newNode;\n }\n ```\n * Time Complexity: O(n) $without tail pointer;$ O(1) if tail pointer is maintained.\n\n* **4.8 Insertion at a Particular Position**\n * Ordering Rule: MUST execute `newNode->next = temp->next` BEFORE executing `temp->next = newNode` to avoid losing the tail list reference.\n * C++ Function (1-based Index Position):\n ```cpp\n void insertAtPosition(Node*& head, int position, int x) {\n if (position == 1) {\n Node* n = new Node{x, head};\n head = n;\n return;\n }\n Node* temp = head;\n for (int i = 1; i < position - 1 && temp != nullptr; i++)\n temp = temp->next;\n if (temp == nullptr) {\n cout << "Invalid position\n";\n return;\n }\n Node* newNode = new Node{x, temp->next};\n temp->next = newNode;\n }\n ```\n * Time Complexity: O(n).\n\n* **4.9 Deletion from the Beginning**\n * Logic:\n 1. Check if `head == nullptr` (empty list condition).\n 2. Save current head to temporary variable `Node* temp = head`.\n 3. Advance head pointer: `head = head->next`.\n 4. Safely free unlinked node memory: `delete temp`.\n * C++ Function:\n ```cpp\n void deleteBeginning(Node*& head) {\n if (head == nullptr) {\n cout << "List is empty\n";\n return;\n }\n Node* temp = head;\n head = head->next;\n delete temp;\n }\n ```\n * Time Complexity: O(1).\n\n* **4.10 Deletion from the End**\n * C++ Function:\n ```cpp\n void deleteEnd(Node*& head) {\n if (head == nullptr) return;\n if (head->next == nullptr) {\n delete head;\n head = nullptr;\n return;\n }\n Node* temp = head;\n while (temp->next->next != nullptr)\n temp = temp->next;\n Node* target = temp->next;\n temp->next = nullptr;\n delete target;\n }\n ```\n * Time Complexity: O(n).\n\n* **4.11 Deletion at a Particular Position / By Value**\n * C++ Function (Delete first occurrence of `key`):\n ```cpp\n void deleteValue(Node*& head, int key) {\n if (head == nullptr) return;\n if (head->data == key) {\n Node* target = head;\n head = head->next;\n delete target;\n return;\n }\n Node* temp = head;\n while (temp->next != nullptr && temp->next->data != key)\n temp = temp->next;\n if (temp->next == nullptr) {\n cout << "Value not found\n";\n return;\n }\n Node* target = temp->next;\n temp->next = target->next;\n delete target;\n }\n ```\n * Time Complexity: O(n).\n\n* **4.12 Updating and Searching**\n * Search Function C++:\n ```cpp\n int search(Node* head, int key) {\n int position = 1;\n Node* temp = head;\n while (temp != nullptr) {\n if (temp->data == key)\n return position;\n temp = temp->next;\n position++;\n }\n return -1;\n }\n ```\n * Update Function C++:\n ```cpp\n void updateAtPosition(Node* head, int position, int newValue) {\n Node* temp = head;\n for (int i = 1; i < position && temp != nullptr; i++)\n temp = temp->next;\n if (temp == nullptr)\n cout << "Invalid position\n";\n else\n temp->data = newValue;\n }\n ```\n * Time Complexities: Both O(n) worst-case.\n\n* **4.13 Counting Nodes**\n * C++ Function:\n ```cpp\n int countNodes(Node* head) {\n int count = 0;\n while (head != nullptr) {\n count++;\n head = head->next;\n }\n return count;\n }\n ```\n\n* **4.14 Reversing a Singly Linked List**\n * Employs three tracking pointers: `prev` (initialized to `nullptr`), `current` (initialized to `head`), and `nextNode` (initialized to `nullptr`).\n * Operational Steps Per Node:\n 1. Preserve forward link: `nextNode = current->next`.\n 2. Invert link pointer: `current->next = prev`.\n 3. Step pointers forward: `prev = current`, `current = nextNode`.\n * Post-Loop Assignment: `head = prev`.\n * C++ Function:\n ```cpp\n void reverse(Node*& head) {\n Node* prev = nullptr;\n Node* current = head;\n while (current != nullptr) {\n Node* nextNode = current->next;\n current->next = prev;\n prev = current;\n current = nextNode;\n }\n head = prev;\n }\n ```\n * Critical Failure Mode: Executing `current->next = prev` prior to backing up `current->next` irrevocably disconnects and loses the remainder of the list.\n\n* **4.15 Complete Menu-Driven Singly Linked List Program**\n ```cpp\n #include \n using namespace std;\n \n struct Node {\n int data;\n Node* next;\n };\n \n void display(Node* head) {\n while (head != nullptr) {\n cout << head->data << " -> ";\n head = head->next;\n }\n cout << "NULL\n";\n }\n \n void insertBeginning(Node*& head, int x) {\n head = new Node{x, head};\n }\n \n void insertEnd(Node*& head, int x) {\n Node* n = new Node{x, nullptr};\n if (head == nullptr) {\n head = n;\n return;\n }\n Node* t = head;\n while (t->next != nullptr) t = t->next;\n t->next = n;\n }\n \n void insertAtPosition(Node*& head, int pos, int x) {\n if (pos == 1) {\n insertBeginning(head, x);\n return;\n }\n Node* t = head;\n for (int i = 1; i < pos - 1 && t != nullptr; i++)\n t = t->next;\n if (t == nullptr) {\n cout << "Invalid position\n";\n return;\n }\n t->next = new Node{x, t->next};\n }\n \n void deleteBeginning(Node*& head) {\n if (head == nullptr) return;\n Node* t = head;\n head = head->next;\n delete t;\n }\n \n void deleteValue(Node*& head, int key) {\n if (head == nullptr) return;\n if (head->data == key) {\n deleteBeginning(head);\n return;\n }\n Node* t = head;\n while (t->next != nullptr && t->next->data != key)\n t = t->next;\n if (t->next == nullptr) {\n cout << "Value not found\n";\n return;\n }\n Node* target = t->next;\n t->next = target->next;\n delete target;\n }\n \n void updateAtPosition(Node* head, int pos, int value) {\n for (int i = 1; i < pos && head != nullptr; i++)\n head = head->next;\n if (head == nullptr) cout << "Invalid position\n";\n else head->data = value;\n }\n \n int search(Node* head, int key) {\n int pos = 1;\n while (head != nullptr) {\n if (head->data == key) return pos;\n head = head->next;\n pos++;\n }\n return -1;\n }\n \n void reverse(Node*& head) {\n Node* prev = nullptr;\n Node* current = head;\n while (current != nullptr) {\n Node* nextNode = current->next;\n current->next = prev;\n prev = current;\n current = nextNode;\n }\n head = prev;\n }\n \n int main() {\n Node* head = nullptr;\n int choice, x, pos;\n do {\n cout << "\n1.Insert Beginning 2.Insert End\n";\n cout << "3.Insert Position 4.Delete Beginning\n";\n cout << "5.Delete Value 6.Update Position\n";\n cout << "7.Search 8.Reverse\n";\n cout << "9.Display 0.Exit\nChoice: ";\n cin >> choice;\n switch (choice) {\n case 1: cin >> x; insertBeginning(head, x); break;\n case 2: cin >> x; insertEnd(head, x); break;\n case 3: cin >> pos >> x; insertAtPosition(head, pos, x); break;\n case 4: deleteBeginning(head); break;\n case 5: cin >> x; deleteValue(head, x); break;\n case 6: cin >> pos >> x; updateAtPosition(head, pos, x); break;\n case 7:\n cin >> x;\n pos = search(head, x);\n if (pos == -1) cout << "Not found\n";\n else cout << "Found at position " << pos << "\n";\n break;\n case 8: reverse(head); break;\n case 9: display(head); break;\n }\n } while (choice != 0);\n \n while (head != nullptr) deleteBeginning(head);\n return 0;\n }\n ```\n\n* **4.16 Array vs. Linked List Feature Comparison**\n * **Memory Layout:** Contiguous memory (Array) vs. Dispersed nodes linked via addresses (Linked List).\n * **Size Allocation:** Fixed static size (Array) vs. Dynamic runtime scaling (Linked List).\n * **Index Access:** O(1) $(Array) vs.$ O(n) sequential lookup (Linked List).\n * **Insert/Delete at Start:** O(n) $shift cost (Array) vs.$ O(1) link pointer update (Linked List).\n * **Memory Overhead:** Zero pointer memory overhead (Array) vs. Extra pointer per element (Linked List).\n * **Cache Performance:** Excellent locality (Array) vs. Lower locality due to non-contiguous allocation (Linked List).\n\n* **4.17 Stack Implementation using Linked List**\n * Structure Strategy: Use list head node as stack `top`. Insertion (`push`) and deletion (`pop`) occur exclusively at head node, guaranteeing O(1) time without list traversal.\n * Class C++ Implementation:\n ```cpp\n class StackLL {\n Node* top;\n public:\n StackLL() : top(nullptr) {}\n bool isEmpty() { return top == nullptr; }\n \n void push(int x) {\n top = new Node{x, top};\n }\n \n void pop() {\n if (isEmpty()) {\n cout << "Stack Underflow\n";\n return;\n }\n Node* t = top;\n top = top->next;\n delete t;\n }\n \n int peek() {\n if (isEmpty()) throw runtime_error("Empty stack");\n return top->data;\n }\n };\n ```\n\n* **4.18 Queue Implementation using Linked List**\n * Structure Strategy: Maintain dual pointers `front` (head node) and `rear` (tail node). `enqueue` appends to `rear->next` in O(1) $time, while `dequeue` removes from `front` in$ O(1) time.\n * Class C++ Implementation:\n ```cpp\n class QueueLL {\n Node *front, *rear;\n public:\n QueueLL() : front(nullptr), rear(nullptr) {}\n bool isEmpty() { return front == nullptr; }\n \n void enqueue(int x) {\n Node* n = new Node{x, nullptr};\n if (rear == nullptr) {\n front = rear = n;\n return;\n }\n rear->next = n;\n rear = n;\n }\n \n void dequeue() {\n if (isEmpty()) {\n cout << "Queue Underflow\n";\n return;\n }\n Node* t = front;\n front = front->next;\n if (front == nullptr) rear = nullptr;\n delete t;\n }\n };\n ```\n\n* **4.19 Complexity Summary of Singly Linked List Operations**\n * Display / Traversal: O(n).\n * Search Value: O(n).\n * Insertion at Head: O(1).\n * Insertion at Tail: O(n) $(without tail pointer) /$ O(1) (with tail pointer).\n * Insertion at Arbitrary Position: O(n).\n * Deletion at Head: O(1).\n * Deletion at Tail: O(n) (requires finding second-to-last node).\n * Deletion by Key / Position: O(n).\n * Update Node Value: O(n).\n * Reverse List: O(n).\n * Dynamic Stack Push/Pop: O(1).\n * Dynamic Queue Enqueue/Dequeue: O(1).\n\n* **4.20 Common Pointer Mistakes & Exam Diagramming Rules**\n * **Modifying `head` directly during traversal:** Loses list start \implies Use `Node* temp = head`.\n * **Missing `nullptr` dereference checks:** Triggers segmentation faults \implies Always check `temp != nullptr`.\n * **Executing statements in reverse order:** Drops remaining list link references \implies Assign `newNode->next = temp->next` prior to modifying `temp->next`.\n * **Deallocating target node before link re-routing:** Destroys target pointer addresses prematurely \implies Re-route list pointers before calling `delete target`.\n * **Forgetting `delete` calls:** Causes memory leaks \implies Always free dynamically allocated nodes.\n * **Exam Diagramming Rule:** When illustrating insertion or deletion, explicitly show `HEAD`, node memory blocks, pointer address arrows, and `NULL` terminators, writing exact pointer statements alongside the steps.\n\n\n# Appendices & Quick Reference\n\n* **Appendix A - Quick Complexity Reference Table**\n * Array Access / Update by Index: O(1)\n * Array Traversal: O(n)\n * Array Insert / Delete at Beginning: O(n)\n * Array Stack `push` / `pop` / `peek`: O(1)\n * Array Queue `enqueue` / `dequeue`: O(1)\n * Circular Queue `enqueue` / `dequeue`: O(1)\n * Linked List Traversal: O(n)\n * Linked List Insert / Delete at Head: O(1)\n * Linked List Insert at End (without tail): O(n)\n * Linked List Stack `push` / `pop`: O(1)\n * Linked List Queue `enqueue` / `dequeue` (with rear pointer): O(1)\n\n* **Appendix B - C++ Pointer & Dynamic Memory Reference**\n * `int* p;`: Declares `p` as a pointer variable storing address of an integer.\n * `p = &x;`: Assigns memory address of variable `x` to pointer `p`.\n * `*p`: Dereferences pointer `p` to access stored integer value.\n * `Node* head = nullptr;`: Initializes pointer to point to null address.\n * `new Node;`: Dynamically allocates memory block for one `Node` in heap.\n * `delete p;`: Releases heap dynamic memory allocated at pointer address `p`.\n * `temp = temp->next;`: Advances tracking pointer to next linked node address.\n * `head->data`: Accesses `data` member field of struct referenced by `head` pointer.\n\n* **Appendix C - Short Answer Review Questions**\n 1. Define a data structure. Why are data structures required?\n 2. Differentiate linear and non-linear data structures with examples.\n 3. Differentiate static and dynamic data structures.\n 4. Define time complexity and space complexity.\n 5. What do Big-O (O $), Omega ($ \Omega $), and Theta ($ \Theta) notations represent?\n 6. What is recursion? What is a base case?\n 7. Define a stack and list its fundamental operations.\n 8. What are stack overflow and stack underflow?\n 9. Give four practical applications of stacks.\n 10. Define a queue and state the FIFO principle.\n 11. Why is a circular queue better than a simple linear array queue?\n 12. What is a linked list? What are the two fields of a singly linked-list node?\n 13. What is dynamic memory allocation in C++?\n 14. Why is random access not possible in a linked list?\n 15. Why are `push` and `pop` operations O(1) in a linked-list stack?\n\n* **Appendix D - Long Answer / Programming Questions**\n 1. Explain insertion, deletion, and update operations on arrays with algorithms, examples, and full C++ programs.\n 2. Explain asymptotic notations and determine the complexity of single loops, nested loops, and halving loops.\n 3. Explain recursion with a C++ program for factorial and trace the call stack for `factorial(5)`.\n 4. Explain stack as an ADT and implement a stack using an array in C++.\n 5. Discuss applications of stacks. Explain balanced-parentheses checking using a stack with an example.\n 6. Explain queue as an ADT and implement a linear queue using an array in C++.\n 7. Explain circular queues with full and empty conditions. Write a complete C++ implementation.\n 8. Explain singly linked lists with diagrams. Write C++ functions for insertion and deletion.\n 9. Write a menu-driven C++ program to perform basic operations on a singly linked list.\n 10. Implement a stack and a queue using linked lists. Compare linked-list and array implementations.\n\n* **Appendix E - Viva Questions with One-Line Answers**\n * **Q:** Why does array indexing start at 0 in C/C++?\n * **A:** Index represents offset distance from base address; offset 0 designates initial base memory location.\n * **Q:** What is the initial value of `top` in an empty array stack?\n * **A:** `-1`.\n * **Q:** What principle does a stack follow?\n * **A:** LIFO (Last In, First Out).\n * **Q:** What principle does a queue follow?\n * **A:** FIFO (First In, First Out).\n * **Q:** What happens when `pop()` is invoked on an empty stack?\n * **A:** Stack Underflow.\n * **Q:** What problem does a circular queue solve?\n * **A:** Solves false overflow by reusing vacated array positions via index wrap-around.\n * **Q:** What does `nullptr` represent?\n * **A:** A null pointer value indicating pointer points to no valid memory address.\n * **Q:** What is the function of the `new` operator?\n * **A:** Dynamically allocates requested memory size on heap and returns pointer address.\n * **Q:** What is the function of the `delete` operator?\n * **A:** Releases dynamically allocated memory back to memory pool.\n * **Q:** What value is stored in the `next` field of a singly linked list's final node?\n * **A:** `nullptr` (or `NULL`).\n * **Q:** Can a singly linked list provide O(1) access to its 10th node?\n * **A:** No; requires sequential pointer traversal costing O(n) time.\n * **Q:** Which end of a linked list is optimal for stack implementation?\n * **A:** The `head` node, because insertion and deletion operations take O(1) time.\n * **Q:** Why maintain both `front` and `rear` pointers in a linked-list queue?\n * **A:** To guarantee O(1)$$ constant execution time for both enqueue and dequeue operations.
Appendix F - Mini Practice Set (Hand-Tracing Exercises)
1. An array [12, 24, 36, 48] has size capacity 8. Insert element 18 at index 1. Write state shift step-by-step.
2. Delete index 2 from array [5, 10, 15, 20, 25]. Write array contents after each element shift.
3. For an empty stack, perform operations: push(10), push(20), push(30), pop(), push(40), pop(). Identify final remaining stack contents.
4. For an empty queue, perform operations: enqueue(5), enqueue(8), enqueue(11), dequeue(), enqueue(15). Identify element at front.
5. For a circular queue with MAX = 5, mathematically demonstrate how index rear wraps around from index 4 to index 0.
6. Given linked list 10 -> 20 -> 30 -> NULL, trace steps to insert 5 at beginning and 40 at end. Draw final linked representation.
7. Given linked list 5 -> 10 -> 20 -> 30 -> NULL, trace deletion of value 20. Identify exact pointer assignments modified.

Data Structures using C++ - Comprehensive B.Sc. Second Year Notes

Course Overview & Exam Preparation

Unit 1 - Introduction to Data Structures and Arrays

include

include

include

include

Unit 2 - Analysis of Algorithms and Recursion