"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. Does anyone know if this data-type
pre-exists under a different name than "reverse doubling list"?

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?

If anyone wants more information, I have published an implementation
in C++, along with a brief analysis of the complexity at
http://www.codeproject.com/useritems/fast-stack.asp

Thanks
Christopher Diggins
http://www.cdiggins.com

.

Relevant Pages

  • Re: "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. ... This is common knowledge, and the technique is used quite often. ...
    (comp.theory)
  • Re: Lisp collections
    ... Obviously, in my sentence above, "lists" must be understood differently! ... THE abstract data type I HAVE IN MIND. ... ones provided by Common-Lisp, if at all. ...
    (comp.lang.lisp)
  • 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)