Unit IV — Complete Solutions to All Practice Questions
Table of Contents
Practice Questions — Singly Linked List
Q1. Implement a singly linked list with all operations: insert (beginning, end, position), delete (beginning, end, position), search, display, and count.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// --- INSERT OPERATIONS ---
Node* insertAtBeginning(Node* head, int value) {
Node* newNode = createNode(value);
newNode->next = head;
return newNode; // New head
}
Node* insertAtEnd(Node* head, int value) {
Node* newNode = createNode(value);
if (head == NULL) return newNode;
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
Node* insertAtPosition(Node* head, int value, int pos) {
if (pos == 0) return insertAtBeginning(head, value);
Node* temp = head;
for (int i = 0; i < pos - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) { printf("Invalid position!\n"); return head; }
Node* newNode = createNode(value);
newNode->next = temp->next;
temp->next = newNode;
return head;
}
// --- DELETE OPERATIONS ---
Node* deleteAtBeginning(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
Node* temp = head;
head = head->next;
free(temp);
return head;
}
Node* deleteAtEnd(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
if (head->next == NULL) { free(head); return NULL; }
Node* temp = head;
while (temp->next->next != NULL)
temp = temp->next;
free(temp->next);
temp->next = NULL;
return head;
}
Node* deleteAtPosition(Node* head, int pos) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
if (pos == 0) return deleteAtBeginning(head);
Node* temp = head;
for (int i = 0; i < pos - 1 && temp->next != NULL; i++)
temp = temp->next;
if (temp->next == NULL) { printf("Invalid position!\n"); return head; }
Node* toDelete = temp->next;
temp->next = toDelete->next;
free(toDelete);
return head;
}
// --- UTILITY OPERATIONS ---
int search(Node* head, int key) {
int pos = 0;
Node* temp = head;
while (temp != NULL) {
if (temp->data == key) return pos;
temp = temp->next;
pos++;
}
return -1; // Not found
}
void display(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d → ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int count(Node* head) {
int c = 0;
Node* temp = head;
while (temp != NULL) { c++; temp = temp->next; }
return c;
}
Q2. Write a function to reverse a singly linked list.
Iterative approach (3 pointers):
Node* reverse(Node* head) {
Node *prev = NULL, *curr = head, *next = NULL;
while (curr != NULL) {
next = curr->next; // Save next
curr->next = prev; // Reverse link
prev = curr; // Advance prev
curr = next; // Advance curr
}
return prev; // New head
}
Trace for list: 10 → 20 → 30 → NULL:
| Step | prev | curr | next | State |
|---|---|---|---|---|
| 0 | NULL | 10 | — | 10→20→30→NULL |
| 1 | NULL | 10 | 20 | NULL←10 20→30→NULL |
| 2 | 10 | 20 | 30 | NULL←10←20 30→NULL |
| 3 | 20 | 30 | NULL | NULL←10←20←30 |
| 4 | 30 | NULL | — | Done! Head = 30 |
Result: 30 → 20 → 10 → NULL
Time: $O(n)$, Space: $O(1)$
Q3. Write a function to find the middle element of a singly linked list (use the two-pointer technique).
int findMiddle(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return -1; }
Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next; // Move 1 step
fast = fast->next->next; // Move 2 steps
}
return slow->data; // slow is at middle
}
How it works: When fast reaches the end (having moved 2x speed), slow is exactly at the middle.
Trace for 10 → 20 → 30 → 40 → 50 → NULL:
| Step | slow | fast |
|---|---|---|
| 0 | 10 | 10 |
| 1 | 20 | 30 |
| 2 | 30 | 50 |
| 3 | — | fast->next = NULL, stop |
Middle: 30 ✓
Time: $O(n)$, Space: $O(1)$
Q4. Write a function to detect a cycle in a linked list (Floyd’s cycle detection).
Floyd’s Tortoise and Hare Algorithm:
int hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1; // Cycle detected!
}
return 0; // No cycle
}
How it works:
slowmoves 1 step,fastmoves 2 steps- If there’s no cycle,
fastreaches NULL - If there’s a cycle,
fastwill eventually catch up toslowinside the cycle (they meet)
Why they must meet: In the cycle, fast closes the gap by 1 node per step. If the cycle has length $C$, they meet within $C$ steps after both enter the cycle.
Finding the starting node of the cycle:
Node* findCycleStart(Node* head) {
Node *slow = head, *fast = head;
// Step 1: Detect cycle
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (fast == NULL || fast->next == NULL) return NULL;
// Step 2: Find start — move slow to head, advance both by 1
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // Start of cycle
}
Time: $O(n)$, Space: $O(1)$
Q5. Write a function to merge two sorted linked lists into one sorted list.
Node* mergeSorted(Node* a, Node* b) {
if (a == NULL) return b;
if (b == NULL) return a;
Node* result = NULL;
if (a->data <= b->data) {
result = a;
result->next = mergeSorted(a->next, b);
} else {
result = b;
result->next = mergeSorted(a, b->next);
}
return result;
}
Iterative version:
Node* mergeSortedIterative(Node* a, Node* b) {
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
while (a != NULL && b != NULL) {
if (a->data <= b->data) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = (a != NULL) ? a : b;
return dummy.next;
}
Trace: a: 1→3→5, b: 2→4→6
| Step | Compare | Result |
|---|---|---|
| 1 | 1 vs 2 → take 1 | 1→ |
| 2 | 3 vs 2 → take 2 | 1→2→ |
| 3 | 3 vs 4 → take 3 | 1→2→3→ |
| 4 | 5 vs 4 → take 4 | 1→2→3→4→ |
| 5 | 5 vs 6 → take 5 | 1→2→3→4→5→ |
| 6 | append remaining | 1→2→3→4→5→6→NULL |
Time: $O(n + m)$, Space: $O(1)$ iterative, $O(n+m)$ recursive
Q6. Explain why inserting at the beginning of a singly linked list is $O(1)$ but inserting at the end is $O(n)$.
Insert at beginning — $O(1)$:
1. Create new node
2. newNode->next = head ← Just one pointer update
3. head = newNode ← One assignment
We already have the head pointer, so no traversal is needed.
Insert at end — $O(n)$:
1. Create new node
2. Start at head
3. Traverse to the LAST node (temp->next == NULL) ← O(n) traversal
4. temp->next = newNode
We don’t have a pointer to the last node, so we must traverse the entire list.
How to make insert-at-end $O(1)$: Maintain a tail pointer alongside head. Then:
tail->next = newNode;
tail = newNode; // O(1) — no traversal!
Practice Questions — Doubly Linked List
Q1. Implement a doubly linked list with insert (beginning, end, after node) and delete (beginning, end, specific node) operations.
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
DNode* createDNode(int value) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = value;
newNode->prev = newNode->next = NULL;
return newNode;
}
// --- INSERT OPERATIONS ---
DNode* insertAtBeginning(DNode* head, int value) {
DNode* newNode = createDNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode;
}
DNode* insertAtEnd(DNode* head, int value) {
DNode* newNode = createDNode(value);
if (head == NULL) return newNode;
DNode* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
return head;
}
DNode* insertAfterNode(DNode* head, int target, int value) {
DNode* temp = head;
while (temp != NULL && temp->data != target)
temp = temp->next;
if (temp == NULL) { printf("Node %d not found!\n", target); return head; }
DNode* newNode = createDNode(value);
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL) temp->next->prev = newNode;
temp->next = newNode;
return head;
}
// --- DELETE OPERATIONS ---
DNode* deleteAtBeginning(DNode* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
DNode* temp = head;
head = head->next;
if (head != NULL) head->prev = NULL;
free(temp);
return head;
}
DNode* deleteAtEnd(DNode* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
if (head->next == NULL) { free(head); return NULL; }
DNode* temp = head;
while (temp->next != NULL) temp = temp->next;
temp->prev->next = NULL;
free(temp);
return head;
}
DNode* deleteNode(DNode* head, int key) {
DNode* temp = head;
while (temp != NULL && temp->data != key)
temp = temp->next;
if (temp == NULL) { printf("Node %d not found!\n", key); return head; }
if (temp->prev != NULL) temp->prev->next = temp->next;
else head = temp->next; // Deleting head
if (temp->next != NULL) temp->next->prev = temp->prev;
free(temp);
return head;
}
Q2. Write a function to reverse a doubly linked list.
DNode* reverseDLL(DNode* head) {
DNode* temp = NULL;
DNode* curr = head;
while (curr != NULL) {
// Swap prev and next pointers
temp = curr->prev;
curr->prev = curr->next;
curr->next = temp;
curr = curr->prev; // Move to next (which is now prev)
}
// After loop, temp->prev is the new head
if (temp != NULL)
head = temp->prev;
return head;
}
Trace for NULL ← 10 ⇄ 20 ⇄ 30 → NULL:
| Step | curr | Action | State |
|---|---|---|---|
| 1 | 10 | Swap prev/next of 10 | 10’s next=NULL, prev=20 |
| 2 | 20 | Swap prev/next of 20 | 20’s next=10, prev=30 |
| 3 | 30 | Swap prev/next of 30 | 30’s next=20, prev=NULL |
| 4 | NULL | Done | NULL ← 30 ⇄ 20 ⇄ 10 → NULL |
Time: $O(n)$, Space: $O(1)$
Q3. Compare singly and doubly linked lists. When would you choose one over the other?
| Feature | Singly LL | Doubly LL |
|---|---|---|
| Pointers per node | 1 (next) |
2 (prev + next) |
| Memory per node | Less | More (extra pointer) |
| Forward traversal | ✓ | ✓ |
| Backward traversal | ✗ | ✓ |
| Insert at beginning | $O(1)$ | $O(1)$ |
| Delete given node | $O(n)$ — need predecessor | $O(1)$ — have prev pointer |
| Insert before a node | $O(n)$ | $O(1)$ |
| Implementation | Simpler | More complex |
Choose Singly LL when:
- Memory is constrained
- Only forward traversal is needed
- Implementation simplicity matters
- Example: Simple stack implementation, hash table chaining
Choose Doubly LL when:
- Need bidirectional traversal
- Frequent deletion of specific nodes
- Need to insert before a given node
- Example: Browser history (back/forward), LRU cache, text editor undo/redo
Q4. Why is deletion $O(1)$ in a doubly linked list when given a pointer to the node?
In a doubly linked list, each node has both prev and next pointers. Given a pointer to node X:
// Delete node X in O(1)
if (X->prev != NULL) X->prev->next = X->next; // Skip X from left
if (X->next != NULL) X->next->prev = X->prev; // Skip X from right
free(X);
Before: ... ← A ⇄ X ⇄ B → ...
After: ... ← A ⇄ B → ...
We can directly access both neighbors (A via X->prev, B via X->next) without traversing.
In a singly linked list, given pointer to X:
- We know
X->next(B), but we don’t know who points to X (A) - Must traverse from head to find A (the predecessor): $O(n)$
This is why doubly linked lists are used in LRU caches — frequent $O(1)$ deletions.
Q5. Implement a function to display a doubly linked list in both forward and reverse direction.
void displayForward(DNode* head) {
printf("Forward: ");
DNode* temp = head;
while (temp != NULL) {
printf("%d ⇄ ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void displayReverse(DNode* head) {
if (head == NULL) { printf("Reverse: NULL\n"); return; }
// Go to the last node
DNode* temp = head;
while (temp->next != NULL)
temp = temp->next;
// Traverse backward using prev
printf("Reverse: ");
while (temp != NULL) {
printf("%d ⇄ ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}
Example output for list 10 ⇄ 20 ⇄ 30:
Forward: 10 ⇄ 20 ⇄ 30 ⇄ NULL
Reverse: 30 ⇄ 20 ⇄ 10 ⇄ NULL
Note: If we maintain a tail pointer, displayReverse becomes more efficient — no need to traverse to the end first.
Practice Questions — Circular Linked List
Q1. Implement a singly circular linked list with insert and delete at beginning and end.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int value) {
Node* n = (Node*)malloc(sizeof(Node));
n->data = value;
n->next = n; // Points to itself (single-node circle)
return n;
}
Node* insertAtBeginning(Node* head, int value) {
Node* newNode = createNode(value);
if (head == NULL) return newNode;
// Find last node
Node* last = head;
while (last->next != head)
last = last->next;
newNode->next = head;
last->next = newNode; // Last now points to new head
return newNode;
}
Node* insertAtEnd(Node* head, int value) {
Node* newNode = createNode(value);
if (head == NULL) return newNode;
// Find last node
Node* last = head;
while (last->next != head)
last = last->next;
last->next = newNode;
newNode->next = head; // New last points to head
return head;
}
Node* deleteAtBeginning(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
if (head->next == head) { free(head); return NULL; } // Only one node
Node* last = head;
while (last->next != head)
last = last->next;
Node* temp = head;
head = head->next;
last->next = head;
free(temp);
return head;
}
Node* deleteAtEnd(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return NULL; }
if (head->next == head) { free(head); return NULL; }
Node* temp = head;
while (temp->next->next != head)
temp = temp->next;
free(temp->next);
temp->next = head;
return head;
}
void display(Node* head) {
if (head == NULL) { printf("List is empty!\n"); return; }
Node* temp = head;
do {
printf("%d → ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to %d)\n", head->data);
}
Q2. How do you detect the last node in a circular linked list? How does traversal differ from a regular linked list?
Detecting the last node:
- In a regular linked list:
node->next == NULL - In a circular linked list:
node->next == head
Traversal differences:
| Aspect | Regular LL | Circular LL |
|---|---|---|
| Stop condition | temp != NULL |
temp->next != head or use do-while |
| Risk | None | Infinite loop if not careful! |
| Start | temp = head |
temp = head |
Regular LL traversal:
while (temp != NULL) {
// process
temp = temp->next;
}
Circular LL traversal (must use do-while):
if (head == NULL) return;
Node* temp = head;
do {
// process temp
temp = temp->next;
} while (temp != head);
A while loop starting with temp != head would skip the head node entirely. The do-while processes head first, then checks the condition.
Q3. Write a function to count the number of nodes in a circular linked list.
int countNodes(Node* head) {
if (head == NULL) return 0;
int count = 0;
Node* temp = head;
do {
count++;
temp = temp->next;
} while (temp != head);
return count;
}
Trace for circular list 10 → 20 → 30 → (back to 10):
| Step | temp | count |
|---|---|---|
| 1 | 10 | 1 |
| 2 | 20 | 2 |
| 3 | 30 | 3 |
| 4 | 10 (= head) → stop | 3 |
Returns: 3
Q4. Solve the Josephus Problem using a circular linked list.
Problem: $n$ people stand in a circle. Starting from person 1, every $k$-th person is eliminated until one remains. Find the survivor.
int josephus(int n, int k) {
// Create circular linked list of n persons
Node* head = createNode(1);
Node* prev = head;
for (int i = 2; i <= n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = i;
prev->next = newNode;
prev = newNode;
}
prev->next = head; // Make it circular
// Eliminate every k-th person
Node* curr = head;
Node* temp;
while (curr->next != curr) { // Until one person remains
// Move to (k-1)th node (the one before the k-th)
for (int i = 1; i < k - 1; i++)
curr = curr->next;
// Remove k-th node
temp = curr->next;
printf("Eliminated: %d\n", temp->data);
curr->next = temp->next;
free(temp);
curr = curr->next; // Start counting from next
}
int survivor = curr->data;
free(curr);
return survivor;
}
Trace for n=5, k=3:
Circle: 1 → 2 → 3 → 4 → 5 → (back to 1)
| Round | Start | Eliminated | Remaining |
|---|---|---|---|
| 1 | 1 | 3 | 1, 2, 4, 5 |
| 2 | 4 | 1 | 2, 4, 5 |
| 3 | 2 | 5 | 2, 4 |
| 4 | 2 | 4 | 2 |
Survivor: Person 2
Q5. Compare singly linked list, doubly linked list, and circular linked list.
| Feature | Singly LL | Doubly LL | Circular LL |
|---|---|---|---|
| Pointers/node | 1 (next) |
2 (prev, next) |
1 (next) |
| Last node points to | NULL |
NULL |
head |
| Forward traversal | ✓ | ✓ | ✓ (with cycle) |
| Backward traversal | ✗ | ✓ | ✗ |
| Insert at begin | $O(1)$ | $O(1)$ | $O(n)$* |
| Insert at end | $O(n)$ | $O(n)$ | $O(n)$* |
| Delete given node | $O(n)$ | $O(1)$ | $O(n)$ |
| End detection | next==NULL |
next==NULL |
next==head |
| Memory | Least | Most | Least |
| Applications | Simple lists, stacks | Browser, LRU cache | Round-robin, playlists |
*$O(1)$ if a tail pointer is maintained.
Choose based on need:
- Singly: Basic, memory-efficient list operations
- Doubly: Need backward traversal or $O(1)$ deletion
- Circular: Cyclic processes (scheduling, turn-based games)
Practice Questions — Applications
Q1. Represent the polynomial $3x^4 + 2x^2 + 5$ as a linked list. Draw the diagram.
Each node stores: coefficient, exponent, and next pointer.
[3|4|•] → [2|2|•] → [5|0|•] → NULL
coeff exp coeff exp coeff exp
Diagram:
head → [3, 4] → [2, 2] → [5, 0] → NULL
↑ ↑ ↑
3x^4 2x^2 5x^0 (= 5)
Node structure in C:
typedef struct PolyNode {
int coeff;
int exp;
struct PolyNode* next;
} PolyNode;
Key rules:
- Nodes are stored in decreasing order of exponent
- Zero-coefficient terms are not stored (sparse representation)
- Constant term has exponent = 0
Q2. Write a C function to add two polynomials represented as linked lists.
typedef struct PolyNode {
int coeff, exp;
struct PolyNode* next;
} PolyNode;
PolyNode* createPolyNode(int coeff, int exp) {
PolyNode* node = (PolyNode*)malloc(sizeof(PolyNode));
node->coeff = coeff;
node->exp = exp;
node->next = NULL;
return node;
}
PolyNode* addPolynomials(PolyNode* p1, PolyNode* p2) {
PolyNode* result = NULL;
PolyNode* tail = NULL;
while (p1 != NULL && p2 != NULL) {
PolyNode* newNode;
if (p1->exp > p2->exp) {
newNode = createPolyNode(p1->coeff, p1->exp);
p1 = p1->next;
} else if (p1->exp < p2->exp) {
newNode = createPolyNode(p2->coeff, p2->exp);
p2 = p2->next;
} else {
int sum = p1->coeff + p2->coeff;
if (sum != 0) {
newNode = createPolyNode(sum, p1->exp);
} else {
p1 = p1->next; p2 = p2->next;
continue; // Skip zero-coefficient terms
}
p1 = p1->next;
p2 = p2->next;
}
if (result == NULL) result = tail = newNode;
else { tail->next = newNode; tail = newNode; }
}
// Append remaining terms
while (p1 != NULL) {
PolyNode* n = createPolyNode(p1->coeff, p1->exp);
if (result == NULL) result = tail = n;
else { tail->next = n; tail = n; }
p1 = p1->next;
}
while (p2 != NULL) {
PolyNode* n = createPolyNode(p2->coeff, p2->exp);
if (result == NULL) result = tail = n;
else { tail->next = n; tail = n; }
p2 = p2->next;
}
return result;
}
Example: $P_1 = 3x^3 + 2x^2 + 5$ and $P_2 = 4x^3 + x$
| p1 term | p2 term | Action | Result term |
|---|---|---|---|
| 3x³ | 4x³ | Same exp → add | 7x³ |
| 2x² | x¹ | p1 exp > p2 exp → take p1 | 2x² |
| 5x⁰ | x¹ | p1 exp < p2 exp → take p2 | x¹ |
| 5x⁰ | NULL | Append p1 | 5 |
Result: $7x^3 + 2x^2 + x + 5$
Time: $O(m + n)$ where $m$ and $n$ are the number of terms.
Q3. What is a sparse matrix? When is sparse representation beneficial?
Sparse Matrix: A matrix in which the majority of elements are zero.
Formally, a matrix is considered sparse when the number of non-zero elements is much less than the total elements: $\text{NNZ} \ll m \times n$.
Normal representation of a $1000 \times 1000$ matrix with 50 non-zero elements:
- Storage: $1000 \times 1000 = 1{,}000{,}000$ integers
- Mostly zeros — huge waste!
Sparse representation (triplet form):
- Store only non-zero elements as
(row, col, value)triples - Storage: $3 \times 50 = 150$ integers + metadata
- Savings: 99.985% less memory
When sparse representation is beneficial:
- Mostly zeros (e.g., >50% zeros)
- Large dimensions (e.g., adjacency matrices of sparse graphs)
- Memory-constrained environments
- Operations can be optimized to skip zeros
When NOT beneficial:
- Dense matrices (most elements are non-zero)
- Small matrices (overhead of triplet storage not worth it)
Q4. Represent the given matrix in triplet form.
Matrix:
0 0 0 5
0 3 0 0
0 0 0 0
2 0 0 0
Triplet form: (rows, cols, numNonZero) followed by (row, col, value) for each non-zero.
| Index | Row | Col | Value |
|---|---|---|---|
| Header | 4 | 4 | 3 |
| 0 | 0 | 3 | 5 |
| 1 | 1 | 1 | 3 |
| 2 | 3 | 0 | 2 |
C representation:
typedef struct {
int row, col, value;
} Element;
typedef struct {
int rows, cols, numNonZero;
Element data[100];
} SparseMatrix;
SparseMatrix m;
m.rows = 4; m.cols = 4; m.numNonZero = 3;
m.data[0] = (Element){0, 3, 5};
m.data[1] = (Element){1, 1, 3};
m.data[2] = (Element){3, 0, 2};
Storage comparison:
- Normal: $4 \times 4 = 16$ integers
- Sparse: $3 \times 3 + 3 = 12$ integers (already better!)
- For a $100 \times 100$ matrix with 3 non-zero: Normal = 10,000 vs Sparse = 12
Q5. Explain Fast Transpose with an example. Why is it $O(cols + numNonZero)$?
Simple Transpose: For each column $c$ (0 to cols-1), scan ALL elements looking for those in column $c$. Time: $O(\text{cols} \times \text{NNZ})$.
Fast Transpose avoids repeated scanning by precomputing target positions (using counting sort principle).
Algorithm:
rowTerms[c]= count of non-zero elements in column $c$startPos[c]= starting index for column $c$ in the result- Place each element directly into its correct position
Example: Transpose the sparse matrix:
| Row | Col | Value |
|---|---|---|
| 0 | 0 | 15 |
| 0 | 3 | 22 |
| 1 | 1 | 11 |
| 1 | 2 | 3 |
| 2 | 3 | -6 |
Step 1 — Count elements per column:
| Col | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| rowTerms | 1 | 1 | 1 | 2 |
Step 2 — Compute starting positions (prefix sum):
| Col | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| startPos | 0 | 1 | 2 | 3 |
Step 3 — Place elements:
| Original (row,col,val) | target col | position = startPos[col]++ | Result |
|---|---|---|---|
| (0,0,15) | 0 | pos=0, startPos[0]=1 | result[0]=(0,0,15) |
| (0,3,22) | 3 | pos=3, startPos[3]=4 | result[3]=(3,0,22) |
| (1,1,11) | 1 | pos=1, startPos[1]=2 | result[1]=(1,1,11) |
| (1,2,3) | 2 | pos=2, startPos[2]=3 | result[2]=(2,1,3) |
| (2,3,-6) | 3 | pos=4, startPos[3]=5 | result[4]=(3,2,-6) |
Transposed result: (swap row↔col in each element)
| Row | Col | Value |
|---|---|---|
| 0 | 0 | 15 |
| 1 | 1 | 11 |
| 2 | 1 | 3 |
| 3 | 0 | 22 |
| 3 | 2 | -6 |
Why $O(\text{cols} + \text{NNZ})$:
- Step 1 (count): Scan all NNZ elements → $O(\text{NNZ})$
- Step 2 (prefix sum): Loop through cols → $O(\text{cols})$
- Step 3 (place): Scan all NNZ elements → $O(\text{NNZ})$
- Total: $O(\text{cols} + \text{NNZ})$ — each element is processed exactly once!
Q6. Write a C function to multiply two polynomials using linked lists.
PolyNode* multiplyPolynomials(PolyNode* p1, PolyNode* p2) {
PolyNode* result = NULL;
for (PolyNode* i = p1; i != NULL; i = i->next) {
for (PolyNode* j = p2; j != NULL; j = j->next) {
int coeff = i->coeff * j->coeff;
int exp = i->exp + j->exp;
result = insertTerm(result, coeff, exp);
}
}
return result;
}
// Helper: insert term into polynomial (combine like terms)
PolyNode* insertTerm(PolyNode* poly, int coeff, int exp) {
if (coeff == 0) return poly;
// Check if term with same exponent exists
PolyNode* temp = poly;
while (temp != NULL) {
if (temp->exp == exp) {
temp->coeff += coeff;
return poly; // Combined with existing term
}
temp = temp->next;
}
// Insert in decreasing order of exponent
PolyNode* newNode = createPolyNode(coeff, exp);
if (poly == NULL || poly->exp < exp) {
newNode->next = poly;
return newNode;
}
temp = poly;
while (temp->next != NULL && temp->next->exp > exp)
temp = temp->next;
newNode->next = temp->next;
temp->next = newNode;
return poly;
}
Example: $(2x^2 + 3) \times (x + 1)$
| $i$ term | $j$ term | Product |
|---|---|---|
| $2x^2$ | $x$ | $2x^3$ |
| $2x^2$ | $1$ | $2x^2$ |
| $3$ | $x$ | $3x$ |
| $3$ | $1$ | $3$ |
Result: $2x^3 + 2x^2 + 3x + 3$
Time: $O(m \times n)$ for the multiplication, plus $O(m \times n)$ for insertions. Total: $O(m \times n \times (m+n))$ worst case.
Comprehensive Unit IV Practice Set
1. Define a linked list. How does it differ from an array?
Linked List: A linear data structure where elements (nodes) are stored at non-contiguous memory locations and connected via pointers. Each node contains data and a pointer to the next node.
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous, static | Non-contiguous, dynamic |
| Size | Fixed at declaration | Grows/shrinks at runtime |
| Access | $O(1)$ random access by index | $O(n)$ sequential access |
| Insertion | $O(n)$ (shifting needed) | $O(1)$ at beginning |
| Deletion | $O(n)$ (shifting needed) | $O(1)$ if pointer given (DLL) |
| Memory waste | Possible (unused slots) | No waste (allocate as needed) |
| Extra memory | None | Pointer(s) per node |
| Cache | Excellent locality | Poor (scattered nodes) |
2. What is dynamic memory management? Explain malloc, calloc, realloc, and free.
Dynamic memory management is the process of allocating and deallocating memory at runtime from the heap.
| Function | Syntax | Purpose |
|---|---|---|
malloc |
ptr = (type*)malloc(size) |
Allocate size bytes, uninitialized |
calloc |
ptr = (type*)calloc(n, size) |
Allocate n*size bytes, initialized to 0 |
realloc |
ptr = (type*)realloc(ptr, newSize) |
Resize previously allocated block |
free |
free(ptr) |
Deallocate memory pointed to by ptr |
Examples:
// malloc — allocate 5 ints (uninitialized, may contain garbage)
int* a = (int*)malloc(5 * sizeof(int));
// calloc — allocate 5 ints (initialized to 0)
int* b = (int*)calloc(5, sizeof(int));
// realloc — resize to 10 ints (preserves existing data)
a = (int*)realloc(a, 10 * sizeof(int));
// free — release memory
free(a);
free(b);
Common errors:
- Memory leak: Forgetting to
free→ memory stays allocated forever - Dangling pointer: Using
ptrafterfree(ptr)→ undefined behavior - Double free: Calling
free(ptr)twice → crash
3. Draw and explain node structures for singly, doubly, and circular linked lists.
Singly Linked List Node:
[data | next] → [data | next] → NULL
struct Node { int data; struct Node* next; };
Doubly Linked List Node:
NULL ← [prev | data | next] ⇄ [prev | data | next] → NULL
struct DNode { int data; struct DNode *prev, *next; };
Circular Linked List Node:
[data | next] → [data | next] → [data | next] ─┐
↑ │
└──────────────────────────────────────────────┘
Same structure as singly LL, but last node’s next points to head instead of NULL.
4. What is a sparse matrix? Why is linked list representation useful for sparse matrices?
A sparse matrix has mostly zero elements. Storing all elements wastes memory.
Linked list advantages for sparse matrices:
- Dynamic size — only non-zero elements are stored
- Efficient insertion/deletion — adding/removing elements doesn’t require shifting
- Memory-efficient — no wasted space for zeros
- Flexible — easy to grow/shrink as elements change
Each non-zero element is a node: (row, col, value, next).
5. Implement a complete singly linked list program in C.
See Q1 of Singly Linked List section above for the complete implementation with all operations: create, insert (beginning, end, position), delete (beginning, end, position), search, display, count.
Adding reverse:
Node* reverse(Node* head) {
Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
6. Implement a doubly linked list with forward and reverse display.
See Q1 of Doubly Linked List section for all insert/delete operations and Q5 for forward/reverse display.
7. Implement a circular linked list and solve a round-robin scheduling problem.
Circular LL implementation: See Q1 of Circular Linked List section.
Round-Robin Scheduling Simulation:
typedef struct Process {
int pid;
int burstTime;
struct Process* next;
} Process;
void roundRobin(Process* head, int timeQuantum) {
if (head == NULL) return;
int time = 0;
Process* curr = head;
while (curr->next != curr) { // More than one process
printf("Time %d: Process P%d runs for ", time, curr->pid);
if (curr->burstTime <= timeQuantum) {
// Process finishes
time += curr->burstTime;
printf("%d units (FINISHED)\n", curr->burstTime);
// Remove from circular list
Process* temp = curr;
Process* prev = curr;
while (prev->next != curr) prev = prev->next;
prev->next = curr->next;
curr = curr->next;
free(temp);
} else {
// Process partially executes
time += timeQuantum;
curr->burstTime -= timeQuantum;
printf("%d units (remaining: %d)\n", timeQuantum, curr->burstTime);
curr = curr->next;
}
}
// Last process
time += curr->burstTime;
printf("Time %d: Process P%d runs for %d units (FINISHED)\n",
time - curr->burstTime, curr->pid, curr->burstTime);
free(curr);
printf("All processes completed at time %d\n", time);
}
8. Write a C program to add two polynomials using linked lists.
$P_1 = 4x^3 + 3x^2 + 5$, $P_2 = 3x^4 + 3x^3 + 2x^2 + x$
See Q2 of Applications section for the implementation.
Tracing for these specific polynomials:
| P1 term | P2 term | Compare exp | Action | Result |
|---|---|---|---|---|
| 4x³ | 3x⁴ | 3 < 4 | Take P2 | 3x⁴ |
| 4x³ | 3x³ | 3 = 3 | Add: 4+3=7 | 3x⁴ + 7x³ |
| 3x² | 2x² | 2 = 2 | Add: 3+2=5 | 3x⁴ + 7x³ + 5x² |
| 5x⁰ | x¹ | 0 < 1 | Take P2 | 3x⁴ + 7x³ + 5x² + x |
| 5x⁰ | NULL | — | Take P1 | 3x⁴ + 7x³ + 5x² + x + 5 |
Result: $3x^4 + 7x^3 + 5x^2 + x + 5$
9. Implement sparse matrix representation using triplets. Write functions for addition and fast transpose.
#define MAX_TERMS 100
typedef struct {
int row, col, value;
} Element;
typedef struct {
int rows, cols, numNZ;
Element data[MAX_TERMS];
} SparseMatrix;
// --- Addition ---
SparseMatrix addSparse(SparseMatrix a, SparseMatrix b) {
SparseMatrix result;
result.rows = a.rows; result.cols = a.cols;
int i = 0, j = 0, k = 0;
while (i < a.numNZ && j < b.numNZ) {
int posA = a.data[i].row * a.cols + a.data[i].col;
int posB = b.data[j].row * b.cols + b.data[j].col;
if (posA < posB) result.data[k++] = a.data[i++];
else if (posA > posB) result.data[k++] = b.data[j++];
else {
int sum = a.data[i].value + b.data[j].value;
if (sum != 0) {
result.data[k] = a.data[i];
result.data[k].value = sum;
k++;
}
i++; j++;
}
}
while (i < a.numNZ) result.data[k++] = a.data[i++];
while (j < b.numNZ) result.data[k++] = b.data[j++];
result.numNZ = k;
return result;
}
// --- Fast Transpose ---
SparseMatrix fastTranspose(SparseMatrix a) {
SparseMatrix result;
result.rows = a.cols; result.cols = a.rows; result.numNZ = a.numNZ;
int rowTerms[a.cols], startPos[a.cols];
for (int i = 0; i < a.cols; i++) rowTerms[i] = 0;
// Step 1: Count elements per column
for (int i = 0; i < a.numNZ; i++)
rowTerms[a.data[i].col]++;
// Step 2: Compute starting positions
startPos[0] = 0;
for (int i = 1; i < a.cols; i++)
startPos[i] = startPos[i-1] + rowTerms[i-1];
// Step 3: Place elements
for (int i = 0; i < a.numNZ; i++) {
int j = startPos[a.data[i].col]++;
result.data[j].row = a.data[i].col;
result.data[j].col = a.data[i].row;
result.data[j].value = a.data[i].value;
}
return result;
}
10. Trace operations on a singly linked list.
Operations: insertAtEnd(10), insertAtEnd(20), insertAtBeginning(5), insertAtPosition(15, 2), deleteAtBeginning(), deleteAtEnd(), display()
| # | Operation | List State |
|---|---|---|
| 1 | insertAtEnd(10) | 10 → NULL |
| 2 | insertAtEnd(20) | 10 → 20 → NULL |
| 3 | insertAtBeginning(5) | 5 → 10 → 20 → NULL |
| 4 | insertAtPosition(15, 2) | 5 → 10 → 15 → 20 → NULL |
| 5 | deleteAtBeginning() | 10 → 15 → 20 → NULL |
| 6 | deleteAtEnd() | 10 → 15 → NULL |
| 7 | display() | Output: 10 → 15 → NULL |
Step 4 detail: Position 2 means insert after the node at index 1 (10), so 15 goes between 10 and 20.
11. Trace insertion and deletion in a doubly linked list.
Starting from empty list:
Insert 10 at beginning:
NULL ← [10] → NULL
head = 10
Insert 20 at end:
NULL ← [10] ⇄ [20] → NULL
Pointer updates: 10->next = 20, 20->prev = 10
Insert 15 after 10:
NULL ← [10] ⇄ [15] ⇄ [20] → NULL
Step 1: 15->next = 10->next (= 20)
Step 2: 15->prev = 10
Step 3: 20->prev = 15
Step 4: 10->next = 15
Delete 15 (given pointer to 15):
NULL ← [10] ⇄ [20] → NULL
Step 1: 15->prev->next = 15->next → 10->next = 20
Step 2: 15->next->prev = 15->prev → 20->prev = 10
Step 3: free(15)
$O(1)$ deletion because we have direct access to both neighbors via prev and next.
12. Compare all types of linked lists with diagrams, operations, complexities, and use cases.
1. Singly Linked List:
[10|•] → [20|•] → [30|•] → NULL
2. Doubly Linked List:
NULL ← [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] → NULL
3. Singly Circular:
[10|•] → [20|•] → [30|•] ─┐
↑ │
└──────────────────────────┘
4. Doubly Circular:
┌──⇄── [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] ──⇄──┐
│ │
└────────────────────────────────────────────────┘
| Operation | Singly | Doubly | Circular | Doubly Circular |
|---|---|---|---|---|
| Insert begin | $O(1)$ | $O(1)$ | $O(n)$ | $O(1)$ |
| Insert end | $O(n)$ | $O(n)$ | $O(n)$ | $O(1)$* |
| Delete begin | $O(1)$ | $O(1)$ | $O(n)$ | $O(1)$ |
| Delete given node | $O(n)$ | $O(1)$ | $O(n)$ | $O(1)$ |
| Search | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Memory/node | 1 ptr | 2 ptrs | 1 ptr | 2 ptrs |
*With tail pointer.
Use cases: Singly (stacks, simple lists), Doubly (browsers, LRU cache), Circular (round-robin), Doubly Circular (Fibonacci heaps).
13. Explain polynomial representation and addition using linked lists.
Representation: Each non-zero term is a node with (coeff, exp, next), sorted by decreasing exponent.
Addition algorithm:
- Compare exponents of current terms from both lists
- If equal: add coefficients, create node if sum ≠ 0
- If P1’s exp > P2’s: copy P1’s term
- If P2’s exp > P1’s: copy P2’s term
- Append remaining terms from whichever list has leftovers
Complete example:
$P_1 = 5x^4 + 3x^2 + 1$
[5|4|•] → [3|2|•] → [1|0|•] → NULL
$P_2 = 4x^3 + 3x^2 + 2x$
[4|3|•] → [3|2|•] → [2|1|•] → NULL
Addition trace:
| Step | P1 | P2 | Compare | Result |
|---|---|---|---|---|
| 1 | 5x⁴ | 4x³ | 4 > 3 → take P1 | 5x⁴ |
| 2 | 3x² | 4x³ | 2 < 3 → take P2 | 5x⁴ + 4x³ |
| 3 | 3x² | 3x² | 2 = 2 → add: 6 | 5x⁴ + 4x³ + 6x² |
| 4 | 1x⁰ | 2x¹ | 0 < 1 → take P2 | 5x⁴ + 4x³ + 6x² + 2x |
| 5 | 1x⁰ | NULL | append P1 | 5x⁴ + 4x³ + 6x² + 2x + 1 |
Time: $O(m + n)$
14. Explain sparse matrix representation, addition, and transpose.
See Q3, Q4, and Q5 of the Applications section for detailed explanations.
Summary comparison — Simple vs Fast Transpose:
| Aspect | Simple Transpose | Fast Transpose |
|---|---|---|
| Algorithm | For each col, scan all elements | Counting sort approach |
| Time | $O(\text{cols} \times \text{NNZ})$ | $O(\text{cols} + \text{NNZ})$ |
| Space | $O(\text{NNZ})$ for result | $O(\text{NNZ} + \text{cols})$ for result + arrays |
| # Passes | cols passes over data | 3 single passes |
| Best for | Small matrices | Large sparse matrices |
15. Discuss the trade-offs between arrays and linked lists for implementing the List ADT.
| Criteria | Array | Linked List |
|---|---|---|
| Random access | $O(1)$ — direct index | $O(n)$ — must traverse |
| Insert at begin | $O(n)$ — shift all | $O(1)$ — just pointer work |
| Insert at end | $O(1)$ amortized (dynamic array) | $O(n)$ or $O(1)$ with tail |
| Insert at middle | $O(n)$ — shift elements | $O(n)$ — traverse + $O(1)$ insert |
| Delete | $O(n)$ — shift elements | $O(1)$ if pointer given (DLL) |
| Memory | Compact, may over-allocate | Extra pointer per node |
| Cache performance | Excellent | Poor |
| Dynamic size | Needs realloc | Natural |
| Memory fragmentation | None | Possible |
Choose Array when:
- Frequent random access (index-based lookups)
- Cache performance matters
- Size is mostly known in advance
- Example: lookup tables, buffers, sorting
Choose Linked List when:
- Frequent insertions/deletions at arbitrary positions
- Size varies significantly
- No random access needed
- Example: implementing stacks/queues, adjacency lists, polynomials