Re: "Reverse Doubling List", is there another name?

cdiggins@xxxxxxxxxxxx writes:

> I am using a abstract data type, which is a linked list of arrays, each
> one twice as big as the next. Does anyone know if this data-type
> pre-exists under a different name than "reverse doubling list"?

I haven't heard this name. Why "reverse"? I don't recall any
specific short name, actually.

> I've discovered that this data type has the property O(1) growth in the
> average and worst case, and the property of O(1) indexing in the
> average case and O(LogN) in the worst case. Is this a noteworthy
> observation, or is it common knowledge amongst theoretical computer
> scientists?

This is common knowledge, and the technique is used quite often.

Torben
.

Relevant Pages

  • "Reverse Doubling List", is there another name?
    ... I am using a abstract data type, which is a linked list of arrays, each ... one twice as big as the next. ...
    (comp.theory)
  • Re: Fortran Forum - Oh Boy
    ... At times is seems to be trying to be a bit string. ... > suggest it's an unsigned integer feature. ... > that aren't consistent with it being a data type. ... > function COUNT applied to arrays of bits. ...
    (comp.lang.fortran)
  • Re: The linf project (2)
    ... exactly two types - statically sized (known at compile time) and ... for local arrays in a procedure. ... to strings, except I am a little confused what a string ought to be. ... each data type comes in exactly one kind and anything else has to be ...
    (comp.lang.fortran)
  • "Type" statement and arrays
    ... I am having difficulty getting a user defined data type to function ... comprised of four 1-D arrays. ... Public Type PlotScalars ... I get an error "Compile error: ...
    (microsoft.public.excel.programming)
  • Re: Howto read line from a stream
    ... Let alone representations ... abstract data type. ... of ints, additive because, composed of ints, etc). ... common knowledge is used to implement protocols, ...
    (comp.lang.ada)