title: Single linked lists & time complexity
body: <p>I'm trying to write my own (as close to standard as possible) single linked list implementation. However I am wondering what time complexity people expect of such a list? </p>
  
  <p>Especially for inserting I am wondering how I should implement it. I've read some locations around the internet, where some say inserting is O(1) while others say O(n) - all agree that a double linked list is O(1). However I think O(1) is the case for single linked lists too? </p>
  
  <p>As long as you know the preceding node you just let the preceding node point to the new new, and the new node will point towards where the preceding node did originally point to.</p>
  
  <p>That said it makes me wonder how people expect <code>insert</code> to behave? Normally it inserts elements BEFORE the given iterator. However with a single-linked-list it is hard to do so (one would have to go through <code>O(n)</code> time to get the preceding element &amp; then use above method). Is it common in such lists to make <code>insert</code> place items behind the current iterator? Or -probably better- is there another common function for this?</p>