Section 1: Singly Linked List Fundamentals & Traversal (20 PYQs)
1. What is the time complexity to insert an element at the beginning of a singly linked list with
n elements?Explanation:
Inserting at the beginning requires creating a new node, setting its next pointer to the current head, and updating the head pointer. No traversal is required, taking constant time O(1).
2. In a standard singly linked list, which of the following is true?
Explanation:
A singly linked list stores elements dynamically where each node consists of data and a single pointer pointing to the successive node. Contiguous allocation applies to arrays, not linked lists.
3. What does the pointer field of the last node in a standard singly linked list store?
Explanation:
In a standard singly linked list, the final node marks the termination of the list by pointing to NULL (or nullptr).
4. What is the worst-case time complexity to search for an element in a singly linked list of size
N?Explanation:
Because nodes are non-contiguous and accessed sequentially via pointers, linear search is required, leading to a worst-case time of O(N).
5. To delete a node
p when given only a pointer to its preceding node prev, which code snippet is correct?Explanation:
Bypassing node p requires routing prev->next to point directly to p->next, after which node p can be deallocated.
6. Which algorithm technique is most effective for detecting a cycle in a singly linked list with O(1) auxiliary space?
Explanation:
Floyd's Tortoise and Hare algorithm uses two pointers moving at different speeds (1 step and 2 steps) to detect loops in O(N) time and O(1) memory.
7. How many pointer modifications are required to reverse a singly linked list iteratively?
Explanation:
Each node's next pointer must be redirected to its previous node, executing exactly 1 pointer inversion per node for a total of N steps.
8. To find the middle node of a singly linked list in a single traversal, you should:
Explanation:
When the fast pointer (advancing 2 nodes per step) hits the end, the slow pointer (advancing 1 node per step) will be exactly at the middle element.
9. If only a pointer to the head node is maintained, what is the time complexity to insert at the end of a singly linked list?
Explanation:
Without a tail pointer, the list must be traversed from head all the way to the last node (which takes N-1 steps), making it O(N).
10. Which condition indicates that a singly linked list with head pointer
head is empty?Explanation:
An empty linked list contains no nodes, represented by the starting pointer head pointing to NULL.
11. Deletion of the first node in a singly linked list requires:
Explanation:
Deleting the head requires updating head = head->next and freeing the old head, taking constant O(1) time without moving remaining elements.
12. What primary disadvantage does a singly linked list have compared to an array?
Explanation:
Arrays allow O(1) constant-time indexed random access (e.g., A[i]), whereas linked lists require sequential traversal O(i).
13. To insert a new node
new_node after node p in a singly linked list:Explanation:
Assigning new_node->next = p->next first preserves the pointer to the rest of the list before modifying p->next. Reversing these steps causes a dangling pointer and loss of downstream nodes.
14. What is the space complexity overhead per node in a 64-bit architecture for a singly linked list holding 32-bit integers?
Explanation:
In a 64-bit architecture, each memory address pointer occupies 8 bytes (64 bits). Hence, each node requires 8 bytes solely for the pointer link.
15. Which of the following data structures can be implemented efficiently using a singly linked list with push/pop operations at O(1)?
Explanation:
A Stack follows LIFO. Inserting at the head (push) and removing from the head (pop) both execute in O(1) time in a singly linked list.
16. What is the time complexity to concatenate two singly linked lists of sizes
m and n if only head pointers are given?Explanation:
You only need to traverse the first list to locate its final node (taking O(m) steps) and link its next pointer to the head of the second list.
17. In a singly linked list, which operation cannot be performed in O(1) time even if a pointer to the target node is provided?
Explanation:
Without knowing the predecessor node, you cannot adjust its pointer to bypass the target node without copying data from the successor node.
18. To delete the last node of a singly linked list when given the head pointer, the time complexity is:
Explanation:
Even if a tail pointer is kept, you must traverse to the second-to-last node to set its next pointer to NULL, requiring O(N) time.
19. If
head points to a singly linked list, what does the recursive function return?void fun(Node* h) { if(h == NULL) return; fun(h->next); printf("%d ", h->data); }Explanation:
The recursive call occurs before printing. Thus, the call stack unwinds from the base case (last node), printing values backwards.
20. What is a "header linked list"?
Explanation:
A header linked list always maintains an initial dummy/sentinel node at the start, simplifying boundary insertion and deletion operations.
Section 2: Doubly Linked List (DLL) Mechanics & Algorithms (20 PYQs)
21. In a Doubly Linked List, how many pointer fields does each individual node contain?
Explanation:
Each node in a doubly linked list contains two pointers: one pointing forward to the next node and one pointing backward to the previous node.
22. What is the time complexity to delete a node in a Doubly Linked List if a direct pointer to that node is given?
Explanation:
Because each node knows its predecessor (via prev) and successor (via next), deletion can be completed in constant time O(1) without list traversal.
23. In a non-empty Doubly Linked List, the
prev pointer of the first node points to:Explanation:
In a linear doubly linked list, the first node has no predecessor; its prev pointer is set to NULL.
24. To insert a node
temp between p and p->next in a DLL, which statement sequence is correct?Explanation:
All 4 links must be updated: link temp to both neighbors first, then update the backward pointer of the next node and the forward pointer of p.
25. What is the main operational advantage of a Doubly Linked List over a Singly Linked List?
Explanation:
A DLL supports both forward and backward traversal and allows deletion of any node in O(1) time without needing to locate the preceding node.
26. An XOR Linked List is a memory-efficient variant of which data structure?
Explanation:
An XOR Linked List stores the bitwise XOR of the previous and next node addresses in a single pointer field, providing Doubly Linked List functionality using the memory of a Singly Linked List.
27. How many pointer updates are required to reverse a Doubly Linked List of
N nodes?Explanation:
In every node, the next and prev pointers must be swapped. Swapping 2 pointers across N nodes requires 2N pointer modifications.
28. Which of the following conditions checks if a Doubly Linked List has exactly one node?
Explanation:
A single-node list has a valid head where both its backward pointer (prev) and forward pointer (next) are NULL.
29. When implementing an LRU (Least Recently Used) cache, which combination of data structures gives O(1) operations?
Explanation:
The Hash Map provides O(1) key lookup, while the Doubly Linked List allows O(1) removal and re-insertion of accessed nodes at the head.
30. What happens if you execute
node->prev->next = node->next; node->next->prev = node->prev; free(node);?Explanation:
This directly unlinks node by making its preceding and succeeding nodes point to each other, correctly freeing the intermediate node.
31. What is the disadvantage of a Doubly Linked List compared to a Singly Linked List?
Explanation:
Every node requires an extra pointer reference, increasing memory consumption, and modifications demand maintaining twice as many link updates.
32. Deleting the head node of a Doubly Linked List requires which sequence (where
temp = head)?Explanation:
First advance head to the next node, clear the new head's prev pointer to NULL, and release the old head node.
33. To traverse a Doubly Linked List backward, you start from:
Explanation:
Reverse traversal begins at the tail node and iteratively moves through each node's prev pointer until reaching NULL.
34. In a two-way (doubly) linked list, which operation can be performed without checking for NULL predecessor?
Explanation:
When inserting after an existing node, the predecessor is guaranteed to exist, so you only verify that the node itself is non-null.
35. What is the time complexity to reverse a Doubly Linked List of size N?
Explanation:
Every node must be visited once to swap its next and prev pointers, which takes linear time O(N).
36. Which operation is NOT symmetric in a doubly linked list?
Explanation:
Binary search requires direct constant-time access to the middle index, which cannot be done efficiently on a linked list regardless of pointer symmetry.
37. A doubly linked list can be sorted with O(N log N) time and O(1) auxiliary space using:
Explanation:
Merge Sort on linked lists requires no auxiliary array allocations because nodes can be rearranged simply by changing pointers, achieving O(N log N) time.
38. In a DLL node, if
node->next == NULL, it represents:Explanation:
In a standard Doubly Linked List, the last node's next pointer points to NULL, marking the end of forward traversal.
39. What is the minimum number of pointer modifications required to insert a node at the beginning of a non-empty DLL?
Explanation:
Four pointer assignments are made: new_node->next = head, new_node->prev = NULL, head->prev = new_node, and updating head = new_node.
40. In a DLL, navigating to
p->next->prev returns:Explanation:
Following next steps forward one node, and following prev immediately returns back to the original starting node p.
Section 3: Circular Linked List (Singly & Doubly) (20 PYQs)
41. In a circular singly linked list, the pointer of the last node points to:
Explanation:
A circular singly linked list forms a closed loop where the final node's next pointer holds the memory address of the first node (head).
42. What is the termination condition when traversing a circular singly linked list starting from
head?Explanation:
Since circular lists have no NULL pointers, a complete traversal stops when the current node's next pointer cycles back to head.
43. If a circular linked list maintains only a
tail (last node) pointer, what is the complexity of inserting at both head and tail?Explanation:
With a tail pointer, tail->next is the head. Therefore, inserting at the head takes O(1), and inserting at the tail simply takes inserting at the head and moving the tail pointer forward one step (also O(1)).
44. Which real-world OS application most commonly relies on a Circular Linked List?
Explanation:
Round-Robin scheduling allocates fixed time slices to tasks cyclically. A circular linked list allows continuous cycling without resetting pointers.
45. In a Circular Doubly Linked List, what does
head->prev point to?Explanation:
In a Circular Doubly Linked List, both ends loop: tail->next points to head, and head->prev points to tail.
46. What happens if a programmer writes
while(ptr != NULL) ptr = ptr->next; on a circular linked list?Explanation:
Because every node points to a valid successor node and no pointer equals NULL, the loop condition remains indefinitely true.
47. What is the time complexity to insert a node at the front of a circular singly linked list when given ONLY the head pointer?
Explanation:
Without a tail reference, you must traverse all N nodes to reach the last node and update its next pointer to point to the new head.
48. Which classical algorithmic problem is directly modeled using a Circular Linked List?
Explanation:
The Josephus Problem involves people standing in a circle where every $k$-th person is eliminated until one remains, directly matching circular list mechanics.
49. In a Circular Doubly Linked List with only 1 node, what are the values of its
next and prev pointers?Explanation:
To maintain circularity in both directions with a single node, both next and prev must point back to itself.
50. Deleting the only node present in a circular singly linked list requires:
Explanation:
When head->next == head, only 1 node exists. Deallocating it and resetting the head pointer to NULL properly leaves the list empty.
51. Which statement is true regarding null pointers in a Circular Linked List?
Explanation:
Circular lists inherently eliminate NULL pointers because every node's pointer targets another valid node in the loop.
52. How can you split a circular singly linked list into two equal circular halves?
Explanation:
Move slow by 1 and fast by 2 steps. When fast reaches the end, slow is at the middle. Connect slow to head, and fast to slow's next to create two separate circular loops.
53. What is the space complexity of reversing a circular linked list iteratively?
Explanation:
Reversing iteratively only requires auxiliary pointers (prev, curr, next) which consume constant extra memory O(1).
54. In a circular queue implemented using a singly linked list with a single pointer, which pointer should be tracked for O(1) enqueue and dequeue?
Explanation:
Keeping rear gives instant access to both rear and front (via rear->next), allowing both enqueue and dequeue in O(1) time.
55. How do you verify if a given singly linked list is circular?
Explanation:
If traversal reaches NULL, the list is linear; if it hits the head again, the list is circular.
56. Which operation takes O(1) time in a Circular Doubly Linked List with only a head pointer?
Explanation:
Because head->prev provides instant direct access to the tail node, end insertions and deletions complete in O(1).
57. In a circular linked list, what is the effect of changing
head = head->next?Explanation:
Because every node points to its successor in a ring, advancing head simply rotates the logical entry point without altering any node links.
58. What is the time complexity to delete a node given by pointer
del_node in a Circular Doubly Linked List?Explanation:
In a Circular DLL, direct access to both neighboring nodes (del_node->prev and del_node->next) allows unlinking in constant O(1) time.
59. Which loop structure is most natural for traversing every node of a circular linked list exactly once?
Explanation:
A do-while loop ensures the body executes for the head node before evaluating the condition ptr != head.
60. Why is memory deallocation critical when deleting the last node in dynamic linked lists?
Explanation:
Nodes are dynamically allocated on the heap (via malloc/new). Unlinking a node without explicitly calling free() or delete causes unrecoverable memory leaks.
.png)