data-structures - 基于数组的列表和常规数组

Question

基于数组的列表和常规数组是否相同？当用作字典数据结构时，哈希表和基于数组的列表有什么不同，它们之间有什么权衡吗？

Answer 1

数据结构简介.. 具有 Java 背景。

基于数组、列表和数组列表的数据结构允许您按元素插入的顺序访问元素。

元素：3,4,2,1,5

列表：[3]<->[4]<->[2]<->[1]<->[5]

基于哈希映射/表的数据结构允许您通过与之关联的唯一键访问元素。

元素：3,4,2,1,5

键：c,d,b,a,e

地图：

[c]->[3]

[d]->[4]

[b]->[2]

[a]->[1]

[e]->[5]

数组（或向量）。它O(1)以极低的空间开销从数组中访问任何元素提供了极快的速度，您还可以从当前元素向后和向前迭代。但主要问题是数组是固定大小的，您必须知道创建数据结构时需要多少元素。

列表（双链表）。它提供了一个动态大小的数据结构（您不必知道创建时元素的数量），可以快速访问前一个元素和新元素。但是访问任何元素都非常慢O(n)，并且它的空间开销略高于数组。

数组列表（基于数组的列表）。像数组一样，它提供了O(1)对任何元素的极快访问并且具有非常低的空间开销。与列表一样，您在创建它时不需要知道数据结构中有多少元素。但在幕后（用户没有意识到）它本质上是一个数组，它检测数组何时“满”，然后创建一个新数组（大约是原始大小的两倍）并将元素从旧数组复制到新数组。

哈希表与上面的三种数据结构有很大的不同。它不允许按插入顺序访问元素。相反，它允许您将键映射到值；O(1)因此您可以使用唯一键非常快速地访问元素。