The concatenation of two lists is to be performed in O(1) time. Which of the…
2018
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of lists could be used?
- A.
Singly linked list
- B.
Doubly linked list
- C.
Circular doubly linked list
- D.
Array implementation of list
Attempted by 796 students.
Show answer & explanation
Correct answer: C
In O(1) time concatenation is possible when we can directly connect the last node of the first list to the first node of the second list without traversal . In a circular doubly linked list , we maintain direct access to both head and tail, and links can be adjusted in constant time. Other list types require traversal to reach the end, which takes O(n) time.