C# LinkedList<T>

A List guarda os itens lado a lado, como cadeiras numeradas num cinema. A lista ligada guarda de outro jeito: cada item sabe quem vem antes e quem vem depois dele, como os vagões de um trem engatados um no outro. Isso torna muito barato encaixar ou soltar um vagão no meio do trem, e é para isso que existe a LinkedList<T>.

Todos os programas desta aula rodaram com o .NET 10 na máquina da Ana (usuária ana, computador notebook), na pasta ~/cs, com dotnet run arquivo.cs. Você pode repetir cada um no editor do guia.

A ideia: um trem de vagões engatados

Cada vagão de um trem só conhece os dois vizinhos: o engate da frente e o engate de trás. Ninguém numera os vagões. Para chegar ao terceiro, você começa na locomotiva e vai passando de vagão em vagão.

  First                                            Last
    ↓                                                ↓
 [locomotiva] ⇄ [vagão 1] ⇄ [vagão 2] ⇄ [vagão 3]
               Previous ←  nó  → Next

Cada vagão é um nó (node): uma caixinha com o valor (o que está guardado) e dois engates, Next ("próximo") e Previous ("anterior"). Como cada nó conhece os dois vizinhos, o nome técnico é lista duplamente ligada. Isso tem duas consequências:

• Encaixar ou tirar um nó no meio é rápido. Basta mexer nos engates dos vizinhos; ninguém precisa ser empurrado. Numa List, inserir no começo obriga a empurrar todos os itens uma posição.
• Não existe posição. Não há trem[2]. Para chegar a um item, você anda de nó em nó.

1. Montar o trem: AddFirst e AddLast

var trem = new LinkedList<string>();

trem.AddLast("vagão 1");
trem.AddLast("vagão 2");
trem.AddFirst("locomotiva");
trem.AddLast("vagão 3");

Console.WriteLine(string.Join(" = ", trem));
Console.WriteLine($"Peças: {trem.Count}");
Console.WriteLine($"Primeira: {trem.First!.Value}");
Console.WriteLine($"Última: {trem.Last!.Value}");

$ dotnet run trem.cs
locomotiva = vagão 1 = vagão 2 = vagão 3
Peças: 4
Primeira: locomotiva                « o AddFirst pôs na frente, mesmo vindo depois
Última: vagão 3

new LinkedList<string>()

Cria uma lista ligada vazia de textos.

trem.AddLast("vagão 1");

"Acrescentar no fim." Engata o vagão no final do trem.

trem.AddFirst("locomotiva");

"Acrescentar no começo." Engata na frente de todos. Numa lista ligada, isso é tão rápido quanto acrescentar no fim.

trem.First / trem.Last

O primeiro e o último nó (não o valor!). Numa lista vazia, os dois são null.

.Value

O valor guardado no nó.

!

O operador "eu garanto que não é null". Como First pode ser null, o compilador avisaria (CS8602) sem ele. Aqui a lista tem itens, então é seguro. Veja Referências Anuláveis.

Você também pode criar a lista já cheia, passando uma coleção: new LinkedList<string>(["a", "b", "c"]). Os itens ficam na mesma ordem da coleção.

2. Os nós: Find, Next, Previous, AddAfter

O que torna a lista ligada especial é trabalhar com os nós. Um nó é do tipo LinkedListNode<T> ("nó de lista ligada"). Com um nó na mão, você vê os vizinhos e encaixa vagões ao lado dele.

var trem = new LinkedList<string>(["locomotiva", "vagão 1", "vagão 2", "vagão 3"]);

LinkedListNode<string>? no = trem.Find("vagão 1");
Console.WriteLine(no!.Value);
Console.WriteLine(no.Previous!.Value);
Console.WriteLine(no.Next!.Value);

trem.AddAfter(no, "restaurante");
trem.AddBefore(no, "carvão");
Console.WriteLine(string.Join(" = ", trem));

trem.Remove("vagão 2");
trem.RemoveLast();
Console.WriteLine(string.Join(" = ", trem));
Console.WriteLine(trem.Find("vagão 9") is null);

$ dotnet run nos.cs
vagão 1
locomotiva                                                      « o vizinho de trás
vagão 2                                                         « o vizinho da frente
locomotiva = carvão = vagão 1 = restaurante = vagão 2 = vagão 3
locomotiva = carvão = vagão 1 = restaurante
True                                                            « Find não achou: null

LinkedListNode<string>? no = trem.Find("vagão 1");

Find = encontrar. Anda do começo ao fim procurando o valor e devolve o nó onde ele está, ou null se não achar (por isso o ? no tipo). Na prática, quase sempre se escreve var no = ….

no.Previous / no.Next

Os nós vizinhos. O Previous do primeiro e o Next do último são null: ali o trem acaba.

trem.AddAfter(no, "restaurante");

"Acrescentar depois": engata um vagão novo logo atrás de no.

trem.AddBefore(no, "carvão");

"Acrescentar antes": engata logo na frente de no.

trem.Remove("vagão 2");

Procura o valor e tira o primeiro nó que o tiver. Devolve true se tirou. Também existe Remove(no), que tira um nó que você já tem na mão (sem procurar).

trem.RemoveLast();

Tira o último nó. O irmão dele é o RemoveFirst().

var playlist = new LinkedList<string>(["Asa Branca", "Garota de Ipanema", "Trem das Onze"]);

// encaixe "Aquarela" depois de "Garota de Ipanema"

Console.WriteLine(string.Join(", ", playlist));

var playlist = new LinkedList<string>(["Asa Branca", "Garota de Ipanema", "Trem das Onze"]);

var garota = playlist.Find("Garota de Ipanema");
playlist.AddAfter(garota!, "Aquarela");

Console.WriteLine(string.Join(", ", playlist));

3. Andar pela lista: para a frente e para trás

O foreach percorre do primeiro ao último, como em qualquer coleção. Mas, andando pelos nós, você pode ir também de trás para a frente:

var playlist = new LinkedList<string>(["Asa Branca", "Garota de Ipanema", "Aquarela", "Trem das Onze"]);

for (var no = playlist.First; no is not null; no = no.Next)
{
    Console.WriteLine($"Tocando: {no.Value}");
}

Console.WriteLine("--- de trás para a frente ---");
for (var no = playlist.Last; no is not null; no = no.Previous)
{
    Console.WriteLine(no.Value);
}

$ dotnet run percorrer.cs
Tocando: Asa Branca
Tocando: Garota de Ipanema
Tocando: Aquarela
Tocando: Trem das Onze
--- de trás para a frente ---
Trem das Onze
Aquarela
Garota de Ipanema
Asa Branca

Leia o primeiro for (aula for) em três partes:

var no = playlist.First;

Começa no primeiro nó.

no is not null;

Continua enquanto houver nó. Depois do último, Next é null e o laço para.

no = no.Next

A cada volta, passa para o vagão seguinte.

O segundo for é o espelho: começa no Last e anda com Previous. É assim que um tocador de música implementa os botões "próxima" e "anterior".

Remover durante o percurso

Dentro de um foreach, você não pode mudar a lista (dá InvalidOperationException, veja Quando dá errado). Andando pelos nós, pode, desde que guarde o próximo antes de remover o atual:

var numeros = new LinkedList<int>([1, 2, 3, 4, 5, 6]);

var no = numeros.First;
while (no is not null)
{
    var proximo = no.Next;
    if (no.Value % 2 == 0)
        numeros.Remove(no);
    no = proximo;
}
Console.WriteLine(string.Join(", ", numeros));

$ dotnet run remover.cs
1, 3, 5

var proximo = no.Next;

Anota o vizinho da frente antes de remover. Um nó removido perde os engates (o Next dele vira null), e o laço pararia no meio.

numeros.Remove(no);

Tira o nó que você já tem na mão: não precisa procurar.

4. List ou LinkedList?

A lista ligada parece ótima, mas no dia a dia a List<T> ganha quase sempre. Os itens da List ficam juntinhos na memória, e o processador lê memória contínua muito depressa. Os nós da LinkedList ficam espalhados, e cada nó gasta memória extra com os dois engates.

Regra prática: comece com List<T>. Use LinkedList<T> quando o programa encaixa e tira itens no meio o tempo todo, sempre ao lado de nós que ele já tem na mão (uma playlist com "tocar a seguir", um editor que guarda as linhas como nós). Para tirar só do começo, a Queue é mais simples; só do fim, a Stack.

Quando dá errado

$ dotnet run indice.cs
/home/ana/cs/indice.cs(2,19): error CS0021: Não é possível aplicar a indexação com [] a uma expressão do tipo "LinkedList<string>"

Ocorreu uma falha no build. Corrija os erros de build e execute novamente.

$ dotnet run vazia.cs
Unhandled exception. System.InvalidOperationException: The LinkedList is empty.
   at System.Collections.Generic.LinkedList`1.RemoveFirst()
   at Program.<Main>$(String[] args) in /home/ana/cs/vazia.cs:line 2

$ cat nulo.cs
var trem = new LinkedList<string>();
Console.WriteLine(trem.First is null);
Console.WriteLine(trem.First.Value);
$ dotnet run nulo.cs
/home/ana/cs/nulo.cs(3,19): warning CS8602: Desreferência de uma referência possivelmente nula.
True
Unhandled exception. System.NullReferenceException: Object reference not set to an instance of an object.
   at Program.<Main>$(String[] args) in /home/ana/cs/nulo.cs:line 3

Referência rápida

Exercícios

Missão final: a playlist de trás para a frente

4. Trem das Onze
3. Aquarela
2. Garota de Ipanema
1. Asa Branca

var playlist = new LinkedList<string>(["Asa Branca", "Garota de Ipanema", "Aquarela", "Trem das Onze"]);

int numero = 1;
for (var no = playlist.First; no is not null; no = no.Next)
{
    Console.WriteLine($"{numero}. {no.Value}");
    numero++;
}

var playlist = new LinkedList<string>(["Asa Branca", "Garota de Ipanema", "Aquarela", "Trem das Onze"]);

int numero = playlist.Count;
for (var no = playlist.Last; no is not null; no = no.Previous)
{
    Console.WriteLine($"{numero}. {no.Value}");
    numero--;
}

Resumo

• Uma LinkedList<T> guarda cada item num nó (LinkedListNode<T>) que conhece o vizinho de trás (Previous) e o da frente (Next).
• AddFirst e AddLast põem nas pontas; AddAfter e AddBefore encaixam ao lado de um nó; Find acha o nó de um valor (ou null).
• Não há [ ] (CS0021): ande pelos nós, para a frente ou para trás.
• First, Last e Find podem dar null: teste antes de usar .Value. RemoveFirst numa lista vazia dá The LinkedList is empty.
• Para remover durante o percurso, ande com while e guarde o Next antes do Remove; no foreach, mudar a lista dá InvalidOperationException.
• No dia a dia, prefira List<T>; a lista ligada vale a pena quando você encaixa e tira no meio o tempo todo.