# 鏈表與數組 > 原文： [https://www.geeksforgeeks.org/linked-list-vs-array/](https://www.geeksforgeeks.org/linked-list-vs-array/) [數組](https://www.geeksforgeeks.org/array-data-structure/)和[鏈表](https://www.geeksforgeeks.org/data-structures/linked-list/)都可以用于存儲相似類型的線性數據，但是它們相互之間都有一些優點和缺點。   數組和鏈接列表 之間的主要區別 1.數組是包含相似類型的數據元素的集合的數據結構，而鏈接列表被視為非原始數據結構，它包含稱為節點的無序鏈接元素的集合。 2.在數組中，元素屬于索引，即，如果要進入第四個元素，則必須編寫變量名稱及其索引或在方括號內的位置。 3.但是，在鏈接列表中，您必須從頭開始并逐步進行，直到到達第四個元素。 4.訪問數組中的元素速度很快，而“鏈接列表”需要線性時間，因此訪問速度要慢得多。 5.諸如在數組中插入和刪除之類的操作會花費大量時間。 另一方面，鏈接列表中這些操作的執行速度很快。 6.數組的大小固定。 相反，鏈接列表是動態且靈活的，并且可以擴展和縮小其大小。 7.在數組中，內存是在編譯時分配的，而在鏈接列表中，內存是在執行或運行時分配的。 9.元素連續存儲在數組中，而元素則隨機存儲在鏈接列表中。 10.由于實際數據存儲在數組的索引內，因此對內存的需求減少了。 相反，由于存儲了額外的下一個和上一個引用元素，因此需要在鏈接列表中有更多的存儲空間。 11.此外，數組中的內存利用率低下。 相反，在鏈表中內存利用率很高。 以下是支持鏈表的要點。 （1）數組的大小是固定的：因此，我們必須提前知道元素數量的上限。 而且，通常，所分配的存儲器與用途無關地等于上限，并且在實際使用中，很少達到上限。 （2）在元素數組中插入新元素非常昂貴，因為必須為新元素創建一個空間，并且為創建空間而必須移動現有元素。 例如，假設我們在數組 id []中維護 ID 的排序列表。 id [] = [1000，1010，1050，2000，2040，…..]。 如果要插入新的 ID 1005，則要維持排序順序，我們必須將所有元素都移到 1000（不包括 1000）之后。 除非使用某些特殊技術，否則刪除數組也很昂貴。 例如，要刪除 id []中的 1010，必須移動 1010 之后的所有內容。 因此，鏈表相對于數組 具有以下兩個優點：1）動態大小 2）易于插入/刪除 鏈接列表具有以下缺點： 1）不允許隨機訪問。 我們必須從第一個節點開始順序訪問元素。 因此，我們無法使用鏈接列表進行二分搜索。 2）列表的每個元素都需要用于指針的額外存儲空間。 3）數組具有更好的緩存局部性，可以在性能上產生很大的不同。 參考： [http://cslibrary.stanford.edu/103/LinkedListBasics.pdf](http://cslibrary.stanford.edu/103/LinkedListBasics.pdf)