std.LinkedList — Lista Duplamente Encadeada
O std.DoublyLinkedList (acessível como std.DoublyLinkedList ou via std.SinglyLinkedList) é a implementação de lista encadeada da biblioteca padrão do Zig. Ela é intrusiva, significando que o nó da lista é embutido dentro da struct de dados do usuário, em vez de envolver os dados em um nó alocado separadamente. Isso evita alocações extras e melhora a localidade de cache.
Visão Geral
const std = @import("std");
const DoublyLinkedList = std.DoublyLinkedList;
const SinglyLinkedList = std.SinglyLinkedList;
Tipos Disponíveis
O Zig oferece duas variantes:
DoublyLinkedList(T)— Lista duplamente encadeada com ponteirosprevenextSinglyLinkedList(T)— Lista simplesmente encadeada com apenasnext
Tipo e Assinatura
pub fn DoublyLinkedList(comptime T: type) type
O tipo T é o tipo dos dados armazenados em cada nó. Cada nó (Node) contém data: T e ponteiros prev/next.
Funções Principais (DoublyLinkedList)
Estrutura do Nó
pub const Node = struct {
data: T,
prev: ?*Node = null,
next: ?*Node = null,
};
Operações da Lista
// Lista vazia (sem inicialização especial)
// var lista = DoublyLinkedList(T){};
// Insere no início
pub fn prepend(self: *Self, node: *Node) void
// Insere no final
pub fn append(self: *Self, node: *Node) void
// Insere após um nó existente
pub fn insertAfter(self: *Self, node: *Node, new_node: *Node) void
// Insere antes de um nó existente
pub fn insertBefore(self: *Self, node: *Node, new_node: *Node) void
// Remove um nó
pub fn remove(self: *Self, node: *Node) void
// Remove e retorna o primeiro
pub fn popFirst(self: *Self) ?*Node
// Remove e retorna o último
pub fn pop(self: *Self) ?*Node
// Campos de acesso
// self.first: ?*Node — primeiro nó
// self.last: ?*Node — último nó
// self.len: usize — número de nós
Exemplo 1: Fila FIFO com Lista Encadeada
const std = @import("std");
const Tarefa = struct {
descricao: []const u8,
prioridade: u8,
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const L = std.DoublyLinkedList(Tarefa);
var fila = L{};
// Aloca nós e insere tarefas
const tarefas = [_]Tarefa{
.{ .descricao = "Compilar projeto", .prioridade = 1 },
.{ .descricao = "Rodar testes", .prioridade = 2 },
.{ .descricao = "Fazer deploy", .prioridade = 3 },
};
var nos: [3]*L.Node = undefined;
for (tarefas, 0..) |tarefa, i| {
nos[i] = try allocator.create(L.Node);
nos[i].* = .{ .data = tarefa };
fila.append(nos[i]);
}
defer for (nos) |no| allocator.destroy(no);
const stdout = std.io.getStdOut().writer();
try stdout.print("Tarefas na fila: {d}\n", .{fila.len});
// Processa na ordem FIFO
try stdout.writeAll("Processando:\n");
while (fila.popFirst()) |no| {
try stdout.print(" [{d}] {s}\n", .{
no.data.prioridade,
no.data.descricao,
});
}
try stdout.print("Fila vazia: {}\n", .{fila.len == 0});
}
Exemplo 2: LRU Cache com Lista Duplamente Encadeada
const std = @import("std");
fn LRUCache(comptime V: type, comptime capacity: usize) type {
return struct {
const Self = @This();
const L = std.DoublyLinkedList(Entry);
const Entry = struct {
chave: []const u8,
valor: V,
};
lista: L,
mapa: std.StringHashMap(*L.Node),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.lista = L{},
.mapa = std.StringHashMap(*L.Node).init(allocator),
.allocator = allocator,
};
}
pub fn deinit(self: *Self) void {
while (self.lista.pop()) |no| {
self.allocator.destroy(no);
}
self.mapa.deinit();
}
pub fn get(self: *Self, chave: []const u8) ?V {
if (self.mapa.get(chave)) |no| {
// Move para o final (mais recente)
self.lista.remove(no);
self.lista.append(no);
return no.data.valor;
}
return null;
}
pub fn put(self: *Self, chave: []const u8, valor: V) !void {
if (self.mapa.get(chave)) |no| {
no.data.valor = valor;
self.lista.remove(no);
self.lista.append(no);
return;
}
// Evicta o mais antigo se cheio
if (self.lista.len >= capacity) {
if (self.lista.popFirst()) |antigo| {
_ = self.mapa.remove(antigo.data.chave);
self.allocator.destroy(antigo);
}
}
const no = try self.allocator.create(L.Node);
no.* = .{ .data = .{ .chave = chave, .valor = valor } };
self.lista.append(no);
try self.mapa.put(chave, no);
}
};
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var cache = LRUCache(i32, 3).init(allocator);
defer cache.deinit();
try cache.put("a", 1);
try cache.put("b", 2);
try cache.put("c", 3);
const stdout = std.io.getStdOut().writer();
if (cache.get("a")) |v| {
try stdout.print("a = {d}\n", .{v});
}
// Inserir "d" evicta "b" (o menos usado recentemente)
try cache.put("d", 4);
try stdout.print("b existe: {}\n", .{cache.get("b") != null}); // false
try stdout.print("d = {d}\n", .{cache.get("d").?}); // 4
}
Exemplo 3: SinglyLinkedList como Pilha
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const L = std.SinglyLinkedList(i32);
var pilha = L{};
// Push: insere no início
const valores = [_]i32{ 10, 20, 30, 40, 50 };
for (valores) |val| {
const no = try allocator.create(L.Node);
no.* = .{ .data = val };
pilha.prepend(no);
}
const stdout = std.io.getStdOut().writer();
try stdout.writeAll("Pop da pilha (LIFO):\n");
// Pop: remove do início
while (pilha.popFirst()) |no| {
try stdout.print(" {d}\n", .{no.data});
allocator.destroy(no);
}
// Saída: 50, 40, 30, 20, 10
}
Quando Usar LinkedList
- Inserções/remoções frequentes no meio: O(1) com ponteiro direto ao nó
- Ponteiros estáveis obrigatórios: Nós nunca são movidos
- Implementação de filas e deques: Operações eficientes nas duas pontas
- Quando NÃO usar: Acesso aleatório por índice, iteração sequencial simples (prefira
ArrayList)
Módulos Relacionados
- std.ArrayList — Array dinâmico contíguo
- std.SegmentedList — Lista segmentada com ponteiros estáveis
- std.PriorityQueue — Fila de prioridade
- std.mem.Allocator — Interface de alocação