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 ?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Did you read the accepted answer in the link you gave? $\endgroup$
    – Pål GD
    Mar 23, 2013 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, 2013 at 10:26
  • $\begingroup$ @Pål GD - Yes, I did. Why ? $\endgroup$
    – avi
    Mar 23, 2013 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, 2013 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, 2013 at 15:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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