Past exam question: 2076 Baisakh (Back), Q5
Open in the Padhaiko appQuestion
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:
push(val): AllocatenewNode, setnewNode->data = val,newNode->next = top, updatetop = newNode(ifmallocreturnsNULL, stack overflow).pop(): Iftop == NULL, underflow. Otherwise savetemp = top,val = top->data, advancetop = top->next,free(temp), returnval.peek(): Returntop->dataiftop != NULL.isEmpty(): Returntop == NULL.
Inserting a Node at the -th Position (1-Based) of a Doubly Linked List: Each node has (prev, data, next).
- Allocate
newNodewithnewNode->data = val. - Case (Insert at Head):
newNode->prev = NULL,newNode->next = head.- If
head != NULL, sethead->prev = newNode. - Set
head = newNode.
- Case :
- Traverse pointer
tempfromheadfor steps sotemppoints to node . - If
temp == NULL, is out of bounds. - Link
newNodeaftertemp:newNode->next = temp->nextnewNode->prev = temp- If
temp->next != NULL, settemp->next->prev = newNode temp->next = newNode
- Traverse pointer
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:
- Linked Stack:
push,pop,peek, andisEmptyoperate athead(top) in time. - Doubly Linked List Insert at -th Position: For , prepend before
head; for , advancetempto position and rewire all four links (n->next,n->prev,temp->next->prev,temp->next).