PPractick

The problem

When the browser's history grows too long, it drops the oldest entry at the head. In a doubly linked list, deleting the head means moving head to the second node and clearing that node's prev, which still points at the node being freed. Leaving it would make any backward traversal read freed memory. The same care applies to deleting any node: both neighbours' pointers must be updated, which the prev pointer makes possible in O(1).

Example: 1 <-> 2 <-> 3, delete the head → 2 <-> 3.

Function signature

DNode* deleteHead(DNode* head);                    // returns the new head
DNode* deleteAtPosition(DNode* head, int pos);     // 1-indexed, valid position

Test cases

Input	Forward result	Explanation
deleteHead(1 <-> 2 <-> 3)	2 <-> 3	The new head's prev is nullptr
deleteHead(5)	(empty)
deleteHead(empty)	(empty)
deleteAtPosition(1 <-> 2 <-> 3 <-> 4, 3)	1 <-> 2 <-> 4	Both neighbours re-linked
deleteAtPosition(1 <-> 2, 1)	2	Position 1 is the head
deleteAtPosition(1 <-> 2 <-> 3, 3)	1 <-> 2	The tail

(Confirm: after every deletion, the backward traversal must be the exact reverse of the forward one; deleted nodes are freed.)

How interviewers phrase it

• "Delete the head node of a doubly linked list" (GeeksforGeeks).
• "Delete the node at position x" or "delete a given node in O(1)."
• Central to the LRU cache: evicting the least recently used node and moving a node to the front.

Clarifying questions to ask

1. Empty list: return nullptr?
2. 0- or 1-indexed positions?
3. Am I given the position or a pointer to the node?

Follow-ups to expect

1. "What's the easy-to-forget step?"
2. "How do you delete a node given only a pointer to it?"
3. "How would sentinel (dummy) head and tail nodes help?"
4. "Complexity?"

Related questions

• Introduction to Doubly LL Easy
• Insert node before head in Doubly Linked List Easy
• Reverse a Doubly Linked List Medium
• Delete all occurrences of a key in DLL Hard
• Find Pairs with Given Sum in Doubly Linked List Medium
• Remove duplicates from sorted DLL Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in