dynamic array must waste this much space if the operations are to remain amortized constant time. Additionally, they present a variant where growing and shrinking the buffer has not only amortized but worst-case constant time. Bagwell (2002) presented the VList algorithm, which can be adapted to implement a dynamic array. Naïve resizable arrays -- also called "the worst implementation" of resizable arrays -- keep the allocated size of the array exactly big enough for all the data it contains, perhaps by calling realloc for each and every item added to the array. Naïve resizable arrays are the simplest way of implementing a resizeable array in C. They don't waste any memory, but appending to the end of the array always takes Θ(n) time. Linearly growing arrays pre-allocate ("waste") Θ(1) space every time they re-size the array, making them many times faster than naïve resizable arrays -- appending to the end of the array still takes Θ(n) time but with a much smaller constant. Naïve resizable arrays and linearly growing arrays may be useful when a space-constrained application needs lots of small resizable arrays; they are also commonly used as an educational example leading to exponentially growing dynamic arrays. Language support C++'s std::vector and Rust's std::vec::Vec are implementations of dynamic arrays, as are the ArrayList classes supplied with the Java API and the .NET Framework. The generic List<> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays. Smalltalk's OrderedCollection is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1). Python's list datatype implementation is a dynamic array the growth pattern of which is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... Delphi and D implement dynamic arrays at the language's core. Ada's Ada.Containers.Vectors generic package provides dynamic array implementation for a given subtype. Many scripting languages such as Perl and Ruby offer dynamic arrays as a built-in primitive data type. Several cross-platform frameworks provide dynamic array implementations for C, including CFArray and CFMutableArray in Core Foundation, and GArray and GPtrArray in GLib. Common Lisp provides a rudimentary support for resizable vectors by allowing to configure the built-in array type as adjustable and the location of insertion by the fill-pointer. References External links NIST Dictionary of Algorithms and Data Structures: Dynamic array VPOOL - C language implementation of dynamic array. CollectionSpy — A Java profiler