head
  ↓
+---+---+    +---+---+    +---+---+    +---+------+
| 5 | ●-+--->| 8 | ●-+--->| 3 | ●-+--->| 1 | null |
+---+---+    +---+---+    +---+---+    +---+------+

Inserção no início (O(1)):
  novo
   ↓
  +---+---+    +---+---+    +---+---+
  | 9 | ●-+--->| 5 | ●-+--->| 8 | ...
  +---+---+    +---+---+    +---+---+
  ↑
 head (atualizado)

Remoção do nó com valor 8:
  +---+---+    +---+---+    +---+---+
  | 5 | ●-+--X-| 8 | ●-+--->| 3 | ...
  +---+---+  ↓ +---+---+    +---+---+
             +---------------↑
             (5 aponta para 3, 8 é liberado)

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Lista encadeada simples genérica.
pub fn ListaEncadeada(comptime T: type) type {
    return struct {
        const Self = @This();

        pub const No = struct {
            valor: T,
            proximo: ?*No,
        };

        head: ?*No,
        tamanho: usize,
        allocator: Allocator,

        /// Cria uma nova lista vazia.
        pub fn init(allocator: Allocator) Self {
            return .{
                .head = null,
                .tamanho = 0,
                .allocator = allocator,
            };
        }

        /// Libera todos os nós.
        pub fn deinit(self: *Self) void {
            var atual = self.head;
            while (atual) |no| {
                const prox = no.proximo;
                self.allocator.destroy(no);
                atual = prox;
            }
            self.head = null;
            self.tamanho = 0;
        }

        /// Insere no início — O(1).
        pub fn inserirInicio(self: *Self, valor: T) !void {
            const novo = try self.allocator.create(No);
            novo.* = .{ .valor = valor, .proximo = self.head };
            self.head = novo;
            self.tamanho += 1;
        }

        /// Insere no final — O(n).
        pub fn inserirFinal(self: *Self, valor: T) !void {
            const novo = try self.allocator.create(No);
            novo.* = .{ .valor = valor, .proximo = null };

            if (self.head == null) {
                self.head = novo;
            } else {
                var atual = self.head.?;
                while (atual.proximo) |prox| {
                    atual = prox;
                }
                atual.proximo = novo;
            }
            self.tamanho += 1;
        }

        /// Insere em posição específica — O(n).
        pub fn inserirEm(self: *Self, indice: usize, valor: T) !void {
            if (indice == 0) return self.inserirInicio(valor);
            if (indice > self.tamanho) return error.IndiceInvalido;

            var atual = self.head.?;
            for (0..indice - 1) |_| {
                atual = atual.proximo.?;
            }

            const novo = try self.allocator.create(No);
            novo.* = .{ .valor = valor, .proximo = atual.proximo };
            atual.proximo = novo;
            self.tamanho += 1;
        }

        /// Remove do início — O(1).
        pub fn removerInicio(self: *Self) ?T {
            const head = self.head orelse return null;
            const valor = head.valor;
            self.head = head.proximo;
            self.allocator.destroy(head);
            self.tamanho -= 1;
            return valor;
        }

        /// Remove por valor (primeira ocorrência) — O(n).
        pub fn removerValor(self: *Self, valor: T) bool {
            if (self.head == null) return false;

            if (self.head.?.valor == valor) {
                _ = self.removerInicio();
                return true;
            }

            var atual = self.head.?;
            while (atual.proximo) |prox| {
                if (prox.valor == valor) {
                    atual.proximo = prox.proximo;
                    self.allocator.destroy(prox);
                    self.tamanho -= 1;
                    return true;
                }
                atual = prox;
            }
            return false;
        }

        /// Busca por valor — O(n).
        pub fn buscar(self: *const Self, valor: T) bool {
            var atual = self.head;
            while (atual) |no| {
                if (no.valor == valor) return true;
                atual = no.proximo;
            }
            return false;
        }

        /// Acessa por índice — O(n).
        pub fn get(self: *const Self, indice: usize) ?T {
            if (indice >= self.tamanho) return null;
            var atual = self.head;
            for (0..indice) |_| {
                atual = atual.?.proximo;
            }
            return atual.?.valor;
        }

        /// Inverte a lista in-place — O(n).
        pub fn inverter(self: *Self) void {
            var anterior: ?*No = null;
            var atual = self.head;
            while (atual) |no| {
                const prox = no.proximo;
                no.proximo = anterior;
                anterior = no;
                atual = prox;
            }
            self.head = anterior;
        }

        /// Converte para slice (aloca memória).
        pub fn paraSlice(self: *const Self, allocator: Allocator) ![]T {
            var resultado = try allocator.alloc(T, self.tamanho);
            var atual = self.head;
            var i: usize = 0;
            while (atual) |no| {
                resultado[i] = no.valor;
                i += 1;
                atual = no.proximo;
            }
            return resultado;
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var lista = ListaEncadeada(i32).init(allocator);
    defer lista.deinit();

    // Inserções
    try lista.inserirFinal(10);
    try lista.inserirFinal(20);
    try lista.inserirFinal(30);
    try lista.inserirInicio(5);
    try lista.inserirEm(2, 15);

    // Exibe
    try stdout.print("Lista: ", .{});
    const items = try lista.paraSlice(allocator);
    defer allocator.free(items);
    for (items) |v| try stdout.print("{d} → ", .{v});
    try stdout.print("null (tamanho={d})\n", .{lista.tamanho});

    // Busca
    try stdout.print("Contém 15? {}\n", .{lista.buscar(15)});
    try stdout.print("Elemento no índice 2: {?d}\n", .{lista.get(2)});

    // Remoção
    _ = lista.removerValor(15);
    _ = lista.removerInicio();
    try stdout.print("Após remover 15 e início: ", .{});
    var atual = lista.head;
    while (atual) |no| {
        try stdout.print("{d} → ", .{no.valor});
        atual = no.proximo;
    }
    try stdout.print("null\n", .{});

    // Inversão
    lista.inverter();
    try stdout.print("Invertida: ", .{});
    atual = lista.head;
    while (atual) |no| {
        try stdout.print("{d} → ", .{no.valor});
        atual = no.proximo;
    }
    try stdout.print("null\n", .{});
}