Lista Ligada

Conceito

Uma lista ligada é um conjunto de nós, cada um guardando um valor e um ponteiro para o próximo. Não há contiguidade — e é isso que troca todo o perfil de custos em relação ao 2. Array.

Sem contiguidade, não existe aritmética de índice: para chegar ao elemento i você precisa seguir i ponteiros. Acesso passa a ser O(n).

O que ela compra em troca:

• inserir e remover em O(1) — desde que você já tenha o nó em mãos. É só religar dois ponteiros; nada desloca.
• sem realocação e sem cópia quando cresce.
• referências a outros nós continuam válidas após inserção/remoção — no array dinâmico, uma realocação invalida todos os ponteiros para elementos.

A nuance que quase todo material erra: remover é O(1) se você tem o nó, O(n) se você precisa achá-lo. A busca é o custo real, não a remoção.

Simples vs duplamente ligada: a dupla guarda também o anterior, o que permite remover um nó tendo só ele (sem varrer para achar o predecessor) e percorrer ao contrário. Custa um ponteiro por nó.

A verdade desconfortável: na prática, array dinâmico ganha quase sempre. Cada nó é uma alocação separada, espalhada pelo heap, então percorrer uma lista ligada é uma sequência de cache misses. O ganho teórico em inserção raramente compensa.

Onde ela realmente é a escolha certa: quando você já tem o nó (cache LRU = mapa de chave → nó da lista), quando referências devem permanecer válidas, e quando não se pode realocar (alocadores, kernels — as intrusive lists).

Em Go

A stdlib tem container/list (duplamente ligada) e ela é raramente usada, por um motivo concreto: é pré-generics e guarda any, então todo valor sofre boxing e alocação, e você paga type assertion na leitura.

Hoje o caminho é escrever à mão com generics — são ~20 linhas e o tipo fica seguro:

type No[T any] struct {
	Val      T
	Prox     *No[T]
}

O custo em Go é especialmente visível porque cada &No[T]{...} é uma alocação no heap (2. Stack vs Heap). Mil elementos = mil alocações espalhadas + mil objetos para o GC rastrear. Um []T equivalente é uma alocação contígua.

Onde lista ligada aparece de verdade em Go:

• runtime interno (filas de goroutines, sync.Pool)
• cache LRU: map[K]*No[V] + lista dupla — o mapa dá o O(1) de busca, a lista dá o O(1) de mover para a frente. É a combinação que justifica a estrutura.

Respostas às perguntas-guia

1. O que a lista ligada compra em troca de perder o acesso por índice?

Conceito: inserção/remoção O(1) com o nó em mãos, ausência de realocação, e estabilidade de referências.

Em Go: a estabilidade de referências é o ganho mais concreto — append pode realocar e invalidar qualquer *T que você guardou apontando para dentro do slice.

2. Por que remover é O(1) se você já tem o nó — e O(n) se não tem?

Conceito: religar ponteiros é trabalho constante; achar o nó é o que custa travessia. O custo está na busca, não na remoção.

Em Go: é exatamente por isso que o LRU usa mapa junto com a lista: o mapa elimina a parte O(n).

3. Simplesmente vs duplamente ligada: o que a segunda resolve?

Conceito: remover um nó qualquer sem varrer para achar o anterior, e travessia reversa. Custa um ponteiro por nó.

Em Go: container/list é dupla justamente porque sem isso o Remove(e) em O(1) seria impossível.

4. Na prática, quando você realmente usaria uma em vez de um array?

Conceito: quando você já tem o nó, quando referências precisam sobreviver a mutações, ou quando realocar é proibido.

Em Go, na prática: cache LRU e listas intrusivas. Para "uma coleção de coisas", slice — sempre. A resposta honesta é que você vai implementar uma nesta semana para entender e provavelmente não vai usar de novo por anos.

Trade-offs

Do conceito:

• O(1) na inserção vs O(n) no acesso — é uma troca, não uma melhoria.
• Sem realocação vs uma alocação por elemento: você troca picos raros por custo constante espalhado.
• Referências estáveis é a vantagem mais subestimada e a menos citada.

Em Go:

• container/list custa boxing e type assertion; generics à mão custa 20 linhas e não custa nada em runtime.
• Cada nó é um objeto de heap → pressão de GC proporcional ao número de elementos.
• []T de 1000 itens: 1 alocação. Lista de 1000 itens: 1000 alocações.

Exemplo prático

Lista simplesmente ligada com generics, e o benchmark honesto contra slice:

package main

import "fmt"

type No[T any] struct {
	Val  T
	Prox *No[T]
}

type Lista[T any] struct {
	cabeca *No[T]
	tam    int
}

func (l *Lista[T]) InsereNaFrente(v T) {
	l.cabeca = &No[T]{Val: v, Prox: l.cabeca} // O(1)
	l.tam++
}

// O(1): só religa ponteiros — mas exige ter o ANTERIOR em mãos.
func (l *Lista[T]) RemoveDepois(anterior *No[T]) {
	if anterior == nil || anterior.Prox == nil {
		return
	}
	anterior.Prox = anterior.Prox.Prox
	l.tam--
}

// O(n): a travessia é o custo real
func (l *Lista[T]) Em(i int) *No[T] {
	n := l.cabeca
	for ; i > 0 && n != nil; i-- {
		n = n.Prox
	}
	return n
}

func (l *Lista[T]) Slice() []T {
	out := make([]T, 0, l.tam)
	for n := l.cabeca; n != nil; n = n.Prox {
		out = append(out, n.Val)
	}
	return out
}

func main() {
	var l Lista[int]
	for i := 3; i >= 1; i-- {
		l.InsereNaFrente(i)
	}
	fmt.Println(l.Slice(), "tam:", l.tam) // [1 2 3] tam: 3

	l.RemoveDepois(l.Em(0)) // remove o elemento 1 (índice 1)
	fmt.Println(l.Slice())  // [1 3]

	// a assimetria: acesso por índice é travessia
	fmt.Println("Em(1) =", l.Em(1).Val) // 3
}

Compare com o equivalente em slice: s = append([]int{v}, s...) para inserir na frente é O(n) — a lista ganha aqui. Mas s[i] é O(1), onde a lista é O(n). É a troca inteira, em duas linhas.

Relacionado

• 2. Array — o outro lado da troca
• 6. Hash Map — encadeamento separado é uma lista ligada por bucket
• 2. Stack vs Heap — semana 1, por que um nó por alocação pesa
• 6. Pilha de Chamadas — semana 3, a pilha do runtime é uma lista de frames

---

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação