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