PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q5

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Linked List

Question

Explain operations of stack using linked list. How do you add a node at the position of the doubly linked list?

Solution

Stack Operations Using a Singly Linked List: Maintaining top at the head of a singly linked list gives push and pop:

Inserting a Node at the -th Position (1-Based) of a Doubly Linked List: Each node has (prev, data, next).

  1. Allocate newNode with newNode->data = val.
  2. Case (Insert at Head):
    • newNode->prev = NULL, newNode->next = head.
    • If head != NULL, set head->prev = newNode.
    • Set head = newNode.
  3. Case :
    • Traverse pointer temp from head for steps so temp points to node .
    • If temp == NULL, is out of bounds.
    • Link newNode after temp:
      • newNode->next = temp->next
      • newNode->prev = temp
      • If temp->next != NULL, set temp->next->prev = newNode
      • temp->next = newNode
DNode *insertAtK(DNode *head, int k, int val) {
    if (k < 1) return head;
    DNode *n = malloc(sizeof(DNode));
    n->data = val;
    if (k == 1) {
        n->prev = NULL;
        n->next = head;
        if (head) head->prev = n;
        return n;
    }
    DNode *temp = head;
    for (int i = 1; i < k - 1 && temp; i++) temp = temp->next;
    if (!temp) { free(n); return head; }
    n->next = temp->next;
    n->prev = temp;
    if (temp->next) temp->next->prev = n;
    temp->next = n;
    return head;
}
Answer:

All past exam questions for Data Structure and Algorithms