Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Logarithmic Cons-Pair Lists

Name: Anonymous 2014-05-26 3:13

What is the name of immutable data structure, which has O(1) access to the head element and logarithmic increasing access cost for the following elements?

It can be implemented by converting tail into an array, when prefix size becomes larger than the tail size. I.e. (cons prefix array)

Name: Anonymous 2014-05-26 7:31

>>13

(cons x xs) and (cdr xs) would still be O(log2(n))

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List