面試官昨天在面試中問了我關于鏈表的問題: 情況如下

訪者: 請告訴我鏈接列表和數組之間的區別？

我: 數組靜態分配內存，鏈表動態分配內存；數組在內存中是連續的鏈表的鏈表，并且鏈表不是連續的；數組使用下標定位，時間復雜度為O（1），鏈表定位元素的時間復雜度為O（n）；在數組中插入或刪除元素的時間復雜度為O（n），而鏈表的時間復雜度為O（1）.

基于以上分析，數組和鏈表的優缺點如下:

訪者: 那么請告訴我單鏈和雙鏈手表之間的區別？

我:

單鏈表只有一個指向下一結點的指針，也就是只能next
雙鏈表除了有一個指向下一結點的指針外，還有一個指向前一結點的指針，可以通過prev()快速找到前一結點，顧名思義，單鏈表只能單向讀取

訪者: 根據您的描述，您可以使用二分法的想法來查找和刪除雙鏈表鏈表的鏈表，這樣效率會大大提高，但是為什么目前市場上需要單鏈表的應用比雙鏈表使用更廣泛？

我: ...我真的不知道，然后面試官提醒我從存儲效率的角度考慮這個問題...

回到百度后，我發現互聯網上的答案主要是關于鏈表代碼的實現，并且對鏈表的本質沒有深入的分析，因此我做了以下工作分析:

單鏈表和雙鏈表的如下:

從以上結構可以得出結論，雙鏈表具有以下優點:

1. 刪除單鏈列表中的節點時，必須獲取要刪除的節點的先驅. 有兩種獲取前體的方法. 第一種方法是找到要刪除的節點，同時始終保存當前節點. 節點的前體. 第二種方法是在定位要刪除的節點之后，從單鏈接列表的開頭定位前驅. 盡管通常使用方法一. 但是實際上，這兩種方法的效率是相同的，指針的總移動操作將有2 * i次. 如果使用雙向鏈表，則無需定位前驅節點. 因此，指針的總移動操作為i倍.

2. 搜索是相同的，我們可以從頭（第一個節點）后向搜索操作和最后一個（尾節點）前向搜索操作中借用二分法的思想，從而使雙鏈表的效率可以加倍.

但是為什么市場上的單鏈表使用冗余的雙鏈表？

從存儲結構的角度來看，每個雙鏈表節點比單鏈表節點多一個指針，并且n的長度需要n * length（32個指針的長度為4個字節）. 位系統（64位系統為8字節），不適用于某些時間效率不高的應用程序，因為它比單鏈表占用更多空間；那么設計人員將在空間上使用時間. 這是一種總體項目測量.

本文來自本站，轉載請注明本文網址：
http://www.pc-fly.com/a/jisuanjixue/article-252611-1.html