title: Java ListIterator Performance
body: <p>I was reading a <a href="https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist">thread</a> here about the performance of java ArrayList and LinkedList. There is an answer from <a href="https://stackoverflow.com/users/219394/kevin-brock">Mr Kevin Brock</a> that reads the following.</p>
  
  <blockquote>
    <p>"Linked list add is not always O(1)
    [or this should say addLast() is
    O(1)]. <strong>This is only true if done from
    within a ListIterator</strong>. The add methods
    in Java's LinkList implementation must
    search through the list if additions
    are not on the head or tail."</p>
  </blockquote>
  
  <p>I din't understand what he meant by "only if done through ListIterator". Does it mean there is a data structure within the linkedlist that holds the reference of each index and as soon as we get the listiterator from a certain index, listiterator is returned straight away without walking through the list to find that index?</p>
  
  <p>Thanks guys!</p>