title: Why is Array Lists faster than a Linked List for LIFO behaviour?
body: <p>I have written an algorithm that has a lot of appending and removing items to an end of a data structure (basically last in first out).</p>
  
  <p>Now for some reason, when I do this operation with <code>ArrayList</code>, it is much faster than a <code>LinkedList</code>, even through ArrayList requires the overhead of relocations. It's not even slightly faster. It's faster by miles!</p>
  
  <p>Why is this?</p>