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.
| Seek | Hops | Work | Why |
|---|
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.