为何ArrayList性能远超LinkedList？附性能测试代码

Hey everyone, I’ve been digging into the performance gap between ArrayList and LinkedList, and wanted to share my research and ask for your take on this topic. I’ve run some performance tests (snippet below) and noticed a clear, consistent performance advantage for ArrayList in most common scenarios.

My Test Code Snippet #

class ListPerformanceSpec extends Specification { 
    def "Throwaway"() { 
        given: "A Linked List" 
        List<Integer> list 
        List<Integer> results = new LinkedList<>() 
        
        when: "Adding numbers" 
        Random random = new Random() 
        // test each list 100 times 
        for (int ix = 0; ix < 100; ++ix) { 
            list = new LinkedList<>() 
            LocalDateTime start = ... // (code truncated)

Key Reasons for ArrayList's Better Performance #

From my analysis, these are the core factors driving the performance difference:

• Contiguous Memory Layout: ArrayList is backed by an array, which stores elements in a single contiguous block of memory. This plays perfectly to modern CPU caching—when you access one element, nearby elements get loaded into cache automatically, making subsequent accesses way faster. LinkedList uses scattered node objects with pointers, so the CPU can’t efficiently cache related elements, leading to frequent cache misses and slower overall access.

• O(1) Random Access: With ArrayList, you can jump directly to any element using its index in constant time (O(1)). For LinkedList, accessing a non-head/tail element requires traversing from the start or end of the list, which takes linear time (O(n)). This is a massive bottleneck for any operation that needs random access.

• Lower Overhead for Common Operations: While LinkedList is often said to have O(1) insertion/deletion, that’s only true if you already hold a reference to the target node. In most real-world cases, you first need to find that node (which is O(n)), plus the overhead of creating a new node object and updating pointers. ArrayList’s amortized O(1) insertion at the end (thanks to dynamic resizing) is usually faster in practice, and even inserting in the middle can outperform LinkedList because the cache efficiency offsets the cost of shifting elements.

• Faster Iteration: Iterating over ArrayList is just incrementing an index and accessing the array. LinkedList’s iterator has to follow a pointer to the next node every time, which adds up to significant overhead when working with large datasets.

I’d love to hear your thoughts—have you encountered edge cases where LinkedList actually outperforms ArrayList? Or any nuances I might have missed in my analysis?

内容的提问来源于stack exchange，提问作者Thom