StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>As far as I understand this method has an O(k2) behavior where k denotes the position of element K. First indexOf() runs through the list until it finds K and afterwards add has to do the same work again until it reaches position k + 1. </p> </blockquote> <p>Actually, the cost of <code>list.add(list.indexOf(K) + 1, E)</code> is <code>O(k)</code> if <code>list</code> is a <code>LinkedList</code>.</p> <ul> <li><p>The <code>list.indexOf(K)</code> call involves <code>k</code> link traversals and <code>k</code> comparisons.</p></li> <li><p>The <code>list.add(k + 1, E)</code> call involves <code>k + 1</code> link traversals.</p></li> </ul> <p>Add them up - <code>3 k + 1</code> operations; i.e. <code>O(k)</code>.</p> <hr> <p>However, you are right. It would be possible to create an alternative version of <code>LinkedList</code> with an <code>addAfter</code> or <code>addBefore</code> method. These methods would also be <code>O(k)</code> but they should be faster. Unfortunately, <code>LinkedList</code> is not implemented in a way that would allow you to simply add these methods (and implement them optimally). The internals of <code>LinkedList</code> are declared as private, so you would need to start over.</p> <hr> <p>And incidentally <code>list.add(list.indexOf(K) + 1, E)</code> on an <code>ArrayList</code> will be <code>O(N)</code> where <code>N</code> is the list length. The <code>indexOf</code> step takes <code>k</code> comparisons, and the <code>add</code> step involves moving <code>N - k</code> elements. Ergo <code>N</code> operations and <code>O(N)</code></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload