title: How does add(index, element) method work behind the scenes using LinkedList?
body: <p>When adding an element at a certain index using the <strong>add(index, element)</strong> method in an <em>ArrayList</em>, it places the element at that index, while all the other elements change their indexes by 1 (they move in memory). That's why an <em>ArrayList</em> has the complexity O(n) when adding an element at a certain position.</p>
  
  <p>In case of a doubly <em>LinkedList</em>, I know that the elements have pointers to the previous element and also for the next one.</p>
  
  <p>My question is, when using the <strong>add(index, element)</strong> method related to a <em>LinkedList</em>, what will actually happen behind the scenes? I know that using the <em>LinkedList</em> the rest of the elements don't move in memory, so how come they can still be placed at a certain index without moving in memory?</p>