← Home

Rainbow Lists

A linked list where every node keeps four shortcuts back down the list, so pushing stays O(1) and reaching the i-th item takes O(log i) hops. Pick an item and watch the seek find it. From the post Pure Lists with O(log(i)) Indexing

The path, hop by hop

    How the head got its pointers

    Push builds a node's pointers in O(1): each is a walk of at most three pointers older nodes already have. Hover a row to see its walk.

    Hops to every item of this list

    For each i (across), the hops the seek takes from the head. Click to pick an item.

    What each seek costs

    As the distance d grows (item i is d = i from the head): the hops followed, and the work done, counting arithmetic and any planning. Click a row to pick its seek.

    SeekHopsWorkWhy

    Click or tap a node to get it; hover one to see its pointers. Arrows move, Enter seeks. Colors as in the post: next, red (2k−1 back), green (2k back, the largest power of two dividing the index), blue (2k+1 back), yellow (for push, and for the greedy, planned and optimal seeks). Nodes count up from the tail, which is node 1, so item i is node n − i.