Data Structures Linked Lists 1 — Questions and Answers
Question 1: What is the time complexity of inserting a node at the beginning of a singly linked list?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n²)
Correct answer: O(1)
Inserting at the head only requires updating the new node's next pointer and the head reference, both constant-time operations.
Question 2: Which algorithm detects a cycle in a linked list using O(1) extra space?
- DFS traversal
- Hash set tracking
- Floyd's cycle detection (slow/fast pointers) (Correct answer)
- Reverse and compare
Correct answer: Floyd's cycle detection (slow/fast pointers)
Floyd's cycle detection uses a slow pointer moving one step and a fast pointer moving two steps; if they meet, a cycle exists.
Question 3: What is the main disadvantage of singly linked lists compared to arrays?
- Higher insertion cost at head
- No random access by index (Correct answer)
- Requires more CPU operations for sorting
- Cannot store duplicate values
Correct answer: No random access by index
Singly linked lists require O(n) traversal to access any element by position since there is no direct index-based access.
Question 4: How do you find the middle node of a linked list in one pass?
- Count nodes then traverse to n/2
- Use two pointers where fast moves twice as fast as slow (Correct answer)
- Store all nodes in an array
- Traverse from both ends simultaneously
Correct answer: Use two pointers where fast moves twice as fast as slow
The slow/fast pointer technique reaches the middle when the fast pointer reaches the end, accomplishing the task in a single O(n) pass.
Question 5: What is the time complexity of deleting a node from a singly linked list given only a pointer to that node (not the previous)?
- O(1) by copying successor data (Correct answer)
- O(n) to find the predecessor
- O(log n)
- Impossible without the previous node
Correct answer: O(1) by copying successor data
You can delete a node in O(1) by copying the successor's data into the current node and deleting the successor node instead.
Question 6: Which linked list variant allows traversal in both forward and backward directions?
- Circular linked list
- Doubly linked list (Correct answer)
- Skip list
- XOR linked list
Correct answer: Doubly linked list
A doubly linked list stores both next and prev pointers in each node, enabling O(1) traversal in either direction.
Data Structures Linked Lists 1
What is the time complexity of inserting a node at the beginning of a singly linked list?