Question

Data Structures - Finding complexity of pop() operation in a circular LinkedList

9. Using a circular LinkedList, how might the pop() operation work, and what would be its complexity? How does it compare to pop() on a normal LinkedList? Justify your answer.

Answer 1

In circular linked list, we usually maintain two variables, called head and tail, which respectively point to the start and end of the list, respectively. Hence, in case of pop() operation, we always remove the element from the end of the list, i.e., from the tail of the list. This means that we have to update the tail of the list. This operation can be done in O(1). [Note that in case of circular list, the tail index can come before the head index].

However, in case of linked list, we just maintain a pointer to the head of the list. In case of pop(), we iterate to the last element in the list and remove it. This operation takes O(n) time.