Multiple choice

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

  1. Singly linked list

  2. Doubly linked list

  3. Circular doubly linked list

  4. Array implementation
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

A circular doubly linked list allows O(1) concatenation because you only need to update a few pointers: connect the tail of the first list to the head of the second, and vice versa. This works in constant time regardless of list size.

Keep practicing — related questions