Past exam question: 2073 Bhadra (Regular), Q4
Open in the Padhaiko appQuestion
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 valInsert 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 headDelete 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 headAnswer:
- Linked Stack:
pushinserts attop(head) andpopremoves fromtopin time. - Doubly Linked List at -th Position:
DLL_INSERT_Kadvances to position and updates 4 links (n->next,n->prev,temp->next->prev,temp->next);DLL_DELETE_Klocates node and bypasses it viatemp->prev->nextandtemp->next->prevbefore freeingtemp.