title: Insertion in the middle of ArrayList vs LinkedList
body: <p>Talking in Java's context. If I want to insert in the middle of either an <code>ArrayList</code> or a <code>linkedList</code>, I've been told that <code>Arraylist</code> will perform terribly.</p>
  
  <p>I understand that it is because, we need to shift all the elements and then do the insertion. This should be of the order n/2 i.e. O(n).</p>
  
  <p>But is not it the same for <code>linkedList</code>. For linked List, we need to traverse till the time we find the middle, and then do the pointer manipulation. In this case too, it will take O(n) time. Would not it?</p>
  
  <p>Thanks</p>