從理論的角度來看，有序列表和數組之間有什麼區別？

有沒有區別，或者它們是同一事物的兩個術語？從理論的角度來看，有序列表和數組之間有什麼區別？

2012-01-29 Nick

它與HTML有什麼關係？ – doc 2016-08-14 20:38:29

雖然數組和列表之間有一些相似之處，但它們被用於不同的目的。

數組是連續的內存段，而列表只是一堆節點，每個節點都有指向「下一個」節點的指針（在雙向列表的情況下也指向「上一個」節點）。 O（1） - 支持隨機訪問（即通過任意給定的索引i），但刪除/插入元素到數組中很慢 - O（n），因爲必須在所有元素之後移動所有元素刪除/插入元素。另一方面，列表不支持有效的隨機訪問（同時支持高效的連續遍歷），但插入和刪除操作快 - O（1）。

看這張圖片： enter image description here ：和this link爲了更好的解釋。

來源

2012-01-29 07:31:24

數組中的項不一定是任何特定的順序。

通常，可以更快速地將項目添加到列表中的特定點，而不是在等效點添加新項目。（在數組中，您必須對其他條目進行混洗;在列表中，只需調整最多3個元素中的適當指針即可）。類似地，用於從列表和數組中刪除元素。

訪問N ^th列表中的項需要O（N）時間，但是O（1）時間是一個數組。

來源

2012-01-29 07:15:53

所以數組是一個基於硬件（或實現）的概念，而有序列表是一種抽象數據類型？ – Nick 2012-01-29 07:20:12

鏈接列表也是基於實現的（儘管人們可能會認爲它們比數組更「抽象」）。順便說一句，抽象數據類型粗略地說就是您的數據結構必須支持的接口。讓數組和鏈表實現相同的接口並不難（例如，查看Java中的ArrayList vs LinkedList）。雖然，關鍵操作的效率：插入，刪除和[]（在給定索引i處訪問）將大不相同。 – 2012-01-29 07:36:21

數組和列表是不同的數據結構。數組不一定是有序的。性能明智，維護有序列表非常昂貴：O（N）插入，刪除，但是你可以比O（N）更快地進行搜索（使用二進制搜索等）。使用常規數組，搜索是O（N）。使用數組，您可以隨機訪問O（1）中的成員，而這需要O（N）在列表中。

來源

2012-01-29 07:19:00 Oleksi

從理論的角度來看，有序列表和數組之間有什麼區別？

回答

相關問題