On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Okasaki's book is a continued inspiration of data structures
and algorithms.
Start with a simple array of data. Then mentally decompose that
array into a concatenation of smaller arrays: first has size 1,
second has size 4, third has size 9, then 16, 25, 36, ...
Generally the size of these imaginary subarrays grows
quadratically. And they're adjacent to each other. The last
array may be incomplete.
........
Please share any thoughts!
Andrei
Interesting, but isn't that basically a skip list with uneven
sub-lists? insert could be quite complex unless the entire data
structure is backed by a continuous or a continuous linked list.