Discussion on Array-Based Lists

Additional notes

Most of the data structures described in this chapter are folklore. They can be found in implementations dating back over 30 years. For example, implementations of stacks, queues, and deques, which generalize easily to the ArrayStack, ArrayQueue and ArrayDeque structures described here, are discussed by KnuthD. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, third edition, 1997..

Brodnik et al.A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick. Resizable arrays in optimal time and space. In Dehne et al. [18], pages 37–48. seem to have been the first to describe the RootishArrayStack and prove a $\sqrt n$ lower-bound. They also present a different structure that uses a more sophisticated choice of block sizes in order to avoid computing square roots in the i2b(i) method. Within their scheme, the block containing $i$ is block $\lfloor \log (i+1) \rfloor$, which is simply the index of the leading $1$ bit in the binary representation of $i + 1$. Some computer architectures provide an instruction for computing the index of the leading $1$-bit in an integer. In Java, the Integer class provides a method numberOfLeadingZeros(i) from which one can easily compute $\lfloor \log(i+1) \rfloor.$

A structure related to the RootishArrayStack is the two-level tiered vector of Goodrich and KlossM. T. Goodrich and J. G. Kloss. Tiered vectors: Efficient dynamic arrays for rank-based sequences. In Dehne et al. [18], pages 205– 216.. This structure supports the get(i, x) and set(i, x) operations in constant time and add(i, x) and remove(i) in $O(\sqrt n)$ time.