Contexto Histórico

A Lista Ligada (Linked List) teve sua origem entre 1955 e 1956, quando Allen Newell, Cliff Shaw e Herbert A. Simon desenvolveram essa estrutura para a Information Processing Language (IPL), criada na RAND Corporation em parceria com o Carnegie Institute of Technology. A IPL foi usada pelos autores para desenvolver diversos programas pioneiros de inteligência artificial , incluindo a Máquina de Teoria Lógica, o Solucionador Geral de Problemas e um programa de xadrez para computador.

Diversos sistemas operacionais (SO) produzidos pela Technical Systems Consultants utilizavam Lista Ligada Simples (Singly Linked List) para seus sistemas de arquivos. Já o sistema operacional TSS/360 desenvolvido pela IBM para as máquinas System 360/370 utilizavam Lista Ligada Dupla (Doubly Linked List) em seus sistemas de arquivos.

Lista Ligada Simples

Devemos definir uma Lista Ligada Simples (Singly Linked List) como uma estrutura linear capaz de armazenar elementos conhecidos como nó, onde cada nó armazena o dado propriamente dito e uma referência chamada next que aponta para o próximo elemento da sequência. Apesar de seus elementos não estarem armazenados de forma contígua na memória como os arrays, ela continua sendo uma estrutura linear, pois seus nós permanecem ligados sequencialmente através de referências.

Para acessar o próximo elemento, seguimos a referência armazenada no nó atual. Em uma lista ligada, chamamos o primeiro nó de cabeça (head). Diferente de um array tradicional que é uma estrutura indexada e podemos acessar seus elementos através dos índices, aqui não temos essa facilidade, tendo que percorrer a lista caso quisermos acessar elementos que estão no meio, o que torna sua complexidade em $O(n)$. O primeiro elemento pode ser acessado diretamente através da referência head, tornando essa operação $O(1)$.

Depois de localizar o nó desejado (e seu predecessor), uma remoção em uma lista ligada ocorre apenas ajustando as referências entre os nós, sem necessidade de deslocar elementos como acontece em um array.

Lista Ligada Dupla

Existem diferentes tipos de listas ligadas, temos a Lista Ligada Simples que discutimos no tópico anterior, a Lista Ligada Dupla e também a chamada Lista Ligada Circular. Por hora, vamos discutir um pouco sobre a Lista Ligada Dupla.

Uma Lista Ligada Dupla é uma estrutura que segue os mesmos conceitos que uma lista simples, mas com algumas diferenças notáveis, a principal delas é a existência de uma ligação dupla entre os nós.

Considere o cenário de remoção do último elemento de uma lista. Em uma lista simples (mesmo que você guarde uma referência para a cauda/tail), a remoção exigirá um esforço $O(n)$. Isso ocorre porque, para remover o último elemento, precisamos atualizar a referência do penúltimo nó para null. Como as referências só apontam para a frente, não podemos ‘voltar’ a partir da cauda, sendo necessário percorrer a lista inteira desde o início. A Lista Ligada dupla resolve esse problema ao introduzir a capacidade de navegar nos dois sentidos.

Dessa forma, uma lista duplamente ligada pode ser caracterizada dessa maneira:

Um nó em uma lista duplamente ligada armazena duas referências, referência para o próximo nó next e uma referência para o nó anterior: prev.

Assim como a cabeça (head) aponta para o primeiro elemento, a cauda (tail) mantém uma referência para o último nó da estrutura, o que torna as coisas bem mais simples para remover ou inserir no último elemento da lista, sua complexidade temporal agora se torna $O(1)$ para este caso em uma lista duplamente ligada.

Lista Ligada Circular

Uma Lista Ligada Circular pode ter apenas uma direção de referência como em uma lista ligada simples ou duas referências como em uma lista duplamente ligada. A principal característica de uma lista circular é que o último nó referencia novamente o primeiro, formando um ciclo. Dependendo da implementação, ainda é possível manter referências para a cabeça (head) e para a cauda (tail) da lista.

Podemos caracterizar uma Lista Circular Simples dessa forma:

Em uma Lista Circular Dupla, a referência next do último nó da lista apontará para o primeiro nó da lista, enquanto a referência prev do primeiro nó da lista apontará para o último nó da lista.

Custos

Operação	Simples	Dupla	Circular Simples	Circular Dupla
Busca	O(n)	O(n)	O(n)	O(n)
Inserir no início	O(1)	O(1)	O(1)	O(1)
Remover no início	O(1)	O(1)	O(1)	O(1)
Inserir no meio	O(n)	O(n)	O(n)	O(n)
Remover no meio	O(n)	O(n)	O(n)	O(n)
Inserir no fim	O(n)	O(1)	O(1)	O(1)
Remover no fim	O(n)	O(1)	O(n)	O(1)

Conclusão

As listas ligadas representam uma solução para um problema que os arrays não conseguem resolver de forma eficiente: a inserção e a remoção frequentes de elementos. Ao substituir o armazenamento contíguo por uma sequência de nós conectados por referências, elas eliminam a necessidade de deslocar elementos a cada modificação da estrutura. Em contrapartida, perdem uma das principais vantagens dos arrays: o acesso direto por índice. Como acontece com qualquer estrutura de dados, não existe uma solução universalmente melhor. A escolha entre arrays e listas ligadas depende do tipo de operação predominante na aplicação.

No ecossistema Java, a implementação padrão da classe LinkedList (que faz parte da Collections Framework) utiliza a arquitetura de uma Lista Duplamente Ligada (Doubly Linked List). Isso garante que operações como adicionar ou remover elementos tanto no início (addFirst(), removeFirst()) quanto no final (addLast(), removeLast()) operem em tempo constante $O(1)$, tornando-a uma excelente escolha para implementação de Filas (Queues) e Pilhas (Stacks).