PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q5

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Linked List

Question

How do you delete a node at the end of the doubly linked list? Explain how the addition of polynomial equations is done using linked list.

Solution

Deleting the Last Node of a Doubly Linked List:

  1. Empty List (head == NULL): Underflow; return NULL.
  2. Single Node (head->next == NULL): free(head), return NULL.
  3. Multiple Nodes: Traverse temp = head until temp->next == NULL (or use tail). Then set temp->prev->next = NULL and free(temp).
DNode *deleteEnd(DNode *head) {
    if (head == NULL) 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;
}

Polynomial Addition Using Linked List: Each non-zero term is stored in a node (coeff, exp, next) sorted in descending order of exp. Using two pointers p1 and p2:

  1. While both p1 and p2 are non-null:
    • If p1->exp > p2->exp: append (p1->coeff, p1->exp) to result, advance p1.
    • Else if p1->exp < p2->exp: append (p2->coeff, p2->exp) to result, advance p2.
    • Else (p1->exp == p2->exp): compute sum = p1->coeff + p2->coeff; if sum != 0, append (sum, p1->exp); advance both p1 and p2.
  2. Append all remaining nodes of whichever list (p1 or p2) is non-empty.

Example: (the and cancel).

Answer:

All past exam questions for Data Structure and Algorithms