Programação · conceitos · estruturas de dados

O que é uma lista ligada?

Uma lista ligada (linked list) é uma estrutura de dados que guarda uma sequência de valores como uma cadeia de nós. Cada nó contém duas coisas: um valor e um ponteiro (uma referência) para o nó seguinte da cadeia. Os nós não estão dispostos lado a lado num único bloco de memória como estão os elementos de um array; em vez disso, cada um simplesmente aponta para onde o seguinte se encontra. Segue os ponteiros a partir do primeiro nó, a cabeça, e podes percorrer toda a sequência um elo de cada vez.

Como a cadeia é construída

Pensa nela como uma caça ao tesouro onde cada pista te diz onde encontrar a pista seguinte. A lista mantém uma referência ao nó cabeça. O ponteiro desse nó leva ao segundo nó, cujo ponteiro leva ao terceiro, e assim sucessivamente até que o ponteiro de um nó esteja vazio (muitas vezes chamado null ou None), o que marca o fim da lista.

[ valor | seguinte ] -> [ valor | seguinte ] -> [ valor | null ]

Como as ligações são apenas ponteiros, os nós podem estar em qualquer lugar da memória. Para fazer crescer a lista, alocas um novo nó e defines um ponteiro para ele; nada mais precisa de se mover.

Simplesmente vs duplamente ligada

Existem duas formas comuns, e a diferença está em quantos ponteiros cada nó transporta:

• Lista simplesmente ligada: cada nó aponta apenas para o nó seguinte. Podes avançar na lista mas não recuar, e pagas apenas um ponteiro por nó.
• Lista duplamente ligada: cada nó aponta tanto para o nó seguinte como para o anterior. Isso permite percorrê-la em ambas as direções e facilita algumas eliminações, ao custo de um ponteiro adicional por nó.

Lista ligada vs array

A forma mais clara de entender uma lista ligada é colocá-la ao lado de um array, porque fazem compromissos opostos. Um array guarda os seus elementos num bloco contíguo com um índice, por isso pode saltar para qualquer posição instantaneamente. Uma lista ligada abdica disso em troca de alterações baratas nas extremidades.

• Acesso aleatório. Um array lê qualquer elemento pelo seu índice em O(1). Uma lista ligada não tem índice: para chegar ao décimo nó tens de partir da cabeça e seguir nove ponteiros, por isso o acesso é O(n).
• Inserir e eliminar. Se já tens uma referência ao nó certo, uma lista ligada pode inserir ou remover aí religando um par de ponteiros, uma operação O(1) - sem deslocar os outros elementos. Num array, inserir ou eliminar no meio implica deslocar os elementos seguintes, o que é O(n).
• Memória e cache. Um array agrupa os seus valores, o que é favorável à cache da CPU. Uma lista ligada dispersa os seus nós e guarda um ponteiro adicional por nó, por isso usa mais memória por elemento e tende a ter pior localidade de cache.

Nenhuma é "melhor"; servem para trabalhos diferentes. Se precisas de pesquisas rápidas por posição, um array (ou um array dinâmico como uma list ou um vector) costuma vencer. Se os teus dados mudam muito de tamanho e sobretudo adicionas ou retiras nas extremidades, uma lista ligada pode encaixar bem. Para uma revisão de como estes custos são descritos, vê o nosso guia sobre a notação Big O.

As complexidades, com honestidade

Eis os custos padrão de uma lista ligada, com a ressalva que sempre importa:

• Acesso e pesquisa: O(n). Não há índice, por isso encontrar um valor significa percorrer a cadeia a partir da cabeça.
• Inserção e eliminação: O(1) quando já tens uma referência ao nó (por exemplo, mesmo na cabeça). Se primeiro tens de encontrar o sítio, essa pesquisa é O(n), e o total reflete ambas as partes.

Essa condição "quando tens o nó" é a parte que as pessoas costumam omitir. Inserir na cabeça de uma lista simplesmente ligada é genuinamente tempo constante; inserir depois de algum valor que ainda tens de localizar não é.

Onde as listas ligadas são usadas

As listas ligadas são mais um bloco de construção do que um contentor do dia a dia. São uma forma natural de implementar uma pilha (stack) ou uma fila (queue), já que estas só adicionam e retiram nas extremidades. Encaixam em situações onde o tamanho da coleção muda muito e não precisas de acesso rápido por posição. Algumas estruturas usam nós ligados internamente; por exemplo, uma forma comum de tratar as colisões numa hash table é encadear as entradas em colisão numa pequena lista ligada por bucket.

Os compromissos

• Sem acesso aleatório. Chegar a uma posição arbitrária custa O(n) porque segues os ponteiros a partir da cabeça; não há índice com que saltar.
• Memória adicional por elemento. Cada nó guarda pelo menos um ponteiro (dois numa lista duplamente ligada) além do seu valor.
• Localidade de cache mais fraca. Nós dispersos são menos favoráveis à cache do que um array contíguo, o que pode tornar o percurso mais lento na prática mesmo quando o Big O é o mesmo.
• Edições baratas num nó conhecido. A vantagem: inserir ou remover num nó que já deténs é O(1), sem deslocar o resto dos dados.

FAQ

Qual é a diferença entre uma lista ligada e um array? Um array guarda os elementos num bloco contíguo com um índice, por isso lê qualquer posição em O(1) mas deslocar elementos para inserir ou eliminar no meio custa O(n). Uma lista ligada guarda nós separados unidos por ponteiros, por isso não tem acesso aleatório (O(n) para chegar a uma posição) mas pode inserir ou eliminar num nó conhecido em O(1).

Porque é que aceder a um elemento é O(n)? Porque uma lista ligada não tem índice. Para chegar ao n-ésimo nó partes da cabeça e segues a cadeia de ponteiros n vezes, por isso o custo cresce com a posição que queres.

Qual é a diferença entre simplesmente e duplamente ligada? Numa lista simplesmente ligada cada nó aponta apenas para o nó seguinte, por isso só te podes mover para a frente. Numa lista duplamente ligada cada nó aponta também para o nó anterior, por isso podes mover-te em ambas as direções, ao custo de um ponteiro adicional por nó.

Quando devo usar uma lista ligada? Quando o tamanho da coleção muda muito e adicionas ou retiras sobretudo nas extremidades, ou como base de uma pilha ou de uma fila. Se precisas de acesso rápido por posição, um array costuma ser a melhor escolha.

Guias relacionados: hash tables, notação Big O, recursão.