基於數組的列表和常規數組

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)使用一個獨特的密鑰元素。