PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q4

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Linked List

Question

How do you perform a push and pop operation in stack as a linked list? How do you insert and delete a node at the position of the doubly linked list?

Solution

Push and Pop in a Linked-List Stack (top at Head):

Algorithm PUSH(top, val):
1. Allocate newNode; if NULL -> Overflow
2. newNode->data = val; newNode->next = top
3. top = newNode; Return top

Algorithm POP(top):
1. If top == NULL -> Underflow
2. temp = top; val = temp->data
3. top = top->next; Free(temp)
4. Return val

Insert at -th Position (1-Based) of Doubly Linked List:

Algorithm DLL_INSERT_K(head, k, val):
1. Allocate n; n->data = val
2. If k == 1:
       n->prev = NULL; n->next = head
       If head != NULL: head->prev = n
       Return n
3. temp = head; advance temp (k - 2) times
4. If temp == NULL: Return head  (out of range)
5. n->next = temp->next; n->prev = temp
6. If temp->next != NULL: temp->next->prev = n
7. temp->next = n; Return head

Delete at -th Position (1-Based) of Doubly Linked List:

Algorithm DLL_DELETE_K(head, k):
1. If head == NULL or k < 1: Return head
2. temp = head; advance temp (k - 1) times
3. If temp == NULL: Return head  (out of range)
4. If temp == head:
       head = temp->next
       If head != NULL: head->prev = NULL
   Else:
       temp->prev->next = temp->next
       If temp->next != NULL: temp->next->prev = temp->prev
5. Free(temp); Return head
Answer:

All past exam questions for Data Structure and Algorithms