1
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ Did you read the accepted answer in the link you gave? $\endgroup$ – Pål GD Mar 23 '13 at 10:14
  • $\begingroup$ 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 ? Ask the lecturer, or choose O(1) and send an email to him after exam. $\endgroup$ – nhahtdh Mar 23 '13 at 10:26
  • $\begingroup$ @Pål GD - Yes, I did. Why ? $\endgroup$ – avi Mar 23 '13 at 10:37
  • 1
    $\begingroup$ Since $O(1) \subseteq O(n)$, just check the largest $O$-class they give. (This ill-posed question illustrates why MCQs are meaningless. Beware if they refer to a particular implementation, though.) $\endgroup$ – Raphael Mar 23 '13 at 15:59
  • 1
    $\begingroup$ @avi: That's a pity. Can you write to them? Mind, though, that you can phrase such a question properly, e.g. "Which is the tightest bound on the runtime of the given algorithm?". $\endgroup$ – Raphael Mar 24 '13 at 15:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.