Testing Java Collections in Practice: ArrayList vs LinkedList and Performance Myths

If you studied Computer Science or prepared for tech interviews, you probably heard this classic rule:

“Use LinkedList when you have frequent insertions and deletions. Use ArrayList only when you need fast access by index.”

In real-world applications, this advice is not entirely true.

First, adding an item in the middle of a LinkedList is not $O(1)$—you still have to loop through the list to find the target position ($O(N)$). Second, modern hardware works very differently from textbook theory. Even when LinkedList looks fast on paper, things like CPU cache and memory allocation make ArrayList win in almost every common scenario.

To see how these collections actually behave, I built a benchmark project using JMH (Java Microbenchmark Harness) on Java 21 LTS. I tested Lists (ArrayList, LinkedList, ArrayDeque), Sets (HashSet, LinkedHashSet, TreeSet), and Maps (HashMap, LinkedHashMap, TreeMap) to compare speed and memory usage.

Here is what the numbers showed.

---

01. Why Hardware Matters: CPU Cache vs. Following Pointers

Big-O notation is great, but it assumes all memory access takes the same amount of time. On real hardware, that is not how it works.

Modern CPUs don’t read bytes one by one from RAM. They load blocks of 64 bytes (called Cache Lines) into very fast L1, L2, and L3 cache memory. Reading from L1 cache takes about 1 nanosecond, while reading from RAM can take 50 to 100 nanoseconds—up to 100 times slower!

---

02. Comparing Lists: ArrayList, LinkedList, and the Secret Weapon

Here are the benchmark results for $N = 20,000$ operations:

Because of CPU cache prefetching, looping through an ArrayList was over 3 times faster than a LinkedList.

What about adding items at the beginning?

People often say LinkedList is better here because it doesn’t need to move items around. An ArrayList does have to shift memory using System.arraycopy.

However, many developers forget about ArrayDeque:

ArrayDeque uses a circular array buffer. It inserts items at the beginning in $O(1)$ time without creating extra Node objects in memory. It was almost 3 times faster than LinkedList!

Operation ($N = 20,000$)	ArrayList	LinkedList	ArrayDeque	Takeaway
Add at the end	~42 μs	~112 μs	~38 μs	Continuous arrays are much faster.
Add at beginning (index 0)	~2,840 μs	~105 μs	~36 μs	ArrayDeque easily beats LinkedList.
Add in the middle ($N/2$)	~1,410 μs	~2,180 μs	N/A	ArrayList is faster even copying memory!
Get by index (get(i))	~8 μs	~14,200 μs	N/A	Direct array math vs looping through nodes.
Loop through all items	~14 μs	~48 μs	~15 μs	3.4x faster thanks to CPU cache.

---

03. Sets and Maps: Hash Tables vs. Trees

Next, I tested Set and Map collections:

Key-Value Collections
├── HashMap        ──► Fast O(1) average lookup, stores data in buckets
├── LinkedHashMap  ──► O(1) lookup + keeps the order you inserted
└── TreeMap        ──► Keeps keys sorted, but operations take O(log N)

Lookup Speed Comparison:

A Cool Detail About LinkedHashMap and LinkedHashSet

Even though HashMap is slightly faster for writing and reading, LinkedHashMap is actually faster to loop through:

• In a normal HashMap, the iterator has to scan every bucket in the table—including thousands of empty null slots.
• In LinkedHashMap, entries are linked together in a simple chain. The loop just follows that chain directly and skips all empty spaces.

---

04. Memory and Cloud Cost: How Much Heap Do They Use?

In cloud environments (like Kubernetes pods with RAM limits), high memory usage increases your cloud bill and can trigger out-of-memory errors (OOMKilled).

I measured the actual Heap memory used for 100,000 items on 64-bit Java 21:

Notice that LinkedList uses more than double the memory of ArrayList for the exact same data, simply because of node wrappers and pointer references.

---

05. Simple Guide: Which One Should You Use?

Here is a practical rule of thumb for your daily work and interviews:

1. Need a standard list? Use ArrayList. If you already know roughly how many items you’ll have, pass the initial size (new ArrayList<>(expectedSize)) to avoid internal resizing.
2. Need a Queue, Stack, or FIFO? Use ArrayDeque. You almost never need LinkedList.
3. Need fast key-value lookups? Use HashMap.
4. Need to keep insertion order? Use LinkedHashMap or LinkedHashSet (great for JSON responses and simple caches).
5. Need keys always sorted? Use TreeMap or TreeSet, accepting that operations take a bit longer ($O(\log N)$).

---

06. Source Code

All benchmark tests were written with OpenJDK JMH and the code is open source on GitHub. You can clone the project and run it yourself with a single command:

git clone https://github.com/marcelopirro/java-collections-benchmark.git
cd java-collections-benchmark
./mvnw clean package -DskipTests
java -jar target/benchmarks.jar

🔗 GitHub Repository: github.com/marcelopirro/java-collections-benchmark

Em praticamente todo currículo universitário de Ciência da Computação e livro de preparação para entrevistas técnicas, você encontra a mesma recomendação clássica:

“Use LinkedList quando precisar de inserções e remoções frequentes, pois ela opera em tempo $O(1)$. Use ArrayList apenas quando precisar de acesso aleatório rápido por índice.”

Só tem um problema: em sistemas reais de produção, esse conselho é duplamente falacioso.

Primeiro, porque inserir em uma LinkedList por índice sequer é $O(1)$ na prática — você gasta $O(N)$ só para navegar nó por nó até a posição desejada. Segundo, porque mesmo no início ou no fim (onde a operação é teoricamente $O(1)$), a alocação de objetos Node individuais e as falhas de cache da CPU (cache misses) tornam ela drasticamente mais lenta do que alternativas baseadas em arrays.

Seguir esse dogma didático sem senso crítico pode derrubar a vazão do seu microsserviço e dobrar o consumo de memória RAM na nuvem.

Para entender o que realmente acontece sob o capô na arquitetura moderna de computadores, montei um laboratório empírico de microbenchmarks usando OpenJDK JMH (Java Microbenchmark Harness) sobre o Java 21 LTS. Testamos Listas (ArrayList, LinkedList, ArrayDeque), Sets (HashSet, LinkedHashSet, TreeSet) e Maps (HashMap, LinkedHashMap, TreeMap) avaliando tempo de execução, latência e pegada de memória na Heap.

Aqui está o que os dados reais mostram.

---

01. A Realidade do Hardware: Localidade de Cache vs. Salto de Ponteiros

O erro fundamental das análises teóricas clássicas é assumir que o acesso à memória RAM tem custo uniforme.

No hardware físico moderno, a CPU nunca busca bytes individuais diretamente da memória principal. Ela carrega blocos de 64 bytes conhecidos como Cache Lines para memórias ultrarrápidas de cache: L1, L2 e L3.

Acessar a cache L1 leva cerca de 1 nanossegundo (~4 ciclos de clock), enquanto buscar dados da memória RAM física leva entre 50 e 100 nanossegundos (~200 ciclos)—duas ordens de grandeza mais lento!

---

02. O Duelo das Listas: Inserção, Leitura e a Arma Secreta

Vamos aos dados obtidos para $N = 20.000$ operações no JMH:

Graças ao prefetcher de hardware da CPU, iterar sobre um ArrayList é mais de 3 vezes mais rápido do que sobre uma LinkedList.

E a famosa inserção no início (índice 0)?

A teoria diz que a LinkedList deveria vencer com folga aqui porque não precisa deslocar elementos. E de fato, inserir no índice 0 em um ArrayList exige mover a memória adjacente com System.arraycopy.

No entanto, a maioria dos engenheiros esquece da existência do ArrayDeque:

O ArrayDeque utiliza um array circular com ponteiros de head e tail. Ele insere na cabeça em tempo $O(1)$ real sem instanciar nenhum objeto Node na Heap, sendo quase 3x mais rápido que a LinkedList.

Operação ($N = 20.000$)	ArrayList	LinkedList	ArrayDeque	Veredito Tático
Append (Fim)	~42 μs	~112 μs	~38 μs	Arrays contíguos dominam em throughput.
Prepend (Início 0)	~2.840 μs	~105 μs	~36 μs	ArrayDeque supera a LinkedList com folga.
Inserção Meio ($N/2$)	~1.410 μs	~2.180 μs	N/A	ArrayList vence mesmo copiando memória!
Acesso Aleatório (get(i))	~8 μs	~14.200 μs	N/A	Offset imediato ($O(1)$) vs varredura sequencial ($O(N)$).
Iteração Sequencial	~14 μs	~48 μs	~15 μs	3.4x mais rápido via cache L1.

---

03. Sets e Maps: Hashing vs. Árvores Balanceadas

Expandindo para coleções associativas e de unicidade, comparamos:

Coleções Chave-Valor
├── HashMap        ──► O(1) médio de busca, array de buckets (treeifica colisões)
├── LinkedHashMap  ──► O(1) médio + preserva ordem de inserção ou acesso
└── TreeMap        ──► O(log N) garantido, Red-Black Tree auto-balanceada

Comparativo de Busca e Recuperação:

O Superpoder Oculto do LinkedHashMap e LinkedHashSet

Embora o HashMap seja marginalmente mais rápido em inserções brutas, a iteração do LinkedHashMap é surpreendentemente mais veloz:

• No HashMap, o iterador precisa inspecionar todos os índices do array interno de buckets—inclusive milhares de posições vazias (null).
• No LinkedHashMap, cada entrada possui referências diretas duplamente ligadas (before e after). O iterador percorre diretamente a corrente linear, pulando os buckets vazios.

---

04. A Realidade na Nuvem: Pegada de Memória (Heap Footprint)

Em arquiteturas de microsserviços em nuvem (containers Kubernetes com limites estritos de memória e CPU), o overhead de RAM vira custo na fatura da AWS/GCP e risco de reinicializações por OOMKilled.

Medimos a alocação de Heap para 100.000 elementos no OpenJDK HotSpot 64-bit (com Compressed OOPs):

A LinkedList consome mais que o dobro de memória da ArrayList para guardar rigorosamente os mesmos dados, unicamente devido aos nós e referências intermediárias.

---

05. Guia Prático de Decisão para o Dia a Dia

Para escolher a estrutura correta em sistemas reais e entrevistas técnicas:

1. Precisa de uma lista comum? Escolha ArrayList. Se souber a estimativa de tamanho, defina a capacidade inicial (new ArrayList<>(expectedSize)) para evitar realocações.
2. Precisa de Fila, Pilha ou Deque (FIFO/LIFO)? Escolha ArrayDeque. Dificilmente haverá razão para usar LinkedList.
3. Precisa de busca rápida por chave? Escolha HashMap.
4. Precisa de ordem previsível de iteração? Escolha LinkedHashMap ou LinkedHashSet (ideal para serialização JSON determinística ou caches LRU).
5. Precisa de chaves sempre ordenadas ou queries de intervalo (subMap)? Escolha TreeMap ou TreeSet, arcando conscientemente com o custo logarítmico $O(\log N)$.

---

06. Código-Fonte e Reprodutibilidade

Todo o código de teste foi construído com OpenJDK JMH e está aberto no GitHub. Você pode clonar o repositório e executar os benchmarks no seu próprio hardware com um único comando usando o Maven Wrapper incluído:

git clone https://github.com/marcelopirro/java-collections-benchmark.git
cd java-collections-benchmark
./mvnw clean package -DskipTests
java -jar target/benchmarks.jar

🔗 Repositório GitHub: github.com/marcelopirro/java-collections-benchmark