Essential Linked Lists Concepts Quiz

Explore the fundamentals of linked lists, analyzing common operations, patterns, and underlying data structures crucial for programming and interviews.

1. Time Complexity to Find Middle

   What is the time complexity to find the middle element of a singly linked list with n nodes?

   1. O(n^2)
   2. O(log n)
   3. O(n)
   4. O(1)

   Explanation: Finding the middle element in a singly linked list usually requires traversing half the list, which is O(n) time. O(1) is incorrect because random access is not possible. O(log n) and O(n^2) do not apply to this basic linear traversal.

2. Detecting Loops Algorithm

   Which algorithm is commonly used to detect a cycle in a linked list?

   1. Dijkstra's Algorithm
   2. Floyd's Cycle Detection (Tortoise & Hare)
   3. Bellman-Ford Algorithm
   4. Breadth-First Search

   Explanation: Floyd's Cycle Detection, also known as the Tortoise & Hare algorithm, detects cycles efficiently by using two pointers. Dijkstra's and Bellman-Ford are shortest path algorithms, while BFS is used for traversing graphs, not specifically for cycle detection in a linked list.

3. Iterative Reversal of Linked List

   How is a singly linked list typically reversed iteratively?

   1. Swapping node values
   2. Recursively calling reverse on sublists
   3. Using a stack to store nodes
   4. By changing next pointers using 3 variables: prev, curr, next

   Explanation: Reversing a singly linked list iteratively requires prev, curr, and next variables to change pointers. Swapping values does not reverse links. Recursion and stacks are alternative methods but are not iterative by nature.

4. Insertion at the Head

   If you insert 4 at the head of a linked list: Head → 1 → 2 → 3 → null, what is the new sequence?

   1. 4 → 1 → 2 → 3 → null
   2. 4 → 2 → 3 → null
   3. 1 → 4 → 2 → 3 → null
   4. 1 → 2 → 3 → 4 → null

   Explanation: Inserting at the head means the new element points to the old head, resulting in 4 → 1 → 2 → 3 → null. The other options either incorrectly place 4, omit nodes, or misorder the sequence.

5. Deleting Node by Reference

   How can you delete a node from a singly linked list, given only that node (not the head)?

   1. Drop node reference only
   2. Copy data from next node and bypass it
   3. Update head pointer
   4. Traverse from head and remove node

   Explanation: Without access to the head, you must copy the next node's data into the current node and bypass the next node. Updating the head pointer or traversing from head isn't possible since the head isn't accessible. Simply dropping the reference doesn't delete the node.

6. Pointers in Doubly Linked List

   How many pointers does a typical node in a doubly linked list contain?

   1. 2
   2. 0
   3. 3
   4. 1

   Explanation: A doubly linked list node contains two pointers: one to the previous node and one to the next. One pointer is for singly linked lists, while three or zero are incorrect for standard doubly linked lists.

7. Circular Linked List Characteristic

   Which of the following is true about circular linked lists?

   1. All nodes have two pointers
   2. Last node points to head
   3. Last node points to null
   4. First node points to last node

   Explanation: In a circular linked list, the last node's next pointer circles back to the head. The first node does not point to the last. Null is used in linear lists, and two pointers per node applies to doubly linked lists, not circularity.

8. Merging Two Sorted Lists

   Which technique is typically used to merge two sorted linked lists efficiently?

   1. Stack-based merging
   2. Sorting after concatenation
   3. Hash map lookup
   4. Two-pointer technique

   Explanation: The two-pointer technique traverses both lists and merges them by comparing elements. Stack-based or hash-map methods are not standard for this problem. Sorting after concatenation is less efficient than merging sorted lists.

9. Recursive Reversal Space Complexity

   What is the space complexity of reversing a linked list recursively?

   1. O(log n)
   2. O(1)
   3. O(n^2)
   4. O(n)

   Explanation: Recursive reversal adds a stack frame for each node, so the space is O(n). O(1) is only for the iterative method. O(log n) and O(n^2) do not reflect the true recursive call stack usage.

10. LRU Cache Underlying Structure

    Which data structure underlies an efficient LRU cache implementation?

    1. Queue only
    2. Doubly Linked List + HashMap
    3. Single array
    4. Binary Search Tree

    Explanation: Efficient LRU caches combine a doubly linked list for order and a hash map for quick access. A queue alone doesn't allow O(1) removals. Arrays and BSTs are not optimal for achieving both O(1) operations.