null ← head                              tail → null
        ↓                                  ↓
  +------+---+    +---+---+---+    +---+---+------+
  | null | 5 | ●→ | ● | 8 | ●→ | ● | 3 | null  |
  |      |   | ←● |   |   | ←● |   |   |       |
  +------+---+    +---+---+---+    +---+---+------+

Inserção entre 5 e 8:
  1. Cria nó 7
  2. 7.proximo = 8, 7.anterior = 5
  3. 5.proximo = 7, 8.anterior = 7

         5 ←→ 7 ←→ 8 ←→ 3

Remoção do nó 8:
  1. 7.proximo = 3
  2. 3.anterior = 7
  3. Libera nó 8

         5 ←→ 7 ←→ 3

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

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

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

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

        pub fn init(allocator: Allocator) Self {
            return .{
                .head = null,
                .tail = null,
                .tamanho = 0,
                .allocator = allocator,
            };
        }

        pub fn deinit(self: *Self) void {
            var atual = self.head;
            while (atual) |no| {
                const prox = no.proximo;
                self.allocator.destroy(no);
                atual = prox;
            }
        }

        /// 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, .anterior = null };

            if (self.head) |head| {
                head.anterior = novo;
            } else {
                self.tail = novo;
            }
            self.head = novo;
            self.tamanho += 1;
        }

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

            if (self.tail) |tail| {
                tail.proximo = novo;
            } else {
                self.head = novo;
            }
            self.tail = novo;
            self.tamanho += 1;
        }

        /// Remove um nó específico — O(1).
        pub fn removerNo(self: *Self, no: *No) T {
            const valor = no.valor;

            if (no.anterior) |ant| {
                ant.proximo = no.proximo;
            } else {
                self.head = no.proximo;
            }

            if (no.proximo) |prox| {
                prox.anterior = no.anterior;
            } else {
                self.tail = no.anterior;
            }

            self.allocator.destroy(no);
            self.tamanho -= 1;
            return valor;
        }

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

        /// Remove do final — O(1).
        pub fn removerFinal(self: *Self) ?T {
            const tail = self.tail orelse return null;
            return self.removerNo(tail);
        }

        /// Busca por valor, retorna o nó — O(n).
        pub fn buscarNo(self: *Self, valor: T) ?*No {
            var atual = self.head;
            while (atual) |no| {
                if (no.valor == valor) return no;
                atual = no.proximo;
            }
            return null;
        }

        /// Move um nó para o início — O(1).
        pub fn moverParaInicio(self: *Self, no: *No) void {
            if (no == self.head) return;

            // Remove das posições atuais
            if (no.anterior) |ant| ant.proximo = no.proximo;
            if (no.proximo) |prox| prox.anterior = no.anterior;
            if (no == self.tail) self.tail = no.anterior;

            // Coloca no início
            no.proximo = self.head;
            no.anterior = null;
            if (self.head) |head| head.anterior = no;
            self.head = no;
        }

        /// Itera do início ao fim.
        pub fn iterarFrente(self: *const Self) Iterator {
            return .{ .atual = self.head };
        }

        /// Itera do fim ao início.
        pub fn iterarTras(self: *const Self) IteratorReverso {
            return .{ .atual = self.tail };
        }

        pub const Iterator = struct {
            atual: ?*No,

            pub fn next(self: *Iterator) ?T {
                const no = self.atual orelse return null;
                self.atual = no.proximo;
                return no.valor;
            }
        };

        pub const IteratorReverso = struct {
            atual: ?*No,

            pub fn next(self: *IteratorReverso) ?T {
                const no = self.atual orelse return null;
                self.atual = no.anterior;
                return no.valor;
            }
        };
    };
}

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

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

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

    // Iteração para frente
    try stdout.print("Frente: ", .{});
    var it = lista.iterarFrente();
    while (it.next()) |v| try stdout.print("{d} ↔ ", .{v});
    try stdout.print("null\n", .{});

    // Iteração para trás
    try stdout.print("Trás:   ", .{});
    var rit = lista.iterarTras();
    while (rit.next()) |v| try stdout.print("{d} ↔ ", .{v});
    try stdout.print("null\n", .{});

    // Remover do final
    if (lista.removerFinal()) |v| {
        try stdout.print("Removido do final: {d}\n", .{v});
    }

    // Buscar e mover para início
    if (lista.buscarNo(20)) |no| {
        lista.moverParaInicio(no);
        try stdout.print("Após mover 20 para início: ", .{});
        var it2 = lista.iterarFrente();
        while (it2.next()) |v| try stdout.print("{d} ", .{v});
        try stdout.print("\n", .{});
    }

    try stdout.print("Tamanho: {d}\n", .{lista.tamanho});
}