动态数组
在计算机科学中，动态数组（dynamic array），也称为：可增长数组（growable array）、可调大小数组（ resizable array）、动态表格（ dynamic table）、可变化数组（mutable array）或数组列表（array list），是一种随机访问的、大小可变的列表数据结构，它允许增加或移除元素。在很多现代主流编程语言中，它是通过标准库而提供的。动态数组克服了静态数组的限制，静态数组有着需要在内存分配时指定的固定容量。
动态数组与动态分配的数组或可变长数组不是一种东西，可变长数组的大小是在分配这个数组的时候固定的，然而动态数组也可以使用这种固定大小的数组作为后端[1]。
语言支持
编辑C++的std::vector和Rust的std::vec::Vec是动态数组的实现，还有ArrayList类，提供它的有Java API[2][3]:236和.NET框架[4][5]:22。
.NET框架版本2.0提供的泛型List<>类也是通过动态数组实现的。Smalltalk的OrderedCollection时具有动态的开始与结束索引的动态数组，这使得移除第一元素也只需要O(1)时间。
Python的list数据类型实现了动态数组，其增长模式是：0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...，参见在github.com的listobject.c[6]。
Ada的Ada.Containers.Vectors泛型包提供了针对给定子类型的动态数组。
很多脚本语言比如Perl和Ruby提供了动态数组作为内建原始数据类型。
一些跨平台框架为C语言提供动态数组实现，包括Core Foundation中的CFArray与CFMutableArray，和GLib中的GArray与GPtrArray。
Common Lisp通过允许配置内建array类型为“可调整的”和通过“填充指针”指定插入位置，提供了对可变大小向量的初步支持。
参见
编辑引用
编辑- ^ See, for example, the source code of java.util.ArrayList class from OpenJDK 6.
- ^ Javadoc on
ArrayList - ^ Bloch, Joshua. "Effective Java: Programming Language Guide" third. Addison-Wesley. 2018. ISBN 978-0134685991.
- ^ ArrayList Class
- ^ Skeet, Jon. C# in Depth. Manning. ISBN 978-1617294532.
- ^ listobject.c (github.com)
外部链接
编辑- NIST Dictionary of Algorithms and Data Structures: Dynamic array
- VPOOL - C language implementation of dynamic array.
- CollectionSpy — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
- Open Data Structures - Chapter 2 - Array-Based Lists, Pat Morin