Skip List – probabilistic data structure O(log n), PHP implementation

Skip List is a probabilistic data structure invented by William Pugh in 1990. It combines the simplicity of a singly linked list with the performance of a binary tree – search, insert and delete operations run in O(log n) on average, without the need for balancing like AVL or Red-Black Trees. Rarely used in PHP, but it illustrates perfectly how randomness can replace complex balancing algorithms.

The idea – multiple levels of pointers

A regular singly linked list is O(n) for search – you have to traverse every element. Skip List adds “express lanes” – additional pointers that skip over many elements. The higher the level, the less frequently elements appear (randomly, with probability 0.5).

Level 3: 1 --------> 50 -----------------> 100
Level 2: 1 --> 20 -> 50 --> 70 ----------> 100
Level 1: 1 --> 20 -> 50 --> 70 --> 85 --> 100
Level 0: 1 -> 10 -> 20 -> 30 -> 50 -> 70 -> 85 -> 90 -> 100

Searching for 70:
- Start level 3: 1, next 50 < 70, continue. Next 100 > 70, drop level.
- Level 2: 50, next 70 = found!
- Instead of 8 steps (list) - 4 steps.

Implementation in PHP

<?php

declare(strict_types=1);

class SkipListNode
{
    /** @var SkipListNode[] */
    public array $next;

    public function __construct(
        public readonly int|float|null $key,
        public mixed $value,
        int $levels
    ) {
        $this->next = array_fill(0, $levels, null);
    }
}

class SkipList
{
    private SkipListNode $head;
    private int $currentMaxLevel = 1;
    private int $size = 0;

    private const MAX_LEVELS  = 16;
    private const PROBABILITY = 0.5;

    public function __construct()
    {
        $this->head = new SkipListNode(null, null, self::MAX_LEVELS);
    }

    private function randomLevel(): int
    {
        $level = 1;
        while ($level < self::MAX_LEVELS && (mt_rand() / mt_getrandmax()) < self::PROBABILITY) {
            $level++;
        }
        return $level;
    }

    public function insert(int|float $key, mixed $value): void
    {
        $update  = array_fill(0, self::MAX_LEVELS, null);
        $current = $this->head;

        for ($i = $this->currentMaxLevel - 1; $i >= 0; $i--) {
            while ($current->next[$i] !== null && $current->next[$i]->key < $key) {
                $current = $current->next[$i];
            }
            $update[$i] = $current;
        }

        $current = $current->next[0];
        if ($current !== null && $current->key === $key) {
            $current->value = $value;
            return;
        }

        $newLevel = $this->randomLevel();
        if ($newLevel > $this->currentMaxLevel) {
            for ($i = $this->currentMaxLevel; $i < $newLevel; $i++) {
                $update[$i] = $this->head;
            }
            $this->currentMaxLevel = $newLevel;
        }

        $newNode = new SkipListNode($key, $value, $newLevel);
        for ($i = 0; $i < $newLevel; $i++) {
            $newNode->next[$i]    = $update[$i]->next[$i];
            $update[$i]->next[$i] = $newNode;
        }

        $this->size++;
    }

    public function search(int|float $key): mixed
    {
        $current = $this->head;

        for ($i = $this->currentMaxLevel - 1; $i >= 0; $i--) {
            while ($current->next[$i] !== null && $current->next[$i]->key < $key) {
                $current = $current->next[$i];
            }
        }

        $current = $current->next[0];
        return ($current !== null && $current->key === $key) ? $current->value : null;
    }

    public function delete(int|float $key): bool
    {
        $update  = array_fill(0, self::MAX_LEVELS, null);
        $current = $this->head;

        for ($i = $this->currentMaxLevel - 1; $i >= 0; $i--) {
            while ($current->next[$i] !== null && $current->next[$i]->key < $key) {
                $current = $current->next[$i];
            }
            $update[$i] = $current;
        }

        $current = $current->next[0];
        if ($current === null || $current->key !== $key) {
            return false;
        }

        for ($i = 0; $i < $this->currentMaxLevel; $i++) {
            if ($update[$i]->next[$i] !== $current) break;
            $update[$i]->next[$i] = $current->next[$i];
        }

        $this->size--;
        return true;
    }

    public function range(int|float $min, int|float $max): array
    {
        $result  = [];
        $current = $this->head;

        for ($i = $this->currentMaxLevel - 1; $i >= 0; $i--) {
            while ($current->next[$i] !== null && $current->next[$i]->key < $min) {
                $current = $current->next[$i];
            }
        }

        $current = $current->next[0];
        while ($current !== null && $current->key <= $max) {
            $result[$current->key] = $current->value;
            $current = $current->next[0];
        }

        return $result;
    }

    public function count(): int { return $this->size; }
}

Practical application – product price index

<?php

$priceIndex = new SkipList();

$products = [
    ['id' => 1, 'name' => 'Widget S',   'price' => 9.99],
    ['id' => 2, 'name' => 'Widget M',   'price' => 29.99],
    ['id' => 3, 'name' => 'Widget L',   'price' => 49.99],
    ['id' => 4, 'name' => 'Gadget Pro', 'price' => 99.99],
    ['id' => 5, 'name' => 'Gadget Max', 'price' => 149.99],
];

foreach ($products as $product) {
    $priceIndex->insert($product['price'], $product);
}

// Range query O(log n + k) where k = number of results
$inRange = $priceIndex->range(20.0, 100.0);
// Returns: Widget M (29.99), Widget L (49.99), Gadget Pro (99.99)

foreach ($inRange as $price => $product) {
    echo "{$product['name']}: {$price} PLN\n";
}

Benchmark: Skip List vs array_filter

<?php

$n        = 100_000;
$skipList = new SkipList();
$array    = [];

for ($i = 0; $i < $n; $i++) {
    $price = mt_rand(1, 100000) / 100;
    $skipList->insert($price, "product_{$i}");
    $array[] = ['price' => $price, 'id' => $i];
}

$min = 50.0; $max = 100.0;

$start = microtime(true);
for ($q = 0; $q < 1000; $q++) {
    $result = $skipList->range($min, $max);
}
$skipTime = (microtime(true) - $start) * 1000;

$start = microtime(true);
for ($q = 0; $q < 1000; $q++) {
    $result = array_filter($array, fn($p) => $p['price'] >= $min && $p['price'] <= $max);
}
$arrayTime = (microtime(true) - $start) * 1000;

echo "Skip List range: {$skipTime}ms\n";  // ~45ms
echo "array_filter:    {$arrayTime}ms\n"; // ~890ms - ~20x slower

Comparison with tree structures

Skip List vs Hash Map: Hash Map is faster for exact lookups, but does not support range queries. Skip List fills that niche - O(log n) for a range instead of O(n) for iterating a hash map.

Summary

Skip List is an elegant example of how randomness can replace complex balancing algorithms. The implementation is many times simpler than AVL or Red-Black Trees with comparable computational complexity. In PHP it is most useful for range queries on large in-memory datasets - filtering products by price, searching by date, indexing by any numeric key. Redis uses Skip List internally in Sorted Sets - which confirms the practical value of this structure. Next post: Flyweight pattern - object sharing and instance caching.