Já se deparou em uma discussão técnica sobre como reduzir o consumo de memória ou melhorar a performance ao manipular grandes volumes de dados? Ou, talvez, durante uma entrevista, já te perguntaram sobre as diferenças entre as principais estruturas de dados disponíveis e qual delas escolher em um determinado cenário?
A escolha da estrutura de dados correta pode ter um impacto significativo na performance e no consumo de recursos da aplicação, dependendo do contexto.
Neste artigo, vamos explorar duas implementações populares da interface List do Java: ArrayList e LinkedList, e entender em quais situações cada uma delas se destaca como melhor opção.
ArrayList e LinkedList
Ambas são implementações da interface List e armazenam elementos de forma sequencial, mantendo a ordem de inserção.
Como funcionam internamente
ArrayList:
- Usa um array dinâmico (como uma “fila” de cadeiras que pode crescer) para armazenar os elementos.
- Quando o array enche, ele cria um novo array maior e copia os elementos para lá.
LinkedList:
- Usa uma lista duplamente encadeada (como uma “corrente” onde cada elo sabe o anterior e o próximo).
- Cada elemento é um nó que contém o valor e ponteiros para o nó anterior e o próximo.
Quando usar cada uma
ArrayList:
- Melhor para acessar elementos por índice (como pegar um item específico rapidamente), pois é como acessar uma posição em um array.
- Boa para adicionar elementos no final da lista.
- Não é tão boa para inserções e remoções no meio, pois precisa mover os elementos para ajustar.
LinkedList:
- Melhor para adicionar ou remover elementos no início ou no meio, pois só ajusta os ponteiros.
- Acessar um elemento específico é mais lento, pois precisa “caminhar” pelos nós para chegar até lá.
Performance
ArrayList:
- Acesso rápido por índice: O(1) (instantâneo).
- Inserções e remoções no meio são mais lentas: O(n) (reorganiza elementos).
LinkedList:
- Inserções e remoções rápidas em qualquer posição: O(1) (só ajusta ponteiros).
- Acesso por índice é lento: O(n) (precisa percorrer a lista).
Uso de memória
ArrayList:
- Não tem ponteiros adicionais, o que torna o uso de memória por elemento mais eficiente.
- Pode desperdiçar memória se o array interno for maior que o necessário.
LinkedList:
- Cada elemento (nó) usa mais memória porque armazena dados e dois ponteiros (para o anterior e o próximo nó).
Teste prático
Segue o resultado de um exemplo prático comparando LinkedList e Arraylist:
Código no GitHub: [https://github.com/jequelia/ExecutionTimeExample]
Operações em LinkedList:
- Inserção no início (Insert at Beginning): 55 ms
- Inserção no meio (Insert at Middle): 7873 ms
- Inserção no final (Insert at End): 49 ms
- Acesso aos elementos (Access Elements): 22628 ms
Observações:
- A inserção no início é relativamente rápida, dado que LinkedList é uma lista encadeada e só precisa ajustar os ponteiros.
- A inserção no meio leva mais tempo, pois envolve percorrer a lista até o ponto de inserção.
- A inserção no final também é rápida, pois o LinkedList tem referência direta ao último nó.
- O acesso aos elementos é extremamente lento (22628 ms), pois LinkedList precisa iterar pelos nós para acessar um elemento em uma posição específica.
Operações em ArrayList:
- Inserção no início (Insert at Beginning): 1008 ms
- Inserção no meio (Insert at Middle): 1538 ms
- Inserção no final (Insert at End): 13 ms
- Acesso aos elementos (Access Elements): 7 ms
Observações:
- A inserção no início é significativamente mais lenta do que em LinkedList, já que ArrayList precisa deslocar todos os elementos subsequentes para abrir espaço.
- A inserção no meio é mais rápida em comparação ao LinkedList, mas ainda assim exige o deslocamento dos elementos.
- A inserção no final é extremamente rápida (13 ms), pois o ArrayList simplesmente adiciona o elemento no fim do array, sem necessidade de mover outros elementos.
- O acesso aos elementos é muito rápido (7 ms), já que o ArrayList permite acesso direto através de um índice.
Conclusão
Em resumo, Entre ArrayList e LinkedList depende diretamente do tipo de operação que você precisa operar.
O ArrayList é a melhor opção quando o acesso rápido a elementos é crucial, pois armazena os dados de forma contínua na memória. Porém, operações de inserção e remoção, especialmente no início e no meio da lista, podem ser mais lentas devido à necessidade de realocar elementos.
Por outro lado, o LinkedList se destaca quando as operações de inserção e remoção são frequentes, principalmente no início ou no meio da lista. Aqui, o custo de acessos aleatórios é maior, já que os elementos não são armazenados de forma contígua, mas sim em nós conectados.
Conhecer as características de cada implementação e entender as necessidades específicas do seu projeto são fundamentais para tomar a decisão mais apropriada e garantir a melhor performance da aplicação.
Artigo escrito por Jequelia Santana, da Comunidade Programaria.
REFERÊNCIAS: