動態數組

在計算機科學中，動態數組（dynamic array），也稱為：可增長數組（growable array）、可調大小數組（ resizable array）、動態表格（ dynamic table）、可變化數組（mutable array）或數組列表（array list），是一種隨機訪問的、大小可變的列表數據結構，它允許增加或移除元素。在很多現代主流程式語言中，它是通過標準庫而提供的。動態數組克服了靜態數組的限制，靜態數組有着需要在內存分配時指定的固定容量。

使用幾何擴張將一些值插入到動態數組的末端。灰白單元格指示留作擴張的空間。多數插入是快速的（常數時間），而某些插入因為需要內存分配而緩慢（Θ(n)時間，標示了烏龜)。展示了最終數組的「邏輯大小」和「容量」。

動態數組與動態分配的數組或可變長數組不是一種東西，可變長數組的大小是在分配這個數組的時候固定的，然而動態數組也可以使用這種固定大小的數組作為後端。

語言支持

C++的std::vector和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語言提供動態數組實現，包括Core Foundation中的CFArray與CFMutableArray，和GLib中的GArray與GPtrArray。

Common Lisp通過允許配置內建array類型為「可調整的」和通過「填充指針」指定插入位置，提供了對可變大小向量的初步支持。

參見

• 堆疊
• 隊列

外部連結

• 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