溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“數組與鏈表的詳細介紹”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“數組與鏈表的詳細介紹”吧！
數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。
線性表就是數據排成像一條線一樣的結構。每個線性表上的數據最多只有前和后兩個方向。其實除了數組，鏈表、隊列、棧等也是線性表結構。
比如二叉樹、堆、圖等叫非線性表，因為在非線性表中，數據之間并不是簡單的前后關系。
優點：根據下標實現隨機訪問元素。
缺點：數組中插入、刪除元素，可能需要遷移數據實現連續的內存空間，效率較低。
計算機會給每個內存單元分配一個地址，計算機通過地址來訪問內存中的數據。當計算機需要隨機訪問數組中的某個元素時，它會首先通過下面的尋址公式，計算出該元素存儲的內存地址： a[i]_address = base_address + i * data_type_size
拓展：對于m*n的二維數組尋址公式： a[i][j]_address = base_address + ( i * n + j) * data_type_size
數組查找元素的時間復雜度為O(1)的表述是?的，因為即使是通過二分查找排序好的數組時間復雜度也是O(logn)，正確的是數組支持隨機訪問，根據下標隨機訪問的時間復雜度為O(1);
由于連續的內存空間特點，我們在插入或刪除元素時需要將該元素之后的數據全部往后或者往前移動。即最好時間復雜度為O(1)，最壞時間復雜度為O(n)；由于每個位置操作元素的概率是一樣的，所以平均時間復雜度為(1+2+…n)/n=O(n)。
如果存儲的數據不是有序的，我們可以在插入時將原位置的元素插入到數組尾部，在刪除時將數組尾部元素替換當前的位置的元素；這樣插入或刪除操作的時間復雜度為O(1)：
很多語言提供了基于數組的容器類 比如Java的ArrayList或者C++的vector；下面以ArrayList為例來看容器相比數組的優勢：
容器可以將很多數組操作的細節封裝起來，比如元素插入或者刪除時其它元素的遷移工作，另外相比數組來講，容器還可以動態擴容。
因為擴容操作涉及內存申請和數據搬移是比較耗時的，所以在創建容器時最好指定數據的大小，盡量避免擴容操作。
對于業務開發來講，使用容器就足夠了，省時省力；
對于網絡框架、性能優化等底層開發，盡量使用數組。
鏈表也是線性表結構，相比數組來講不需要連續的內存空間，可通過“指針”將零散的內存塊串聯起來，對內存要求沒數組那么高。
每個鏈表的結點除了儲存數據外還需記錄下一個結點的位置，即后繼指針next。
在單鏈表中，第一個結點稱為頭結點，最后一個節點叫做尾結點；頭結點記錄鏈表的開始地址，尾結點后繼指針指向空地址NULL。
在上面數組低效的插入與刪除中我們講過，數組為了保證內存的連續需要搬移操作元素之后的元素，所以時間復雜度為O(n)，而在鏈表中我們只需考慮相鄰節點的后繼指針改變，所以對應的時間復雜度為O(1)。
因為鏈表中內存地址不是連續的，所以不能根據開始地址和下標計算對應元素的內存地址，需要根據后繼指針一一遍歷找到指定節點。
循環鏈表跟單鏈表唯一的區別在于單鏈表尾結點后繼指針指向空地址NULL，而循環鏈表尾結點后繼指針指向頭結點，像環一樣首尾相連。
單向鏈表每個結點只有一個后繼指針next，而雙向鏈表結點除了next還有一個前驅指針prev。
存儲同樣多的數據時，雙向鏈表雖然比單鏈表占用更多內存空間，但是比單鏈表更為靈活支持雙向遍歷，使其在某些情況下插入刪除操作比單鏈表更為簡單、高效。
其實在討論單鏈表時，我們說插入和刪除的時間復雜度為O(1)，其實這個描述是不準確的，下面我們已刪除操作為例：
盡管刪除操作的時間復雜度為O(1)，但是我們要根據值從頭結點開始遍歷比較找到要刪除的結點，遍歷查詢對應的時間復雜度為O(n)；根據加法法則，此種刪除的時間復雜度為O(n)。
這種情況我們已經找到了要刪除的結點，但是如果是單鏈表，我們還需要遍歷單鏈表查詢其前驅結點信息，所以時間復雜度仍然為O(n)；
但雙向鏈表可以直接通過當前結點prev找到其前驅結點信息，所以時間復雜度為O(1)。
雙鏈表的實現就是用空間換時間的設計思想；當內存空間充足的時候，如果我們更加追求代碼的執行速度，我們就可以選擇空間復雜度相對較高、但時間復雜度相對很低的算法或者數據結構。
相反，如果內存比較緊缺，比如代碼跑在手機或者單片機上，這個時候，就要反過來用時間換空間的設計思路。
雙向循環鏈表就是整合了雙向鏈表和循環鏈表的新版本
數組訪問效率高；但是不支持動態擴容，需要整塊內存空間。
鏈表天然支持動態擴容，插入刪除操作更快；但是占用更多內存，頻繁插入刪除時容易造成內存碎片，可能導致頻繁的GC。
感謝各位的閱讀，以上就是“數組與鏈表的詳細介紹”的內容了，經過本文的學習后，相信大家對數組與鏈表的詳細介紹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
