），而某些插入因为需要内存分配而缓慢（时间，标示了乌龟)。展示了最终数组的“逻辑大小”和“容量”。]]
在计算机科学中，动态数组（dynamic array），也称为：可增长数组（growable array）、可调大小数组（ resizable array）、动态表格（ dynamic table）、可变化数组（mutable array）或数组列表（array list），是一种随机访问的、大小可变的列表数据结构，它允许增加或移除元素。在很多现代主流编程语言中，它是通过标准库而提供的。动态数组克服了静态数组的限制，静态数组有着需要在内存分配时指定的固定容量。
动态数组与动态分配的数组或可变长数组不是一种东西，可变长数组的大小是在分配这个数组的时候固定的，然而动态数组也可以使用这种固定大小的数组作为后端。
语言支持
C++的和Rust的std::vec::Vec是动态数组的实现，还有ArrayList类，提供它的有Java API和.NET框架。
.NET框架版本2.0提供的泛型List<>类也是通过动态数组实现的。Smalltalk的OrderedCollection时具有动态的开始与结束索引的动态数组，这使得移除第一元素也只需要O(1)时间。
Python的list数据类型实现了动态数组，其增长模式是：0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...，参见在github.com的listobject.c。
Delphi和D在语言核心实现了动态数组。
Ada的Ada.Containers.Vectors泛型包提供了针对给定子类型的动态数组。
很多脚本语言比如Perl和Ruby提供了动态数组作为内建原始数据类型。
一些跨平台框架为C语言提供动态数组实现，包括中的CFArray与CFMutableArray，和GLib中的GArray与GPtrArray。
Common Lisp通过允许配置内建array类型为“可调整的”和通过“填充指针”指定插入位置，提供了对可变大小向量的初步支持。
参见
- 堆栈
- 队列
引用
外部链接
- [https://xlinux.nist.gov/dads/HTML/dynamicarray.html NIST Dictionary of Algorithms and Data Structures: Dynamic array]
- [http://www.bsdua.org/libbsdua.html#vpool VPOOL] - C language implementation of dynamic array.
- [https://web.archive.org/web/20090704095801/http://www.collectionspy.com/ CollectionSpy] — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
- [http://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html Open Data Structures - Chapter 2 - Array-Based Lists] , Pat Morin
评论 (0)