Introdução
Uma lista ligada é uma estrutura de dados onde cada elemento (nó) contém um valor e um ponteiro para o próximo nó. Diferente de arrays, listas ligadas permitem inserção e remoção em O(1) em qualquer posição, sem necessidade de deslocar elementos. Zig oferece std.SinglyLinkedList e std.DoublyLinkedList na biblioteca padrão.
Nesta receita, você aprenderá a usar ambas as implementações.
Pré-requisitos
- Zig instalado (versão 0.13+). Veja o guia de instalação
- Conhecimento básico de Zig. Consulte a introdução ao Zig
Lista Simplesmente Ligada (SinglyLinkedList)
Cada nó aponta apenas para o próximo:
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Definir tipo do nó
const L = std.SinglyLinkedList(i32);
// Criar nós
var node1 = try allocator.create(L.Node);
defer allocator.destroy(node1);
node1.* = .{ .data = 10, .next = null };
var node2 = try allocator.create(L.Node);
defer allocator.destroy(node2);
node2.* = .{ .data = 20, .next = null };
var node3 = try allocator.create(L.Node);
defer allocator.destroy(node3);
node3.* = .{ .data = 30, .next = null };
// Montar lista
var lista = L{};
lista.prepend(node3); // 30
lista.prepend(node2); // 20 -> 30
lista.prepend(node1); // 10 -> 20 -> 30
// Iterar
std.debug.print("Lista: ", .{});
var it = lista.first;
while (it) |node| {
std.debug.print("{d} -> ", .{node.data});
it = node.next;
}
std.debug.print("null\n", .{});
// Contar elementos
std.debug.print("Tamanho: {d}\n", .{lista.len()});
// Remover primeiro
const removido = lista.popFirst();
if (removido) |node| {
std.debug.print("Removido: {d}\n", .{node.data});
}
}
Saída esperada
Lista: 10 -> 20 -> 30 -> null
Tamanho: 3
Removido: 10
Lista Duplamente Ligada (DoublyLinkedList)
Cada nó aponta para o próximo e para o anterior, permitindo navegação bidirecional:
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const L = std.DoublyLinkedList([]const u8);
// Função auxiliar para criar nós
var nodes: [5]*L.Node = undefined;
const nomes = [_][]const u8{ "Alice", "Bob", "Carlos", "Diana", "Eva" };
for (nomes, 0..) |nome, i| {
nodes[i] = try allocator.create(L.Node);
nodes[i].* = .{ .data = nome, .next = null, .prev = null };
}
defer for (&nodes) |node| allocator.destroy(node);
var lista = L{};
for (&nodes) |node| {
lista.append(node);
}
// Iterar para frente
std.debug.print("Frente: ", .{});
var it = lista.first;
while (it) |node| {
std.debug.print("{s} ", .{node.data});
it = node.next;
}
std.debug.print("\n", .{});
// Iterar para trás
std.debug.print("Trás: ", .{});
var rit = lista.last;
while (rit) |node| {
std.debug.print("{s} ", .{node.data});
rit = node.prev;
}
std.debug.print("\n", .{});
std.debug.print("Tamanho: {d}\n", .{lista.len});
// Remover um nó do meio
lista.remove(nodes[2]); // Remove "Carlos"
allocator.destroy(nodes[2]);
std.debug.print("Após remover Carlos: ", .{});
it = lista.first;
while (it) |node| {
std.debug.print("{s} ", .{node.data});
it = node.next;
}
std.debug.print("\n", .{});
}
Exemplo Prático: Lista de Tarefas com Prioridade
const std = @import("std");
const Tarefa = struct {
descricao: []const u8,
prioridade: enum { alta, media, baixa },
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const L = std.DoublyLinkedList(Tarefa);
var lista = L{};
// Helper para criar e adicionar
const tarefas_data = [_]Tarefa{
.{ .descricao = "Corrigir bug crítico", .prioridade = .alta },
.{ .descricao = "Escrever documentação", .prioridade = .baixa },
.{ .descricao = "Revisar pull request", .prioridade = .media },
.{ .descricao = "Atualizar dependências", .prioridade = .media },
.{ .descricao = "Deploy para produção", .prioridade = .alta },
};
var nodes: [tarefas_data.len]*L.Node = undefined;
for (tarefas_data, 0..) |tarefa, i| {
nodes[i] = try allocator.create(L.Node);
nodes[i].* = .{ .data = tarefa, .next = null, .prev = null };
lista.append(nodes[i]);
}
defer for (&nodes) |node| allocator.destroy(node);
// Listar por prioridade
const prioridades = [_]@TypeOf(Tarefa.prioridade){ .alta, .media, .baixa };
const nomes_prio = [_][]const u8{ "ALTA", "MEDIA", "BAIXA" };
for (prioridades, 0..) |prio, pi| {
std.debug.print("\n[{s}]\n", .{nomes_prio[pi]});
var it = lista.first;
while (it) |node| {
if (node.data.prioridade == prio) {
std.debug.print(" - {s}\n", .{node.data.descricao});
}
it = node.next;
}
}
}
Saída esperada
[ALTA]
- Corrigir bug crítico
- Deploy para produção
[MEDIA]
- Revisar pull request
- Atualizar dependências
[BAIXA]
- Escrever documentação
Quando Usar Listas Ligadas vs. ArrayList
| Operação | Lista Ligada | ArrayList |
|---|---|---|
| Inserir no início | O(1) | O(n) |
| Inserir no fim | O(1) com tail | O(1) amortizado |
| Remover do meio | O(1) com referência | O(n) |
| Acesso por índice | O(n) | O(1) |
| Uso de memória | Maior (ponteiros) | Menor (contíguo) |
| Cache-friendly | Não | Sim |
Dicas e Boas Práticas
Prefira ArrayList na maioria dos casos: Acesso sequencial é mais eficiente com memória contígua. Use listas ligadas quando inserção/remoção no meio é frequente.
Gerencie a memória dos nós: Cada nó é alocado individualmente. Use
defer allocator.destroy(node)ou um ArenaAllocator para simplificar.DoublyLinkedList é mais versátil: Permite remoção em O(1) e iteração bidirecional.
Use ArenaAllocator para muitos nós: Simplifica a liberação de memória quando todos os nós têm o mesmo tempo de vida.
Receitas Relacionadas
- Arrays Dinâmicos com ArrayList - Alternativa principal
- Implementação de Fila (Queue) - Filas com listas
- Usando ArenaAllocator - Simplificar alocação de nós
- Implementação de Pilha (Stack) - Pilhas