The concatenation of two lists is to be performed in O(1) time. Which of the…
201820182023
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of lists could be used?
Answer: C. Circular doubly linked list — In a circular doubly linked list, each node has next and prev pointers, and the tail node's next points back to the head (the list is circular). Concatenation…
- A.
Singly linked list
- B.
Doubly linked list
- C.
Circular doubly linked list
- D.
Array implementation of list
Attempted by 1185 students.
Show answer & explanation
Correct answer: C
In a circular doubly linked list, each node has next and prev pointers, and the tail node's next points back to the head (the list is circular). Concatenation can be done by updating a constant number of pointers. Example pointer-update steps: Let A_head and A_tail be the head and tail of the first circular list, and B_head and B_tail be the head and tail of the second circular list.
Set A_tail.next = B_head
Set B_head.prev = A_tail
Set B_tail.next = A_head
Set A_head.prev = B_tail
These are a fixed number of pointer assignments (independent of the list sizes), so concatenation takes O(1) time. Notes