---
title: "Skip List em Zig — Implementação Completa"
url: "https://ziglang.com.br/estruturas-dados/skip-list-em-zig-implementa%C3%A7%C3%A3o-completa/"
markdown_url: "https://ziglang.com.br/estruturas-dados/skip-list-em-zig-implementa%C3%A7%C3%A3o-completa.MD"
description: "Aprenda Skip List em Zig. Estrutura probabilística com busca, inserção e remoção em O(log n). Alternativa simples a árvores balanceadas."
date: "2026-02-21"
author: "Zig Brasil"
---

# Skip List em Zig — Implementação Completa

Aprenda Skip List em Zig. Estrutura probabilística com busca, inserção e remoção em O(log n). Alternativa simples a árvores balanceadas.


# Skip List em Zig — Implementação Completa

Uma **Skip List** é uma estrutura de dados probabilística que permite busca, inserção e remoção em O(log n) esperado. É uma alternativa elegante às árvores balanceadas (AVL, Red-Black) com implementação mais simples. A ideia é manter múltiplos níveis de listas encadeadas, onde níveis superiores funcionam como "atalhos" que pulam vários elementos.

## Conceito

```
Skip List com max_level=4:

Level 3:  HEAD ──────────────────── 50 ────────────────── NIL
Level 2:  HEAD ────── 20 ────────── 50 ────── 70 ──────── NIL
Level 1:  HEAD ── 10 ─ 20 ── 30 ── 50 ── 60 ─ 70 ── 90 ─ NIL
Level 0:  HEAD ── 10 ─ 20 ── 30 ── 40 ── 50 ── 60 ─ 70 ── 80 ── 90 ── NIL

Busca por 60:
  Level 3: HEAD → 50 (60 > 50, avança)  → NIL (60 < NIL, desce)
  Level 2: 50 → 70 (60 < 70, desce)
  Level 1: 50 → 60 ✓ Encontrado!

Cada nó é promovido ao próximo nível com probabilidade p (geralmente 0.5).
```

## Implementação em Zig

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

/// Skip List genérica com nível máximo configurável.
pub fn SkipList(comptime T: type, comptime max_level: u8) type {
    return struct {
        const Self = @This();

        const No = struct {
            valor: T,
            proximos: [max_level]?*No,
            nivel: u8,
        };

        head: No,
        nivel_atual: u8,
        tamanho: usize,
        allocator: Allocator,
        prng: std.Random.DefaultPrng,

        pub fn init(allocator: Allocator) Self {
            var head = No{
                .valor = undefined,
                .proximos = [_]?*No{null} ** max_level,
                .nivel = max_level - 1,
            };
            _ = &head;
            return .{
                .head = head,
                .nivel_atual = 0,
                .tamanho = 0,
                .allocator = allocator,
                .prng = std.Random.DefaultPrng.init(@intCast(std.time.milliTimestamp())),
            };
        }

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

        fn nivelAleatorio(self: *Self) u8 {
            var nivel: u8 = 0;
            const random = self.prng.random();
            while (nivel < max_level - 1 and random.boolean()) {
                nivel += 1;
            }
            return nivel;
        }

        fn comparar(a: T, b: T) std.math.Order {
            if (T == []const u8) {
                return std.mem.order(u8, a, b);
            }
            return std.math.order(a, b);
        }

        /// Insere um valor — O(log n) esperado.
        pub fn inserir(self: *Self, valor: T) !bool {
            var atualizar: [max_level]?*No = [_]?*No{null} ** max_level;
            var atual: *No = &self.head;

            // Desce pelos níveis encontrando posição
            var nivel: i16 = @intCast(self.nivel_atual);
            while (nivel >= 0) : (nivel -= 1) {
                const n: usize = @intCast(nivel);
                while (atual.proximos[n]) |prox| {
                    if (comparar(prox.valor, valor) == .lt) {
                        atual = prox;
                    } else break;
                }
                atualizar[n] = atual;
            }

            // Verifica se já existe
            if (atual.proximos[0]) |prox| {
                if (comparar(prox.valor, valor) == .eq) return false;
            }

            // Determina nível do novo nó
            const novo_nivel = self.nivelAleatorio();
            if (novo_nivel > self.nivel_atual) {
                var n: u8 = self.nivel_atual + 1;
                while (n <= novo_nivel) : (n += 1) {
                    atualizar[n] = &self.head;
                }
                self.nivel_atual = novo_nivel;
            }

            // Cria novo nó
            const novo = try self.allocator.create(No);
            novo.* = .{
                .valor = valor,
                .proximos = [_]?*No{null} ** max_level,
                .nivel = novo_nivel,
            };

            // Insere nos níveis
            var n: usize = 0;
            while (n <= novo_nivel) : (n += 1) {
                if (atualizar[n]) |at| {
                    novo.proximos[n] = at.proximos[n];
                    at.proximos[n] = novo;
                }
            }

            self.tamanho += 1;
            return true;
        }

        /// Busca um valor — O(log n) esperado.
        pub fn buscar(self: *Self, valor: T) bool {
            var atual: *No = &self.head;

            var nivel: i16 = @intCast(self.nivel_atual);
            while (nivel >= 0) : (nivel -= 1) {
                const n: usize = @intCast(nivel);
                while (atual.proximos[n]) |prox| {
                    const cmp = comparar(prox.valor, valor);
                    if (cmp == .lt) {
                        atual = prox;
                    } else if (cmp == .eq) {
                        return true;
                    } else break;
                }
            }
            return false;
        }

        /// Remove um valor — O(log n) esperado.
        pub fn remover(self: *Self, valor: T) bool {
            var atualizar: [max_level]?*No = [_]?*No{null} ** max_level;
            var atual: *No = &self.head;

            var nivel: i16 = @intCast(self.nivel_atual);
            while (nivel >= 0) : (nivel -= 1) {
                const n: usize = @intCast(nivel);
                while (atual.proximos[n]) |prox| {
                    if (comparar(prox.valor, valor) == .lt) {
                        atual = prox;
                    } else break;
                }
                atualizar[n] = atual;
            }

            if (atual.proximos[0]) |alvo| {
                if (comparar(alvo.valor, valor) != .eq) return false;

                var n: usize = 0;
                while (n <= self.nivel_atual) : (n += 1) {
                    if (atualizar[n]) |at| {
                        if (at.proximos[n] == alvo) {
                            at.proximos[n] = alvo.proximos[n];
                        }
                    }
                }

                self.allocator.destroy(alvo);
                self.tamanho -= 1;

                // Reduz nível se necessário
                while (self.nivel_atual > 0 and self.head.proximos[self.nivel_atual] == null) {
                    self.nivel_atual -= 1;
                }
                return true;
            }
            return false;
        }

        /// Imprime a estrutura visual da skip list.
        pub fn imprimir(self: *Self, writer: anytype) !void {
            var nivel: i16 = @intCast(self.nivel_atual);
            while (nivel >= 0) : (nivel -= 1) {
                try writer.print("Level {d}: HEAD", .{nivel});
                const n: usize = @intCast(nivel);
                var atual = self.head.proximos[n];
                while (atual) |no| {
                    try writer.print(" → {}", .{no.valor});
                    atual = no.proximos[n];
                }
                try writer.writeAll(" → NIL\n");
            }
        }
    };
}

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

    var lista = SkipList(i32, 8).init(allocator);
    defer lista.deinit();

    // Insere valores
    const valores = [_]i32{ 50, 30, 70, 10, 40, 60, 80, 20, 90 };
    try stdout.writeAll("=== Inserindo valores ===\n");
    for (valores) |v| {
        _ = try lista.inserir(v);
    }

    // Imprime estrutura
    try stdout.writeAll("\n=== Estrutura da Skip List ===\n");
    try lista.imprimir(stdout);

    // Buscas
    try stdout.writeAll("\n=== Buscas ===\n");
    const testes = [_]i32{ 30, 45, 80, 100 };
    for (testes) |v| {
        try stdout.print("  Buscar {d}: {}\n", .{ v, lista.buscar(v) });
    }

    // Remoção
    try stdout.writeAll("\n=== Remoção ===\n");
    _ = lista.remover(50);
    _ = lista.remover(10);
    try stdout.print("Após remover 50 e 10 (tamanho={d}):\n", .{lista.tamanho});
    try lista.imprimir(stdout);
}
```

## Análise de Complexidade

| Operação | Esperado | Pior |
|----------|----------|------|
| **Busca** | O(log n) | O(n) |
| **Inserção** | O(log n) | O(n) |
| **Remoção** | O(log n) | O(n) |
| **Espaço** | O(n) | O(n log n) |

## Comparação com Árvores Balanceadas

| Aspecto | Skip List | AVL / Red-Black Tree |
|---------|-----------|---------------------|
| Complexidade média | O(log n) | O(log n) |
| Pior caso | O(n) probabilístico | O(log n) garantido |
| Implementação | Mais simples | Mais complexa |
| Cache-friendly | Razoável | Ruim |
| Concorrência | Fácil de paralelizar | Difícil |

## Recursos Relacionados

- [Árvore de Busca Binária](/estruturas-dados/arvore-busca-binaria/) — BST simples
- [AVL Tree](/estruturas-dados/avl-tree/) — Árvore balanceada determinística
- [Red-Black Tree](/estruturas-dados/red-black-tree/) — Árvore rubro-negra
- [Lista Encadeada](/estruturas-dados/lista-encadeada/) — Base conceitual