Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Java

Discussion on Array-Based Lists

Understand the core concepts behind array-based lists including ArrayStack and RootishArrayStack, study their historical origins, implementation techniques, and how they optimize storage and access times in Java.

We'll cover the following...

Additional notes

Most of the data structures described in this chapter are folklore. They can be found in implementations dating back over 3030 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 n\sqrt n ...