skip lists

Geoff Canyon gcanyon at gmail.com
Sun May 12 16:26:42 EDT 2013


On Sat, May 11, 2013 at 5:20 PM, Richard Gaskin
<ambassador at fourthworld.com>wrote:

> Geoff Canyon wrote:
>
> > I'm curious why you'd want to do this?
>
> Because I'm a madman. :)


A perfectly fine reason, I've done many things for the same reason. In this
instance, just to make sure there's nothing I'm overlooking, as far as I
can see:

In non-high-level languages:
Linked lists, are compact and easy to write to. They don't have to allocate
all storage space up front the way arrays do. They're slow to find elements
in, which skip lists help to address.

In LC:
Arrays allocate memory below the level we look at, as do all other storage
forms. Any implementation of a linked list that I can think of would
probably be slower than simply writing to an array. The only thing that
comes to mind that *might* be faster to write to would be some sort of
two-variable solution where one variable contained the data, and new
additions involved simply appending to the end of the (increasingly long)
string, along with a second variable that, in some efficient way, keeps
track of what is where in the first variable, which sounds horrible.

Am I overlooking anything?

gc



More information about the use-livecode mailing list