Linked Lists MCQs for Data Structures at GATE level

Linked Lists MCQs for Data Structures at GATE level

1. Q1. Which of the following is true for a singly linked list?
   A) Random access is O(1)
   B) Insertion at head is O(1)
   C) Deletion of a node given only its pointer is O(1) always
   D) Memory for nodes is contiguous
   Answer: B
   Solution: Insertion at head requires updating head pointer and new node’s next — constant time. Random access is O(n). Deletion given only pointer in singly list requires previous pointer (except trick cases), memory is not contiguous.
2. Q2. For a singly linked list with n nodes, accessing the k-th node (1-based) takes:
   A) O(1)
   B) O(log n)
   C) O(k)
   D) O(n²)
   Answer: C
   Solution: Must traverse from head k−1 steps → O(k) time, worst-case O(n).
3. Q3. To delete a node x in a singly linked list when only x (not head) is given, what must be true to do it in O(1)?
   A) Node x must be last node
   B) Node x must not be last node
   C) Head pointer must be null
   D) List must be circular
   Answer: B
   Solution: Trick: copy next node’s data into x and bypass next — works only if x is not tail.
4. Q4. Which of these data structures can be implemented efficiently using a linked list?
   A) Stack
   B) Queue
   C) Both A and B
   D) Hash table
   Answer: C
   Solution: Both stack (push/pop at head) and queue (enqueue at tail, dequeue at head) are well-suited to linked lists.
5. Q5. Reverse a singly linked list iteratively — time complexity is:
   A) O(1)
   B) O(log n)
   C) O(n)
   D) O(n²)
   Answer: C
   Solution: Each node’s next pointer changed once → linear time O(n).
6. Q6. In a singly linked list, to insert a new node after a given node p, time complexity is:
   A) O(1)
   B) O(n)
   C) O(k) where k = position
   D) O(n log n)
   Answer: A
   Solution: Direct pointer updates: new->next = p->next; p->next = new.
7. Q7. Which of these is a disadvantage of singly linked lists compared to arrays?
   A) Dynamic size
   B) Extra memory for pointers
   C) Fast insertion at head
   D) No shifting elements required
   Answer: B
   Solution: Each node stores a pointer which consumes extra memory.
8. Q8. For a doubly linked list with n nodes, deleting the last node (given tail pointer) takes:
   A) O(1)
   B) O(n)
   C) O(log n)
   D) O(n²)
   Answer: A
   Solution: With tail pointer, set tail = tail->prev and update pointers — constant time.
9. Q9. Detecting a cycle in a singly linked list using Floyd’s algorithm has time complexity:
   A) O(n²)
   B) O(n)
   C) O(1)
   D) O(log n)
   Answer: B
   Solution: Tortoise and hare traverse in O(n) time and O(1) space.
10. Q10. Given two singly linked lists that intersect at node X, finding intersection by length difference technique is:
    A) O(n + m)
    B) O(n * m)
    C) O(n²)
    D) O(1)
    Answer: A
    Solution: Compute lengths, advance longer by diff, then walk both → linear in total nodes.
11. Q11. Which operation is easiest (fastest) in a circular singly linked list with tail pointer?
    A) Insert at head
    B) Insert at tail
    C) Delete last node given only head
    D) Reverse list
    Answer: B
    Solution: With tail pointer, insertion at tail is O(1) since tail->next points to head in circular list.
12. Q12. A linked list node contains an integer and a pointer. If there are 1,000,000 nodes and each pointer is 8 bytes, pointer memory alone is:
    A) ~8 MB
    B) ~80 MB
    C) ~0.8 MB
    D) ~800 MB
    Answer: A
    Solution: 1,000,000 * 8 bytes = 8,000,000 bytes ≈ 8 MB.
13. Q13. Which of the following is true for sentinel/dummy nodes?
    A) They eliminate special-case code for head operations
    B) Increase algorithmic time complexity
    C) Are only used in arrays
    D) Prevent memory leaks automatically
    Answer: A
    Solution: Dummy head simplifies insert/delete at head/tail by avoiding null checks.
14. Q14. To find the middle node of a singly linked list in one pass, one uses:
    A) Two pointers with same speed
    B) Two pointers, one moves twice faster
    C) Stack to store first half
    D) Sorting
    Answer: B
    Solution: Fast pointer moves 2 steps, slow moves 1; when fast hits end, slow at middle.
15. Q15. Inserting at the tail of singly linked list when only head pointer is available takes:
    A) O(1)
    B) O(n)
    C) O(log n)
    D) O(n²)
    Answer: B
    Solution: Must traverse to tail → O(n) unless tail pointer stored.
16. Q16. Merge two sorted singly linked lists into a single sorted list — time complexity:
    A) O(1)
    B) O(n + m)
    C) O(n log m)
    D) O(n*m)
    Answer: B
    Solution: Standard merge (like merge step) linear in sum of lengths.
17. Q17. Which of the following is not true about doubly linked lists?
    A) They allow reverse traversal easily
    B) Each node has two pointers
    C) Deleting a given node requires previous pointer
    D) They use less memory than singly linked lists
    Answer: D
    Solution: Doubly linked lists use more memory per node (two pointers) than singly linked lists.
18. Q18. For memory locality, arrays are better than linked lists because:
    A) Arrays have nodes in heap randomly
    B) Linked lists store elements contiguously
    C) Arrays are contiguous, improving cache performance
    D) Linked lists always improve cache hits
    Answer: C
    Solution: Contiguous allocation in arrays leads to better CPU cache locality.
19. Q19. In a singly linked list, what is the cost to insert before a given node when only that node pointer is provided (no prev pointer)?
    A) O(1) by copying data
    B) O(1) impossible if node is head
    C) O(n) to find previous
    D) Both B and C depending on node position
    Answer: D
    Solution: If not head, need previous pointer — else O(n) to find; cannot insert before in O(1) unless copy workaround (which changes identities) or have prev.
20. Q20. How to free all nodes of a singly linked list safely? Best method:
    A) Free head and stop
    B) Traverse, free each node after saving next pointer
    C) Call free on pointer to head only
    D) Set head = NULL
    Answer: B
    Solution: Must traverse and free nodes one by one after saving next to avoid losing access and memory leaks.
21. Q21. Which linked list variation allows O(1) concatenation of two lists?
    A) Singly linked list with only head
    B) Doubly linked list without tail
    C) Singly circular with tail pointer
    D) Array list
    Answer: C
    Solution: Circular singly with tail: tail->next = head; concatenation by updating tails is O(1).
22. Q22. Given a singly linked list, which operation cannot be done in O(1) worst-case?
    A) Insert at head
    B) Delete head
    C) Access k-th element
    D) Push at head
    Answer: C
    Solution: Access requires traversal → O(k) not constant.
23. Q23. Which is true when you reverse a doubly linked list by swapping next and prev pointers for each node?
    A) Time O(n), Space O(1)
    B) Time O(n²), Space O(n)
    C) Time O(1), Space O(1)
    D) Time O(n), Space O(n)
    Answer: A
    Solution: Single pass swapping pointers yields reversal in linear time and constant extra space.
24. Q24. To detect a cycle and also find its length in a singly linked list, after Floyd finds meeting point, you:
    A) Restart pointers from head only
    B) Move one pointer until it returns to meeting point counting steps
    C) Use hash set to count unique nodes
    D) Cannot find length
    Answer: B
    Solution: From meeting point, advance one pointer until it loops back, counting nodes to get cycle length.
25. Q25. If a linked list is implemented in C and you forget to free nodes after deletion, what’s the effect?
    A) Faster performance
    B) Memory leak
    C) Automatic reclamation by runtime
    D) Undefined behavior only on Linux
    Answer: B
    Solution: Memory allocated but not freed remains allocated → memory leak.
26. Q26. Which structure is ideal for implementing an LRU cache with O(1) operations?
    A) Singly linked list only
    B) Doubly linked list + hash map
    C) Array only
    D) Heap only
    Answer: B
    Solution: Doubly linked list for order + hash map for O(1) lookup gives O(1) LRU operations.
27. Q27. What is the effect of using a sentinel tail node in singly linked list?
    A) Speeds up tail insertions to O(1) without tail pointer
    B) Eliminates need to check for null next during traversal
    C) Always wastes memory and has no benefits
    D) Prevents cyclic lists
    Answer: B
    Solution: Sentinel can simplify edge cases by ensuring next is never null, but tail insert still needs walk unless tail pointer present.
28. Q28. Converting a linked list to array requires:
    A) Extra O(n) memory and O(n) time
    B) No extra memory
    C) O(n²) time
    D) O(1) time
    Answer: A
    Solution: Need array of size n to hold elements and traverse list → O(n) time and space.
29. Q29. Which is required to delete last node of singly linked list in O(1)?
    A) Nothing — O(1) always
    B) Tail pointer and previous pointer available
    C) Doubly linked list or maintain previous pointer
    D) Array implementation
    Answer: C
    Solution: Singly list without previous pointer requires traversal; to do O(1) need doubly linked list or stored prev pointer.
30. Q30. Merging two circular singly linked lists each with their own tail pointers into one circular list takes:
    A) O(1) time
    B) O(n) time
    C) O(log n) time
    D) O(n²) time
    Answer: A
    Solution: Swap tail pointers’ next fields — constant-time concatenation.
31. Q31. How many pointers does a node in XOR linked list store (conceptually)?
    A) One XOR pointer storing XOR(prev, next)
    B) Two separate pointers prev & next
    C) Zero pointers
    D) Three pointers
    Answer: A
    Solution: XOR list stores single word containing XOR of prev and next addresses; traversal needs previous address.
32. Q32. What is a downside of XOR linked lists?
    A) Saves memory and simpler code
    B) Harder to debug and not portable in managed languages
    C) Faster pointer arithmetic always
    D) Uses more memory than doubly list
    Answer: B
    Solution: XOR lists are less readable, error-prone, and incompatible with garbage-collected languages.
33. Q33. If you have a singly linked list with cycle, which operation is guaranteed to terminate?
    A) Simple traversal to end
    B) Detecting cycle via tortoise-hare
    C) Printing all nodes once without extra memory
    D) Finding length by naive traversal
    Answer: B
    Solution: Floyd’s algorithm terminates in O(n), while naive traversal to end never ends.
34. Q34. You need to insert n elements into an initially empty singly linked list at tail while maintaining O(1) per insertion. What do you store?
    A) Only head pointer
    B) Only tail pointer
    C) Both head and tail pointers
    D) Array of nodes
    Answer: C
    Solution: To support O(1) insert-at-tail from empty list, maintain both head and tail pointers.
35. Q35. How to rotate a singly linked list right by k positions (k may be > n) efficiently?
    A) Rebuild list each time O(nk)
    B) Use modulo k = k % n, find new head and tail, rearrange pointers O(n)
    C) Use stack O(n) extra memory each rotation
    D) Impossible
    Answer: B
    Solution: Compute k%n, locate new tail at n-k-1, adjust next pointers in one pass.
36. Q36. Given head pointer only, how to remove duplicates from an unsorted singly linked list in average O(n) time?
    A) Nested loops O(n²)
    B) Use hash set to track seen values → O(n) average time, O(n) extra space
    C) Sorting then remove duplicates
    D) Impossible
    Answer: B
    Solution: Hash set for seen values yields linear average time.
37. Q37. Which of the following uses extra memory but yields linear time for kth-from-end retrieval?
    A) Two-pass traversal O(n) no extra memory
    B) Using array to copy nodes → O(n) time and space
    C) Using recursion → O(n) call stack
    D) Both B and C
    Answer: D
    Solution: Copying to array or recursion uses O(n) extra memory/stack but allows direct access from end.
38. Q38. Which approach finds kth-from-end in one pass and O(1) extra space?
    A) Two-pointer (lead k steps ahead) method
    B) Hash map
    C) Stack of size k
    D) Sorting
    Answer: A
    Solution: Advance lead pointer by k then move both until lead hits end; trailing pointer at kth-from-end.
39. Q39. Which algorithm splits a linked list into two halves for merge sort?
    A) Use array index split
    B) Slow-fast pointer technique to find middle in O(n)
    C) Random selection
    D) Repeated deletion
    Answer: B
    Solution: Use slow/fast pointers to find middle and split for merge sort.
40. Q40. Merging k sorted linked lists of total N nodes using min-heap yields time complexity:
    A) O(N log k)
    B) O(N k)
    C) O(N log N)
    D) O(k log N)
    Answer: A
    Solution: Each of N nodes extracted/pushed in heap of size k → O(N log k).
41. Q41. Which structure is best to represent adjacency lists of sparse graphs?
    A) 2D array
    B) Linked lists per vertex
    C) Single vector of fixed size
    D) Balanced BST per vertex
    Answer: B
    Solution: Linked lists per vertex provide dynamic adjacency with O(1) insertion.
42. Q42. Problem: Given head of singly linked list, determine if palindrome in O(n) time and O(1) space. Best strategy:
    A) Copy to array and check → O(n) space
    B) Use stack of n/2 elements → O(n) space
    C) Reverse second half in-place, compare, then restore → O(1) extra space
    D) Use hashing only
    Answer: C
    Solution: Reverse second half, compare nodes, then restore list — linear time, constant extra space.
43. Q43. Which node pointer change sequence reverses singly linked list iteratively?
    A) prev = current; current = next; next = current->next
    B) next = current->next; current->next = prev; prev = current; current = next
    C) current->next = head; head = current
    D) None of the above
    Answer: B
    Solution: Standard iterative reversal uses those pointer assignments per node.
44. Q44. Which is true for tail pointer maintenance in singly linked list?
    A) tail->next always NULL (non-circular)
    B) tail helps O(1) append
    C) tail not enough to delete last in O(1)
    D) All of the above
    Answer: D
    Solution: All statements hold: tail->next = NULL in singly list; tail allows O(1) append; deleting last still needs previous pointer.
45. Q45. Inserting into sorted singly linked list to maintain order has worst-case time:
    A) O(1)
    B) O(log n)
    C) O(n)
    D) O(n²)
    Answer: C
    Solution: Need to find insertion point by traversal → linear time.
46. Q46. Which of these operations is simplest on a circular doubly linked list with given pointer to node?
    A) Insert after node
    B) Delete node
    C) Both A and B in O(1)
    D) Reverse entire list in O(1)
    Answer: C
    Solution: With prev & next available, insert/delete at node are O(1).
47. Q47. In a linked list with nodes allocated via malloc, calling free(node) without fixing neighbors leads to:
    A) Safe deletion always
    B) Dangling pointers from neighbors still pointing to freed memory
    C) Automatic neighbor update
    D) None
    Answer: B
    Solution: Neighbors still have pointers to freed address → dangling pointers and potential use-after-free.
48. Q48. Which is a common use of linked lists in OS kernels?
    A) Page tables stored as linked lists always
    B) Scheduling queues and free lists are often linked lists
    C) Linked lists are never used in kernels
    D) Linked lists replaced by arrays for speed always
    Answer: B
    Solution: OS uses linked lists for free lists, process queues, etc., due to dynamic insert/delete.
49. Q49. Which method can detect and remove a cycle in a linked list?
    A) Mark visited nodes by modifying node (if allowed)
    B) Use Floyd’s detection and then find start and break cycle
    C) Hash set of visited nodes
    D) Any of the above depending on constraints
    Answer: D
    Solution: All are valid: marking nodes (if data can be modified), Floyd’s algorithm then break, or using hash set with extra memory.
50. Q50. For a list of size 10, splitting into two lists of size 5 each preserving original order can be done in:
    A) O(1)
    B) O(5) = O(n) time
    C) O(n²)
    D) Impossible
    Answer: B
    Solution: Traverse to 5th node and split by setting next pointers appropriately — linear in split index.
51. Q51. Which statement about linked lists is false?
    A) Inserting in middle is O(1) if previous node is known
    B) Reverse traversal is easy in singly linked lists
    C) Doubly linked lists occupy more memory
    D) Circular lists are useful for round-robin scheduling
    Answer: B
    Solution: Reverse traversal not straightforward in singly linked lists without extra memory.
52. Q52. Combining two sorted singly linked lists by rearranging pointers (no new nodes) requires how much extra memory?
    A) O(1)
    B) O(n)
    C) O(log n)
    D) O(n²)
    Answer: A
    Solution: Merge by pointer re-linking uses constant extra space.
53. Q53. To remove all nodes with value x from singly linked list, recommended approach:
    A) Use a dummy head and iterate, removing matches by relinking
    B) Use recursion only
    C) Convert to array and filter
    D) None of above
    Answer: A
    Solution: Dummy head simplifies handling removals at head and general cases in one pass O(n).
54. Q54. Which linked list operation may cause segmentation fault if head becomes NULL and you attempt head->next?
    A) Accessing head without checking for null
    B) Deleting tail properly
    C) Inserting at head
    D) None
    Answer: A
    Solution: Dereferencing NULL causes segmentation fault.
55. Q55. Which of these is a stable method to copy a linked list with random pointers (each node has random pointer to arbitrary node) in O(n) time and O(1) extra space?
    A) Use hash map mapping old->new (O(n) space)
    B) Interleave copied nodes between originals, assign randoms, then separate lists
    C) Deep recursion
    D) Impossible in O(1) space
    Answer: B
    Solution: Interleaving trick creates new nodes adjacent to originals, set randoms, then unweave — linear time constant extra space.
56. Q56. What is the time complexity to find the length of a linked list?
    A) O(1)
    B) O(n)
    C) O(log n)
    D) O(n log n)
    Answer: B
    Solution: Must traverse and count nodes → O(n).
57. Q57. Which method is preferred to implement adjacency list for graphs when deletions are frequent?
    A) Vector of vectors
    B) Linked lists per vertex
    C) Adjacency matrix
    D) None
    Answer: B
    Solution: Linked lists allow O(1) delete if pointer to node is known; vectors cost shifting.
58. Q58. A tail pointer in singly linked list gives O(1) append. What about O(1) prepend?
    A) Also O(1), since head updated
    B) O(n) always
    C) Only if circular
    D) Depends on size
    Answer: A
    Solution: Prepending requires updating head pointer only — O(1).
59. Q59. Which of these makes linked list iteration order stable while merging?
    A) Removing nodes at random
    B) Always reusing existing pointers to maintain order
    C) Sorting first
    D) None
    Answer: B
    Solution: Pointer-based merge preserves relative order of equal elements if implemented stably.
60. Q60. For implementing undo feature storing operations, which list variant is convenient?
    A) Singly linked list only
    B) Doubly linked list to move back and forth
    C) Circular list always
    D) Array only
    Answer: B
    Solution: Doubly linked list allows moving backward (undo) and forward (redo) easily.
61. Q61. Which of the following is best when frequent searches by index are required?
    A) Linked list
    B) Array (dynamic)
    C) XOR list
    D) None
    Answer: B
    Solution: Arrays provide O(1) random access; linked lists are O(n).
62. Q62. Inserting into middle of doubly linked list with pointer to node is:
    A) O(1)
    B) O(n)
    C) O(log n)
    D) O(n log n)
    Answer: A
    Solution: Given position node, manipulate prev/next pointers in constant time.
63. Q63. Which of below is true about memory allocation for linked lists?
    A) All nodes must be contiguous
    B) Nodes can be allocated anywhere on heap
    C) Must be in stack memory
    D) Compiler arranges contiguous blocks for each list
    Answer: B
    Solution: Each node allocated via malloc/new can reside anywhere in heap.
64. Q64. Which scenario benefits most from linked lists over arrays?
    A) Frequent random access
    B) Frequent insertions/deletions in middle when position known
    C) Small fixed-size data where memory contiguous desirable
    D) CPU cache optimizations
    Answer: B
    Solution: Linked lists excel at frequent insert/delete where pointer/reference to node known.
65. Q65. What is the standard way to represent polynomial as linked list coefficients for sparse polynomials?
    A) Array indexed by degree
    B) Linked list of (coeff, degree) sorted by degree
    C) Hash table only
    D) Matrix
    Answer: B
    Solution: Sparse polynomial rows use linked lists of terms to save space and allow insertion/deletion.
66. Q66. Which approach to free memory of large linked list better prevents stack overflow?
    A) Recursion free(node->next) then free node
    B) Iterative loop freeing nodes one by one
    C) Using longjmp
    D) Not freeing at all
    Answer: B
    Solution: Iterative free uses O(1) stack; recursive free will use O(n) stack frames and can overflow.
67. Q67. In a concurrent setting, which linked list variant is easiest to make lock-free?
    A) Doubly linked list
    B) Singly linked list with atomic compare-and-swap on head/tail
    C) XOR list
    D) None
    Answer: B
    Solution: Singly linked lists are simpler to implement lock-free structures using CAS on head/tail.
68. Q68. Which is best to implement a queue that needs O(1) enqueue and dequeue?
    A) Singly linked list with head & tail pointers
    B) Singly linked list with only head
    C) Doubly linked list with only head
    D) Array without circular handling
    Answer: A
    Solution: Maintain head for dequeue and tail for enqueue; both O(1).
69. Q69. If you need reverse-iterable container with efficient insert/delete anywhere, which to choose?
    A) Singly linked list
    B) Doubly linked list
    C) Array list
    D) Heap
    Answer: B
    Solution: Doubly linked lists allow reverse iteration and O(1) insert/delete at known node.
70. Q70. To remove every second node (i.e., nodes at even positions) from a singly linked list, complexity is:
    A) O(n) time, O(1) space
    B) O(n²) time
    C) O(1) time
    D) O(n) time, O(n) space
    Answer: A
    Solution: Single traversal with pointer skipping next nodes and freeing them — linear time constant space.
71. Q71. A linked list stored as nodes in memory, how to check memory corruption causing cycle inadvertently?
    A) Use Floyd’s algorithm to detect cycle
    B) Print addresses and analyze manually
    C) Assume no corruption
    D) Use bubble sort
    Answer: A
    Solution: Floyd’s cycle detection will catch cycles even due to corruption.
72. Q72. What happens if you accidentally set head = head->next in code but forget to free old head?
    A) Memory leak for old head if no other pointer refers
    B) Safe — old head recovered automatically
    C) Program crashes immediately
    D) Garbage collector frees it always in C
    Answer: A
    Solution: Old node becomes unreachable — memory leak unless freed.
73. Q73. Which of the following makes copy operation O(1) time?
    A) Shallow copy by copying head pointer only (both lists share nodes)
    B) Deep copy always
    C) Interleaving nodes
    D) None
    Answer: A
    Solution: Shallow copy copies pointer, constant time, but both lists share nodes (aliasing).
74. Q74. Which of the following is the primary reason linked lists are preferred for insertion-heavy workloads?
    A) Better cache locality
    B) O(1) insertion when position known
    C) Lower memory overhead always
    D) Easier random access
    Answer: B
    Solution: Insertion at known position requires only pointer updates.
75. Q75. If you need to maintain sorted numbers and frequently find median, which is better than plain linked lists?
    A) Balanced BST or heaps (two heaps technique)
    B) Singly linked list
    C) XOR list
    D) None
    Answer: A
    Solution: Two-heaps or balanced BST provide efficient median updates; linked lists are O(n).
76. Q76. Linked list vs vector: which consumes more memory per element typically?
    A) Vector (array) because contiguous
    B) Linked list because pointer per node overhead
    C) Same always
    D) Depends only on compiler
    Answer: B
    Solution: Linked list has pointer(s) per node increasing per-element overhead.
77. Q77. What’s the simplest way to insert at index 0 in singly linked list?
    A) Create new node; new->next = head; head = new
    B) Shift all nodes by one
    C) Use recursion
    D) Swap data only
    Answer: A
    Solution: Standard head insertion constant-time.
78. Q78. For adding a node B after node A in doubly linked list, which pointers to update?
    A) A->next, B->prev, B->next, (original next)->prev
    B) Only A->next and B->next
    C) Only B->prev
    D) None
    Answer: A
    Solution: Must correctly patch all neighboring pointers to maintain list integrity.
79. Q79. Which of the following improves locality for linked nodes while keeping linked behavior?
    A) Use array of nodes and store indices as next (index-based linked list)
    B) Use pointers only
    C) Use random heap allocations
    D) Use XOR list always
    Answer: A
    Solution: Pool/array allocation gives contiguous storage improving cache while keeping linked semantics.
80. Q80. Which technique prevents frequent small allocations for linked list nodes?
    A) Memory pool / free list / allocator slab
    B) malloc for each node always
    C) Use recursion
    D) Use stack memory for nodes permanently
    Answer: A
    Solution: Memory pooling reduces overhead and fragmentation.
81. Q81. What is an advantage of using sentinel/dummy tail node?
    A) Simplify tail deletion logic similarly to head sentinel
    B) Remove need for tail pointer always
    C) Saves memory
    D) None
    Answer: A
    Solution: Tail sentinel can simplify boundary cases but tail pointer may still be needed.
82. Q82. Which of the following is true for a circular doubly linked list?
    A) head->prev points to tail
    B) tail->next points to head
    C) Both A and B
    D) Neither
    Answer: C
    Solution: Circular doubly links wrap both directions.
83. Q83. Which method of creating nodes avoids fragmentation and improves speed?
    A) Using custom allocator that preallocates blocks of nodes
    B) Using standard malloc for each node always
    C) Using new operator in high-level language each time
    D) Using stack allocation per node permanently
    Answer: A
    Solution: Custom allocators reduce fragmentation and speed up allocations.
84. Q84. Which of these helps prevent ABA problem when performing lock-free updates on linked lists?
    A) Use double-word CAS with version/tag counters (tagged pointers)
    B) Do nothing — ABA is harmless
    C) Use XOR linked list
    D) Use recursion
    Answer: A
    Solution: Tagged pointers/counters detect ABA occurrences in CAS loops.
85. Q85. To rotate a singly linked list left by 1 (move head to tail), required operations:
    A) head = head->next; tail->next = oldHead; oldHead->next = NULL; tail = oldHead
    B) Swap data only
    C) Use array operations
    D) Impossible
    Answer: A
    Solution: Re-link head to tail and update pointers in O(1) with tail pointer.
86. Q86. Which approach yields stable sorting of linked list with O(n log n) time and O(1) extra space?
    A) Merge sort specialized for linked lists (O(1) extra if using pointers)
    B) Quick sort in place (unstable)
    C) Heap sort (needs random access)
    D) Bubble sort O(n²)
    Answer: A
    Solution: Merge sort works well on linked lists, stable and can be done with pointer manipulations.
87. Q87. For implementing a sparse matrix with efficient row traversal and insertion, best structure:
    A) 2D array
    B) Linked lists per row of (col, value) pairs
    C) Single linked list of all elements unordered
    D) Hash table only
    Answer: B
    Solution: Per-row linked lists allow easy row-wise traversal and insertion.
88. Q88. Which linked list operation is tricky in multithreaded context requiring locks or lock-free primitives?
    A) Single node read-only traversal
    B) Insert at head with atomic CAS on head pointer
    C) Deleting arbitrary node while others iterate concurrently
    D) All reads are safe always
    Answer: C
    Solution: Deleting nodes while others traverse requires careful synchronization to avoid use-after-free.
89. Q89. Which method enumerates all nodes in ring buffer implemented as linked list?
    A) Start at head and stop when node==head again (handle empty specially)
    B) Iterate indefinitely
    C) Use recursion only
    D) None
    Answer: A
    Solution: Circular lists require stop condition when wrapping to starting node.
90. Q90. If you want to implement undo/redo with infinite history but bounded memory, which technique using linked lists is appropriate?
    A) Use doubly linked list + cap length and drop oldest nodes when exceeding cap
    B) Use singly list without cap
    C) Use recursion
    D) Use XOR lists only
    Answer: A
    Solution: Keep doubly linked list with head as oldest, tail as newest; drop from head as needed.
91. Q91. Which is the fastest way to append multiple nodes at tail given tail pointer?
    A) Append one-by-one with O(1) each → total O(m) for m nodes
    B) Rebuild list from scratch
    C) Prepend then reverse
    D) None
    Answer: A
    Solution: Each append O(1) yields total linear in number appended.
92. Q92. In languages with garbage collection (e.g., Java), what must you do to help GC reclaim a removed linked list node?
    A) Nullify references to it (prev/next and any external refs) so GC can collect
    B) Call free manually
    C) Use unsafe memory free
    D) Nothing — GC will reclaim even if references exist
    Answer: A
    Solution: Remove references so object becomes unreachable; GC will collect.
93. Q93. Which pattern helps implement adjacency list while preserving insertion order of neighbors?
    A) Use singly linked list per adjacency vector and append at tail
    B) Use hash set only
    C) Use stack per vertex
    D) Use unordered map
    Answer: A
    Solution: Appending at tail preserves neighbor insertion order.
94. Q94. To split linked list into odd and even positioned nodes (preserving order), you should:
    A) Maintain two tails and append each node alternately, then combine
    B) Reverse and select
    C) Sort by value
    D) Use recursion only
    Answer: A
    Solution: Build two lists (odd and even) then concatenate; single pass O(n).
95. Q95. When copying a linked list, deep copy vs shallow copy difference:
    A) Deep copy duplicates nodes; shallow copies pointer to same nodes
    B) Shallow copy is O(n) always; deep copy O(1)
    C) They are identical
    D) None
    Answer: A
    Solution: Deep creates new nodes; shallow copies pointers causing aliasing.
96. Q96. Which traversal is impossible on singly linked list without extra memory or modification?
    A) Forward traversal from head
    B) Reverse traversal from tail without tail/prev pointers
    C) Visiting nodes sequentially
    D) Counting nodes
    Answer: B
    Solution: Reverse traversal requires prev pointers or extra memory/modify list.
97. Q97. To delete a node with value v in singly linked list where multiple nodes may contain v, and you want to delete all occurrences, recommended approach:
    A) Use dummy head and scan, unlink matched nodes and free them
    B) Recursively delete nodes only
    C) Convert to array and filter
    D) Reassign head pointer only
    Answer: A
    Solution: Dummy head simplifies deletion at head and in middle; single pass O(n).
98. Q98. Which technique converts recursion-based list algorithms to iterative ones to avoid deep recursion?
    A) Use explicit stack data structure to store state
    B) Do nothing
    C) Use recursion more
    D) Use bubble sort
    Answer: A
    Solution: Simulate recursion with explicit stack to avoid call-stack depth.
99. Q99. Which data structure is preferable when you need persistable snapshots (immutable versions) cheaply?
    A) Immutable/persistent singly linked lists (structural sharing)
    B) Mutable arrays only
    C) XOR lists
    D) Doubly lists only
    Answer: A
    Solution: Persistent linked lists share structure and allow cheap snapshots (functional programming).
100. Q100. For a huge linked list you want to quickly jump to approximate middle for balancing workload; what cheap approach helps?
     A) Keep additional index pointers every √n nodes (skip list-like)
     B) Always traverse from head
     C) Use recursion
     D) Convert to binary tree
     Answer: A
     Solution: Maintain skip pointers (square-root decomposition) to speed up near O(√n) jumps; skip lists are similar idea.

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts