Unrolled List, Bloom Filter, and Skip List: Concepts, Implementations, and Trade‑offs

Unrolled List

Linked lists are a fundamental data structure known for their recursive nature and dynamic memory allocation, which makes them suitable for variable‑length collections but can cause memory fragmentation and pointer‑chasing overhead. When the length is known, arrays offer contiguous memory and faster access.

The Unrolled List is a hybrid that stores a variable‑length array inside each node, reducing memory usage and improving efficiency while still supporting dynamic growth. It balances complexity (e.g., deciding how many items each node holds) with the benefits of both linked lists and arrays.

template < typename T >
struct UnrolledListNode{
    T* items;
    int items_length;
    UnrolledListNode* next;
};

Bloom Filter

The Bloom Filter, named after Burton Howard Bloom, is a probabilistic data structure that answers set‑membership queries with a controllable false‑positive rate, using far less memory than a conventional hash table.

Given a large dataset of keys, a Bloom Filter hashes each key with multiple hash functions and sets the corresponding bits in a bit array. To query a key, all its hash‑derived bits must be set; if any are clear, the key is definitely absent, otherwise it may be present with a known error probability.

Mathematically, for a set of n elements, a desired false‑positive probability p , the required bit array size m and number of hash functions k are determined by:

and

Implementations can use universal hash families as described in algorithm textbooks.

Skip List

A Skip List is a probabilistic alternative to balanced trees that augments a sorted linked list with multiple forward pointers, enabling faster search by “skipping” over sections of the list.

Each node contains an array of pointers to nodes at higher levels; the height of a node is chosen randomly during insertion. While searches are not guaranteed to be binary, they achieve logarithmic expected time with simpler implementation and space‑time trade‑offs.

template < typename T >
struct SkipListNode{
    SkipListNode** next; // dynamic allocate
    int length; // next array length and also node level
    T data;
};