Question

Given a circular doubly linked list whose content are sorted in ascending order, what is the run time complexity for inserting a new element into the list so that it remains correctly sorted? (Including the time required to search for the elements correct position)

• A. O(s)
• B. O(logn)
• C. O(n)
• D. $O\left(n^2\right)$

Answer 1

The correct option is C O(n)

For inserting the element in the sorted circular doubly linked list, we must find the appropriate position for the element. For finding the position of the element we must do the linear search because random access is not possible in the linked list. Binary search does not work well with the linked list. So it will take O(n).