LinkedLists: O que acontece por trás da interface

Neste artigo veremos o que ocorre na estrutura interna da classe LinkedList, que implementa a interface List em Java. Essa classe modela uma lista duplamente encadeada, e pode ser usada como implementação para pilhas, filas, e deques com grande eficiência.

Diferente das listas sequenciais, os dados de uma lista encadeada estão espalhados na memória, isto é, os elementos não estão juntos em grandes blocos de memória, mas em lugares diferentes dela. Isso faz com que as operações de inserção e remoção sejam feitas com mais facilidade, tanto no início como no fim da lista. Vejamos o porquê.

Num vetor, os dados ficam armazenados na memória sequencialmente; dessa forma, pra descobrirmos a posição de qualquer elemento, só precisamos saber onde está o primeiro e saber qual o tamanho que cada elemento ocupa. Entretanto, nas LinkedLists cada objeto está espalhado na memória. Como acha-los?

A solução é simples: nas listas encadeadas, cada elemento guarda a posição do próximo, ou seja, se eu quiser achar o quinto elemento, preciso do quarto; para achar o quarto, preciso do terceiro. E assim sucessivamente até percebermos que precisamos percorrer toda a lista se quisermos chegar num elemento qualquer. Com isso, já achamos um ponto negativo das LinkedLists. Mas será tão negativo assim? Isso varia muito da utilização, pois geralmente ocorre o acesso à lista inteira, e não a um elemento só.

A LinkedList do Java, especificamente, implementa uma lista circular duplamente encadeada: cada elemento guarda a posição do próximo e do anterior, formando um círculo, onde o elemento depois do último é o primeiro, e o anterior a este, é aquele.

Veja na Figura 1 como os dados de uma lista encadeada ficam salvos na memória. Cada elemento destes é chamado de nó, e é composto basicamente por três partes: dados, posição anterior e próxima posição.

Na Figura 1 vemos que podemos percorrer a lista tanto aumentando o índice (setas vermelhas) como diminuindo (setas azuis). Devemos lembrar que a classe LinkedList deve salvar onde estão o primeiro e o último elemento, pois são nessas posições que ocorrem mais inserções. Como já temos o entendimento da estrutura, vamos analisar as operações.

A inserção no início e no fim são triviais, uma vez que temos essas posições; ela segue os seguintes passos:

Para inserção no início:

1. Criar o nó com os dados.
2. Configurar os apontadores do nó criado. O seu anterior é o último elemento da lista, e seu posterior é o antigo primeiro nó.
3. Feito isso, configuramos o último elemento da lista: seu próximo agora é o nó recém-criado.
4. Agora configuramos o antigo primeiro elemento: seu anterior agora é também o nó recém-criado.

A inserção no final da lista é feita de forma análoga, só que com os apontadores trocados, pois a lista funciona da mesma forma para frente ou para trás. Veja na figura 2 como funciona a inserção no início da lista.

Obviamente, os antigos nós 0 e 1 passaram a ser 1 e 2, pois o novo nó inserido ocupará o índice 0. Com isso, vemos que a inserção no início e no fim da lista tem complexidade constante, pois tem operações já definidas que não dependem de nenhum outro fator, seja a lista de qualquer tamanho. Apesar de a inserção em listas sequenciais (vetores) terem a inserção no final também constante, ela eventualmente gera um grande overhead com o doubleVector, explicado no artigo anterior. Com relação à inserção no início da lista, as linkedlists são muito mais rápidas, devido ao problema de shift de elementos dos arrays.

A adição de elementos em uma posição aleatória funciona quase da mesma forma que nas extremidades, a única diferença é que precisamos percorrer a lista até o ponto da inserção, e então repetirmos o processo. Percebemos então que este algoritmo é de complexidade linear, pois o número de operações cresce proporcionalmente com a posição de inserção. Vale salientar que nessas inserções o Java escolhe sempre o caminho mais curto para percorrer, isto é, se quisermos adicionar um elemento nas últimas posições da lista, o caminho a ser percorrido, obviamente, é o de trás pra frente.

Apesar de a inserção em posições arbitrárias de uma ArrayLists ser também linear, ela é mais demorada, pois o shift de elementos faz muitos acessos (load e store) à memória, enquanto a lista encadeada faz poucos acessos, só para fins de percorrimento.

A remoção é também linear, e também simples. Basta percorrermos a lista até a posição desejada, e alterarmos os apontadores dos elementos anterior e posterior ao que será removido. Veja na figura 3 a remoção do elemento de índice 9.

Obviamente, os índices nas figuras são apenas para melhor compreensão, pois eles não são salvos em lugar nenhum. Sabemos que Java tem o camarada Garbage Collector, e por isso não precisamos nos preocupar com a posição removida, entretanto, em outras linguagens seria necessário que nós liberássemos a memória que o elemento 9 utilizava, caso contrário teríamos desperdício de memória com elementos que não estão mais sendo úteis para o programa, o que é chamado de vazamento de memória.

Com relação à busca de um elemento específico, tanto nos arrays como nas listas encadeadas, temos complexidade linear, pois iriamos procurar um por um, e no pior caso, percorreríamos a lista toda.

Terminamos aqui nosso artigo sobre LinkedLists, e concluímos que em casos de inserção e (principalmente) de remoção, elas levam vantagem sobre as ArrayLists, entretanto, no acesso, estes são mais rápidos. Dessa forma, devemos analisar bem nosso programa e ver quais operações estamos utilizando com mais frequência, para que façamos uma boa escolha e tenhamos o máximo de eficiência possível.

Espero ter ajudado, galera, e até o próximo.