Unit IV — Lists

Syllabus Coverage: List as ADT, Concept of linked organization of data against linked list. Singly linked list, doubly linked list, circular linked list implementation and Analysis. Operations on Linked list — insertion, deletion, searching. Representation & manipulations of polynomials/sets using linked lists. Dynamic memory management. Representation of sparse matrix. Addition and transpose of sparse matrix. (09 Hours)

Table of Contents

Glossary — Key Terms

1 — Introduction to Linked Lists

1.1 List as an ADT

ADT List:
    Data:
        An ordered collection of elements
    
    Operations:
        insert(pos, element)   → Insert at position            — O(n)
        delete(pos)            → Delete element at position     — O(n)
        search(element)        → Find element, return position  — O(n)
        get(pos)               → Return element at position     — O(n)
        length()               → Return count of elements       — O(1) or O(n)
        isEmpty()              → Check if list is empty         — O(1)
        display()              → Print all elements             — O(n)
    
    Implementations:
        1. Array-based (sequential)
        2. Linked list (pointer-based)

1.2 Array vs Linked Organization

1.3 Node Structure & Pointers

Each element in a linked list is stored in a node:

┌──────┬──────┐
│ data │ next │ ← Singly linked list node
└──────┴──────┘

┌──────┬──────┬──────┐
│ prev │ data │ next │ ← Doubly linked list node
└──────┴──────┴──────┘

In C:

// Singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Doubly linked list node
struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
};

1.4 Dynamic Memory Management in C

// Creating a new node dynamically
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

2 — Singly Linked List

2.1 Structure & Visualization

head → [10|•] → [20|•] → [30|•] → [40|•] → NULL

• head is a pointer to the first node
• Each node’s next points to the next node
• The last node’s next is NULL (end marker)

2.2 Creating a Node

#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;
}

🔍 Line-by-Line Logic:

• (Node*)malloc(sizeof(Node)) — malloc allocates exactly sizeof(Node) bytes on the heap (enough for one int + one pointer). The cast (Node*) converts the generic void* returned by malloc into our specific node pointer type.
• newNode->next = NULL — Critical initialization! A newly created node doesn’t connect to anything yet. Setting next to NULL prevents a dangling pointer. Without this, next would contain garbage — leading to crashes when traversing.
• Why return a pointer? — The node lives on the heap, not the stack. Returning a pointer lets the caller use this node long after createNode returns. If we returned a local struct, it would vanish when the function exits.

2.3 Traversal (Display)

void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int length(Node* head) {
    int count = 0;
    Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

🔍 Why This Logic:

• Node* temp = head — We use a temporary pointer so we don’t lose the head. If we moved head itself, we’d lose access to the beginning of the list permanently.
• while (temp != NULL) — A linked list has no length field — the only way to know when we’ve reached the end is to check for NULL. This is the universal “end-of-list” sentinel.
• temp = temp->next — This is the linked-list equivalent of i++ in arrays. Each step follows the pointer chain to the next node.
• Time is $O(n)$ — We must visit every single node. There’s no shortcut because nodes aren’t contiguous in memory — unlike arrays where you can jump to any index.

Time: $O(n)$ — must visit each node

2.4 Insertion — Beginning, End, At Position

Insert at Beginning — $O(1)$

Node* insertAtBeginning(Node* head, int value) {
    Node* newNode = createNode(value);
    newNode->next = head;  // New node points to old head
    head = newNode;         // Head now points to new node
    return head;
}

🔍 Why This Logic:

• newNode->next = head — The new node’s next must point to the current first node. This links the new node into the chain BEFORE updating head.
• head = newNode — Now head points to the new node, making it the first element.
• Order matters! — If we did head = newNode first, we’d lose the reference to the old first node. Always link the new node first, then update head.
• Why $O(1)$? — No traversal needed. We directly manipulate the head pointer regardless of list length. This is the fastest linked list operation.
• Why return head? — In C, function parameters are passed by value. Changing head inside the function doesn’t affect the caller’s copy. Returning the new head lets the caller update it: head = insertAtBeginning(head, 10);

Before: head → [20|•] → [30|•] → NULL
Insert 10 at beginning:
After:  head → [10|•] → [20|•] → [30|•] → NULL

Insert at End — $O(n)$

Node* insertAtEnd(Node* head, int value) {
    Node* newNode = createNode(value);
    
    if (head == NULL)   // Empty list
        return newNode;
    
    Node* temp = head;
    while (temp->next != NULL)  // Traverse to last node
        temp = temp->next;
    
    temp->next = newNode;
    return head;
}

🔍 Line-by-Line Logic:

• if (head == NULL) return newNode — Edge case: if the list is empty, the new node IS the entire list. Return it as head.
• while (temp->next != NULL) — We stop when temp->next is NULL, meaning temp is the last node. If we checked temp != NULL instead, we’d go one step too far and temp would be NULL — we couldn’t attach the new node.
• temp->next = newNode — The old last node now points to the new node. The new node’s next is already NULL (set in createNode), so it becomes the new tail.
• Why $O(n)$? — We must traverse the entire list to find the last node. This is the main disadvantage of singly linked lists. Maintaining a tail pointer would make this $O(1)$.

Insert at Position — $O(n)$

Node* insertAtPosition(Node* head, int value, int pos) {
    if (pos == 0) return insertAtBeginning(head, value);
    
    Node* newNode = createNode(value);
    Node* temp = head;
    
    for (int i = 0; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;
    
    if (temp == NULL) {
        printf("Position out of range!\n");
        free(newNode);
        return head;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    return head;
}

🔍 Line-by-Line Logic:

• if (pos == 0) — Special case: inserting at position 0 means inserting at the beginning. Reuse the existing function to avoid code duplication.
• for (int i = 0; i < pos - 1 ...) — We traverse to the node at position pos-1 (the node BEFORE where we want to insert). We need this predecessor to splice in the new node.
• pos - 1, not pos — To insert between nodes A and B, we need a pointer to A. If we traverse to position pos, we’d be at B and couldn’t access A (no prev pointer in singly LL).
• temp == NULL check — If the user gives a position beyond the list length, temp becomes NULL during traversal. We catch this, free the wasted node, and return.
• newNode->next = temp->next; temp->next = newNode — Two-step splice: (1) new node points to what was after temp, (2) temp points to new node. Order matters — reversing these would lose the link to the rest of the list.

Before: head → [10|•] → [20|•] → [30|•] → NULL
                         pos-1 ↑    pos ↑

Step 1: newNode → [25|•]
Step 2: newNode->next = temp->next  (25 points to 30)
Step 3: temp->next = newNode        (20 points to 25)

After:  head → [10|•] → [20|•] → [25|•] → [30|•] → NULL

2.5 Deletion — Beginning, End, At Position

Delete at Beginning — $O(1)$

Node* deleteAtBeginning(Node* head) {
    if (head == NULL) {
        printf("List is empty!\n");
        return NULL;
    }
    Node* temp = head;
    head = head->next;
    free(temp);
    return head;
}

🔍 Why This Logic:

• Node* temp = head — Save the current head before moving it. Without temp, after head = head->next, we lose access to the old first node and can never free it → memory leak.
• head = head->next — The second node becomes the new head. If the list had only one node, head->next is NULL, so head becomes NULL (empty list).
• free(temp) — Release the old head’s memory back to the heap. This is mandatory in C — there’s no garbage collector.
• Why $O(1)$? — We only touch the head. No traversal needed regardless of list size.

Delete at End — $O(n)$

Node* deleteAtEnd(Node* head) {
    if (head == NULL) return NULL;
    
    if (head->next == NULL) {   // Only one node
        free(head);
        return NULL;
    }
    
    Node* temp = head;
    while (temp->next->next != NULL)   // Stop at second-to-last
        temp = temp->next;
    
    free(temp->next);
    temp->next = NULL;
    return head;
}

🔍 Line-by-Line Logic:

• head->next == NULL check — If there’s only one node, just free it and return NULL. Without this special case, temp->next->next would dereference NULL->next → crash.
• while (temp->next->next != NULL) — We need the second-to-last node, not the last one. Why? Because after deleting the last node, the second-to-last must become the new tail (its next set to NULL). There’s no prev pointer in singly LL, so we must stop one step early.
• free(temp->next); temp->next = NULL — Delete the last node and make the second-to-last the new tail.
• Why $O(n)$? — We must traverse to find the second-to-last node. A tail pointer alone wouldn’t help because we’d still need the node before tail. A doubly linked list solves this.

Delete at Position — $O(n)$

Node* deleteAtPosition(Node* head, int pos) {
    if (head == NULL) 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("Position out of range!\n");
        return head;
    }
    
    Node* toDelete = temp->next;
    temp->next = toDelete->next;
    free(toDelete);
    return head;
}

🔍 Why This Logic:

• pos == 0 delegates to deleteAtBeginning — Deleting position 0 changes the head, which needs special handling.
• Traverse to pos - 1 — Same reason as insertion: we need the node BEFORE the deletion target so we can relink around it.
• toDelete = temp->next — Save a pointer to the node we’ll delete. This is the node at position pos.
• temp->next = toDelete->next — The predecessor now points to the node AFTER the deleted one, effectively removing the target from the chain.
• free(toDelete) — Release the deleted node’s memory. Without this, the node is unreachable but still occupying heap memory (memory leak).

2.6 Search

int search(Node* head, int key) {
    Node* temp = head;
    int pos = 0;
    while (temp != NULL) {
        if (temp->data == key)
            return pos;
        temp = temp->next;
        pos++;
    }
    return -1;  // Not found
}
// Time: O(n)

🔍 Why This Logic:

• Linear scan — Unlike arrays, linked lists don’t support random access. We can’t jump to the middle, so even binary search is impossible. We must check nodes one by one.
• pos counter — We track position as we traverse so we can return WHERE the key was found (not just whether it exists).
• return -1 for not found — Convention: -1 signals absence since valid positions are non-negative.
• Why not binary search? — Binary search requires $O(1)$ access to the middle element. In a linked list, finding the middle takes $O(n)$ traversal, which defeats the purpose. This is where arrays excel.

2.7 Reversing a Singly Linked List

Reversing a linked list means making the last node the head and reversing every link direction.

Iterative Approach (3-Pointer Technique):

Node* reverseList(Node* head) {
    Node *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;   // Save next node
        curr->next = prev;   // Reverse the link
        prev = curr;         // Move prev forward
        curr = next;         // Move curr forward
    }
    return prev;  // prev is the new head
}

🔍 Line-by-Line Logic:

• Three pointers: prev (the reversed portion so far), curr (the node we’re processing), next (saved link to the rest of the list).
• next = curr->next — We MUST save the next node before overwriting curr->next. Otherwise, we lose access to the rest of the list.
• curr->next = prev — This is the actual reversal: the current node now points backward instead of forward.
• prev = curr; curr = next — Advance both pointers one step. prev moves to the just-processed node; curr moves to the next unprocessed node.
• Return prev — When curr becomes NULL, we’ve processed all nodes. prev points to the last node processed, which is the new head.

Recursive Approach:

Node* reverseListRec(Node* head) {
    if (head == NULL || head->next == NULL)
        return head;  // Base case: empty or single node
    Node* newHead = reverseListRec(head->next);
    head->next->next = head;  // Make next node point back to current
    head->next = NULL;        // Remove forward link
    return newHead;
}

🔍 Why This Works:

• The recursion goes all the way to the last node (base case: head->next == NULL), which becomes the new head.
• On the way back (unwinding), head->next->next = head makes the node in front of us point backward to us.
• head->next = NULL removes our forward pointer (it will be set by the previous call, except for the original head which should point to NULL).
• Time: $O(n)$, Space: $O(n)$ due to recursion stack (iterative is better at $O(1)$ space).

2.8 Complexity Analysis

Practice Questions — Singly Linked List

3 — Doubly Linked List

3.1 Structure & Visualization

NULL ← [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] ⇄ [•|40|•] → NULL
        ↑ head

Each node has two pointers: prev (points to previous node) and next (points to next node).

3.2 Node Structure

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 = NULL;
    newNode->next = NULL;
    return newNode;
}

🔍 Why This Logic: Same as singly LL createNode, but we now initialize TWO pointers to NULL. A doubly-linked node has prev AND next. Both must be NULL because the node isn’t connected to anything yet. The extra pointer per node is the cost of bidirectional traversal.

3.3 Insertion Operations

Insert at Beginning — $O(1)$

DNode* insertAtBeginning(DNode* head, int value) {
    DNode* newNode = createDNode(value);
    
    if (head != NULL) {
        newNode->next = head;
        head->prev = newNode;
    }
    return newNode;  // New head
}

🔍 Line-by-Line Logic:

• if (head != NULL) — If the list isn’t empty, we need to link the new node to the existing first node. If the list IS empty, the new node is both head and tail — its prev and next stay NULL.
• newNode->next = head — New node points forward to the old head (same as singly LL).
• head->prev = newNode — The old head’s prev now points back to the new node. This is the EXTRA step that singly LL doesn’t have. Two-way linking requires updating pointers in BOTH directions.
• return newNode — The new node is always the new head, regardless of whether the list was empty.

Insert at End — $O(n)$

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;
}

🔍 Why This Logic:

• Traversal to the last node is identical to singly LL — follow next until NULL.
• temp->next = newNode — Old tail points forward to new node.
• newNode->prev = temp — New node points back to old tail. Both links established → fully connected.
• Same $O(n)$ time issue as singly LL. Maintaining a tail pointer would make this $O(1)$.

Insert After a Given Node — $O(1)$

void insertAfter(DNode* prevNode, int value) {
    if (prevNode == NULL) return;
    
    DNode* newNode = createDNode(value);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    
    if (prevNode->next != NULL)
        prevNode->next->prev = newNode;
    
    prevNode->next = newNode;
}

🔍 Line-by-Line Logic (4 pointer updates):

• newNode->next = prevNode->next — New node’s forward link set to what was after prevNode.
• newNode->prev = prevNode — New node’s backward link set to prevNode.
• prevNode->next->prev = newNode — The node that was after prevNode now points back to new node (instead of prevNode). The if guard prevents crash when inserting at the tail.
• prevNode->next = newNode — prevNode’s forward link updated to new node.
• Why this order? — We must set newNode’s links first (steps 1-2), then update the surrounding nodes (steps 3-4). If we updated prevNode->next first (step 4), we’d lose the reference to the node that was after it.

Before: NULL ← [10] ⇄ [20] ⇄ [30] → NULL
                        ↑ prevNode

After:  NULL ← [10] ⇄ [20] ⇄ [25] ⇄ [30] → NULL

Steps:
1. newNode->next = prevNode->next   (25 → 30)
2. newNode->prev = prevNode         (25 ← 20)
3. prevNode->next->prev = newNode   (25 ← 30)
4. prevNode->next = newNode         (20 → 25)

3.4 Deletion Operations

Delete at Beginning — $O(1)$

DNode* deleteAtBeginning(DNode* head) {
    if (head == NULL) return NULL;
    
    DNode* temp = head;
    head = head->next;
    
    if (head != NULL)
        head->prev = NULL;
    
    free(temp);
    return head;
}

🔍 Why This Logic:

• head = head->next — Advance head to the second node (same as singly LL).
• head->prev = NULL — The new head’s prev used to point to the old head. We must sever this link so the new head has no predecessor. Without this, head->prev would be a dangling pointer (pointing to freed memory).
• if (head != NULL) guard — If the list had only one node, head is now NULL. We can’t dereference NULL->prev.

Delete a Specific Node — $O(1)$ (when node pointer is given)

DNode* deleteNode(DNode* head, DNode* delNode) {
    if (head == NULL || delNode == NULL) return head;
    
    // If deleting head
    if (head == delNode)
        head = delNode->next;
    
    // Update next node's prev pointer
    if (delNode->next != NULL)
        delNode->next->prev = delNode->prev;
    
    // Update previous node's next pointer
    if (delNode->prev != NULL)
        delNode->prev->next = delNode->next;
    
    free(delNode);
    return head;
}

🔍 Line-by-Line Logic:

• This is the crown jewel of DLL — given a pointer to ANY node, delete it in $O(1)$. In a singly LL, you’d need $O(n)$ traversal to find the predecessor.
• if (head == delNode) — Special case: if deleting the head, advance head pointer.
• delNode->next->prev = delNode->prev — The node after delNode should skip over delNode and point back to delNode’s predecessor. The if guard handles deletion of the tail node (where next is NULL).
• delNode->prev->next = delNode->next — The node before delNode should skip over delNode and point to delNode’s successor. The if guard handles deletion of the head (where prev is NULL).
• Why $O(1)$? — Because delNode->prev gives us the predecessor directly. No traversal needed. This is the fundamental advantage of the extra prev pointer.

3.5 Advantages & Disadvantages

Practice Questions — Doubly Linked List

4 — Circular Linked List

4.1 Singly Circular Linked List

     ┌──────────────────────────────────┐
     ↓                                  │
    [10|•] → [20|•] → [30|•] → [40|•]──┘
     ↑ head

How to detect the end: A node is the last node if node->next == head.

// Traversal of circular linked list
void display(Node* head) {
    if (head == NULL) return;
    
    Node* temp = head;
    do {
        printf("%d → ", temp->data);
        temp = temp->next;
    } while (temp != head);   // Stop when we return to head
    printf("(back to head)\n");
}

🔍 Why do-while instead of while?

• In a regular linked list, while (temp != NULL) works because the end is marked by NULL.
• In a circular list, there IS no NULL — every node’s next points to another node. The termination condition is temp == head (we’ve gone full circle).
• But if we used while (temp != head), the loop body would NEVER execute (because temp starts equal to head). The do-while ensures we process the first node before checking the condition.
• This is the defining pattern of circular list traversal: do { ... } while (temp != head);

4.2 Doubly Circular Linked List

  ┌──────────────────────────────────────┐
  ↓                                      │
 [•|10|•] ⇄ [•|20|•] ⇄ [•|30|•] ⇄ [•|40|•]
  │                                      ↑
  └──────────────────────────────────────┘

4.3 Operations on Circular Linked List

Insert at Beginning (Singly Circular)

Node* insertAtBeginning(Node* head, int value) {
    Node* newNode = createNode(value);
    
    if (head == NULL) {
        newNode->next = newNode;  // Points to itself
        return newNode;
    }
    
    // Find the last node
    Node* last = head;
    while (last->next != head)
        last = last->next;
    
    newNode->next = head;
    last->next = newNode;   // Last node points to new head
    return newNode;          // New head
}

🔍 Line-by-Line Logic:

• newNode->next = newNode — When the list is empty, the single node must point to itself to maintain the circular property. A lone node is its own successor.
• Finding the last node: while (last->next != head) — The last node is identified by last->next == head. We need it because inserting at the beginning of a CIRCULAR list requires updating the last node’s next to point to the new head.
• last->next = newNode — The circle is maintained: last → newNode → old head → … → last.
• Why $O(n)$? — Finding the last node requires full traversal. Maintaining a tail pointer would make this $O(1)$.

Insert at End (Singly Circular)

Node* insertAtEnd(Node* head, int value) {
    Node* newNode = createNode(value);
    
    if (head == NULL) {
        newNode->next = newNode;
        return newNode;
    }
    
    Node* last = head;
    while (last->next != head)
        last = last->next;
    
    last->next = newNode;
    newNode->next = head;   // New node points back to head
    return head;
}

🔍 Why This Logic:

• Almost identical to insert-at-beginning, but the new node goes AFTER the last node instead of before head.
• last->next = newNode — Old last node points to new node.
• newNode->next = head — New node (now the last) completes the circle by pointing back to head.
• Head doesn’t change — Unlike insert-at-beginning, the first element stays the same. We return head unchanged.

Delete at Beginning (Singly Circular)

Node* deleteAtBeginning(Node* head) {
    if (head == NULL) return NULL;
    
    if (head->next == head) {   // Only one node
        free(head);
        return NULL;
    }
    
    Node* last = head;
    while (last->next != head)
        last = last->next;
    
    Node* temp = head;
    head = head->next;
    last->next = head;    // Last node now points to new head
    free(temp);
    return head;
}

🔍 Line-by-Line Logic:

• head->next == head — If the node points to itself, it’s the only node. Free it and return NULL.
• Finding last node again — Just like insertion, we need the last node so we can update last->next to point to the new head (maintaining the circle).
• last->next = head — After advancing head to the second node, the last node must now point to this new head. Without this, the circle would still include the freed node → dangling pointer and crash.
• Pattern: Every circular LL operation that changes the head requires finding AND updating the last node. This is the operational cost of the circular structure.

Practice Questions — Circular Linked List

4.4 Header Linked Lists

Two Types:

1. Grounded Header List:

• The header node’s next points to the first actual data node
• The last node’s next is NULL (grounded)

Header → [10] → [20] → [30] → NULL
  ↑
(no data, just a sentinel)

2. Circular Header List:

• The header node’s next points to the first actual data node
• The last node’s next points back to the header node (not NULL)

┌─────────────────────────────────┐
│                                 │
Header → [10] → [20] → [30] ───┘

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* header;  // Permanent header node
} HeaderLinkedList;

void init(HeaderLinkedList* list) {
    list->header = (Node*)malloc(sizeof(Node));
    list->header->data = 0;     // Header stores metadata (e.g., count)
    list->header->next = NULL;  // Grounded: NULL, Circular: list->header
}

void insertAfterHeader(HeaderLinkedList* list, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = list->header->next;
    list->header->next = newNode;
    list->header->data++;  // Increment count stored in header
}

void display(HeaderLinkedList* list) {
    Node* temp = list->header->next;  // Skip header
    while (temp != NULL) {  // For circular: while (temp != list->header)
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

🔍 Why Use a Header Node?

• No special cases for empty list — The header always exists, so list->header->next is always valid. Insertion at the beginning doesn’t need to update a head pointer — we just insert after the header.
• Metadata storage — The header’s data field can store useful information like the count of nodes, so we don’t need to traverse to count.
• Uniform operations — Every actual data node has a predecessor (at minimum, the header). This eliminates edge cases in insertion/deletion code.
• Circular header lists simplify traversals that need to “wrap around” — we know we’ve visited all nodes when we return to the header.

5 — Applications of Linked Lists

5.1 Polynomial Representation & Operations

typedef struct PolyNode {
    int coeff;
    int exp;
    struct PolyNode* next;
} PolyNode;

Representation Example

Polynomial: 5x³ + 4x² + 2x + 1

[5,3|•] → [4,2|•] → [2,1|•] → [1,0|•] → NULL
 coeff,exp

Polynomial Addition

Two polynomials: $P1 = 5x^3 + 4x^2 + 2x + 1$ and $P2 = 3x^3 + 2x + 7$

PolyNode* addPolynomials(PolyNode* p1, PolyNode* p2) {
    PolyNode* result = NULL;
    
    while (p1 != NULL && p2 != NULL) {
        if (p1->exp > p2->exp) {
            // Add p1's term to result
            appendTerm(&result, p1->coeff, p1->exp);
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            // Add p2's term to result
            appendTerm(&result, p2->coeff, p2->exp);
            p2 = p2->next;
        } else {
            // Same exponent — add coefficients
            int sumCoeff = p1->coeff + p2->coeff;
            if (sumCoeff != 0)
                appendTerm(&result, sumCoeff, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    // Copy remaining terms
    while (p1 != NULL) {
        appendTerm(&result, p1->coeff, p1->exp);
        p1 = p1->next;
    }
    while (p2 != NULL) {
        appendTerm(&result, p2->coeff, p2->exp);
        p2 = p2->next;
    }
    return result;
}

🔍 Line-by-Line Logic:

• Merge-like pattern — This algorithm is structurally identical to merging two sorted arrays. Both polynomials are sorted by exponent (descending), and we process them together using two pointers.
• p1->exp > p2->exp — If p1’s current term has a higher exponent, it has no match in p2. Copy it directly to the result and advance p1.
• p1->exp < p2->exp — Similarly, p2’s term has no match. Copy it and advance p2.
• p1->exp == p2->exp — Same exponent! Add the coefficients. This is the actual polynomial addition: $ax^n + bx^n = (a+b)x^n$.
• if (sumCoeff != 0) — If coefficients cancel out (e.g., $5x^2 + (-5)x^2 = 0$), we don’t add a zero term. This keeps the result clean.
• Remaining terms — After one polynomial is exhausted, the other’s remaining terms are copied as-is (they have no counterparts to add with).
• Time: $O(m + n)$ where $m$ and $n$ are the number of terms in each polynomial.

5.2 Sparse Matrix Representation

Why Use Sparse Representation?

For a $100 \times 100$ matrix with only 10 non-zero elements:

• Normal representation: $100 \times 100 = 10,000$ elements stored
• Sparse representation: Only 10 elements + their positions stored

Triplet Representation (Array-based)

Store each non-zero element as a triplet: (row, column, value)

typedef struct {
    int row, col, val;
} Element;

typedef struct {
    int rows, cols, numNonZero;
    Element data[MAX];  // Array of triplets
} SparseMatrix;

0  0  3  0
0  4  0  0
5  0  0  0
0  0  0  6

Linked List Representation

Each non-zero element is a node with (row, col, value, next):

typedef struct SparseNode {
    int row, col, val;
    struct SparseNode* next;
} SparseNode;

head → [0,2,3|•] → [1,1,4|•] → [2,0,5|•] → [3,3,6|•] → NULL

5.3 Sparse Matrix Addition

SparseMatrix addSparse(SparseMatrix a, SparseMatrix b) {
    SparseMatrix result;
    result.rows = a.rows;
    result.cols = a.cols;
    result.numNonZero = 0;
    
    int i = 0, j = 0;
    while (i < a.numNonZero && j < b.numNonZero) {
        // Compare positions (row-major order)
        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[result.numNonZero++] = a.data[i++];
        } else if (posA > posB) {
            result.data[result.numNonZero++] = b.data[j++];
        } else {
            // Same position — add values
            int sum = a.data[i].val + b.data[j].val;
            if (sum != 0) {
                result.data[result.numNonZero].row = a.data[i].row;
                result.data[result.numNonZero].col = a.data[i].col;
                result.data[result.numNonZero].val = sum;
                result.numNonZero++;
            }
            i++; j++;
        }
    }
    // Copy remaining
    while (i < a.numNonZero)
        result.data[result.numNonZero++] = a.data[i++];
    while (j < b.numNonZero)
        result.data[result.numNonZero++] = b.data[j++];
    
    return result;
}

🔍 Line-by-Line Logic:

• posA = row * cols + col — Converts 2D position (row, col) into a single linear index. This allows comparing positions of elements from both matrices in one comparison. E.g., position (1,3) in a 5-column matrix = $1 \times 5 + 3 = 8$. This is row-major order — the same way 2D arrays are stored in memory.
• posA < posB — Element from matrix A comes first in row-major order. Copy it to result and advance A’s pointer.
• posA > posB — Element from B comes first. Copy it and advance B.
• posA == posB — Both matrices have a non-zero element at the same position. Add their values. If the sum is zero, don’t include it (it’s no longer “non-zero”).
• Same merge pattern as polynomial addition! Both structures are sorted sequences merged element-by-element.
• Time: $O(a + b)$ where $a$ and $b$ are the number of non-zero elements.

Transpose swaps rows and columns: element at $(i, j)$ moves to $(j, i)$.

Simple Transpose — $O(cols \times numNonZero)$

SparseMatrix transposeSparse(SparseMatrix a) {
    SparseMatrix result;
    result.rows = a.cols;
    result.cols = a.rows;
    result.numNonZero = a.numNonZero;
    
    int k = 0;
    for (int col = 0; col < a.cols; col++) {
        for (int i = 0; i < a.numNonZero; i++) {
            if (a.data[i].col == col) {
                result.data[k].row = a.data[i].col;
                result.data[k].col = a.data[i].row;
                result.data[k].val = a.data[i].val;
                k++;
            }
        }
    }
    return result;
}

🔍 Why This Logic:

• Transpose = swap rows and columns. Element at (row, col) moves to (col, row).
• result.rows = a.cols — The transposed matrix has its dimensions swapped.
• Why the nested loop? — We want the result sorted by row (which is the original column). The outer loop iterates over columns 0, 1, 2, … and for each column, the inner loop finds all elements in that column. This naturally produces results in row-major order.
• Why not just swap row/col directly? — We could, but the result wouldn’t be in sorted row-major order. The nested loop ensures sorted output.
• Time: $O(cols \times numNonZero)$ — For each of the cols columns, we scan all numNonZero elements. This is slow for large matrices. The fast transpose solves this.

Fast Transpose — $O(cols + numNonZero)$

Uses two auxiliary arrays to compute positions directly:

SparseMatrix fastTranspose(SparseMatrix a) {
    SparseMatrix result;
    result.rows = a.cols;
    result.cols = a.rows;
    result.numNonZero = a.numNonZero;
    
    int rowTerms[a.cols];    // Count of elements in each column of a
    int startPos[a.cols];    // Starting position in result for each column
    
    // Initialize
    for (int i = 0; i < a.cols; i++) rowTerms[i] = 0;
    
    // Count non-zero elements in each column
    for (int i = 0; i < a.numNonZero; i++)
        rowTerms[a.data[i].col]++;
    
    // Compute starting positions
    startPos[0] = 0;
    for (int i = 1; i < a.cols; i++)
        startPos[i] = startPos[i-1] + rowTerms[i-1];
    
    // Place elements in correct position
    for (int i = 0; i < a.numNonZero; 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].val = a.data[i].val;
    }
    
    return result;
}

🔍 Line-by-Line Logic:

• Two auxiliary arrays: rowTerms[col] counts how many non-zero elements are in column col of the original matrix. startPos[col] tells us where elements from column col should start in the result.
• Step 1 — Count: for (i) rowTerms[a.data[i].col]++ — Scan all non-zero elements once, counting how many belong to each column.
• Step 2 — Compute positions: startPos[i] = startPos[i-1] + rowTerms[i-1] — Prefix sum! If column 0 has 2 elements and column 1 has 3 elements, column 1’s elements start at index 2, and column 2’s start at index 5. This is exactly how counting sort works.
• Step 3 — Place: j = startPos[col]++ — Get the next available slot for this column and increment. Each element goes directly into its correct final position — no shifting needed.
• Why $O(cols + numNonZero)$? — Step 1: $O(numNonZero)$. Step 2: $O(cols)$. Step 3: $O(numNonZero)$. Total: $O(cols + numNonZero)$ — much faster than the simple transpose’s $O(cols \times numNonZero)$.
• Key insight: This is the counting sort technique applied to matrix transposition. Instead of sorting by value, we’re sorting elements by their column index.

Practice Questions — Applications

0  0  0  5
0  3  0  0
0  0  0  0
2  0  0  0

6 — Comparison of All Linked List Types

6.1 Master Comparison Table

*$O(1)$ if a tail pointer is maintained.

Comprehensive Unit IV Practice Set

insertAtEnd(10), insertAtEnd(20), insertAtBeginning(5),
insertAtPosition(15, 2), deleteAtBeginning(),
deleteAtEnd(), display()

📝 View Complete Solutions for Unit IV →

← Back to DSA Index