Complexity of algorithm inserting an element in a circular linked list at the front end

Question

In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here)

But in a book currently, I have, it is mentioned that it is done in O(n) (the usual method). I also saw few lecture ppts, they all mention the usual method of traversing the list & adding an element.

My question is :

1. In practical scenarios which method is used ?

2. I am about to attend an exam, which consists of MCQs, if above question is asked shall I mark O(n), since that is the standard answer ?

Answer 1

The method used in practical scenarios depends on the scenario (and on the programmer). There are several possible issues influencing the choice of implementation:

1. Whether the algorithm is known to the programmer.
2. Ease of coding (it's easiest if it's already implemented in some library you can use).
3. Speed - that depends on how the data structure is used.
4. Space overhead taken by the data structure.

An intelligent programmer should take all of these into account, and try to make themselves more knowledgeable of various algorithms and data structures.