當前位置：網站首頁>數組與鏈錶

數組與鏈錶

2022-01-26 23:12:25 【智慧的人不要禿頭】

作為線性錶的兩種存儲方式 —— 鏈錶和數組，這對相愛相殺的好基友有著各自的優缺點。

數組，所有元素都連續的存儲於一段內存中，且每個元素占用的內存大小相同。這使得數組具備了通過下標快速訪問數據的能力。

但連續存儲的缺點也很明顯，增加容量，增删元素的成本很高，時間複雜度均為 O(n)。

增加數組容量需要先申請一塊新的內存，然後複制原有的元素。如果需要的話，可能還要删除原先的內存。

删除元素時需要移動被删除元素之後的所有元素以保證所有元素是連續的。

增加元素時需要移動指定比特置及之後的所有元素，然後將新增元素插入到指定比特置，如果容量不足的話還需要先進行擴容操作。

數組的優缺點：

由若幹個結點組成，每個結點包含數據域和指針域。（頭節點、尾節點）

鏈錶的存儲方式使得它可以高效的在指定比特置插入與删除，時間複雜度均為 O(1)。

鏈錶的優缺點：

優點：

（1）插入和删除速度快，保留原有的物理順序，在插入或者删除一個元素的時候，只需要改變指針指向即可。

（2）沒有空間限制,存儲元素無上限,只與內存空間大小有關.

（3）動態分配內存空間，不用事先開辟內存

（4)是內存的利用率變高

缺點：

（1）占用額外的空間以存儲指針，比較浪費空間，不連續存儲，malloc函數開辟空間碎片比較多)

（2）查找速度比較慢，因為在查找時，需要循環鏈錶。查找操作為O(n)

無法高效獲取長度，無法根據偏移快速訪問元素，是鏈錶的兩個劣勢。

然而面試的時候經常碰見諸如獲取倒數第k個元素，獲取中間比特置的元素，判斷鏈錶是否存在環，判斷環的長度等和長度與比特置有關的問題。這些問題都可以通過靈活運用雙指針來解决。

如果存在環，如何判斷環的長度呢？快慢指針相遇後繼續移動，直到第二次相遇。兩次相遇間的移動次數即為環的長度。

參考：來自 <力扣>

版權聲明
本文為[智慧的人不要禿頭]所創，轉載請帶上原文鏈接，感謝
https://cht.chowdera.com/2022/01/202201262312247099.html