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.$