3 ms·

This is not necessarily true in garbage-collected languages.

• gamegoblin 10y ago
  For what it's worth, I did the following benchmarks in Java 8: Make two List<Object>s. One is LinkedList one is ArrayList. Then timed how long it took to empty the list by deleting random indexes. For LinkedList this is O(n) to iterate up to the element and O(1) to remove it. For ArrayList isn't O(n) to shift all of the following elements down by 1 index. As the list size approaches infinity, the benchmark shows that the ArrayList is 10x faster. That's because even though you are copying a ton of memory, it's all contiguous in memory and highly cacheable. In the LinkedList you are just chasing pointers to iterate the array, but they are not cacheable. A more common example is the case of queues. I made two Queue<Object>s, one was LinkedList and another ArrayDeque. Then I polled the head of the queue until empty. As N gets larger, the ArrayDeque is 3x faster.