下載好向圈APP可以快速聯系圈友

您需要 登錄 才可以下載或查看，沒有帳號？立即注冊

x

Python 算法 03-- 數組和鏈表(下)-1.jpg (93.27 KB, 下載次數: 0)

2020-9-12 12:24 上傳

Python 算法 03-- 數組和鏈表(下)-2.jpg (56.14 KB, 下載次數: 0)

2020-9-12 12:24 上傳

Python 算法 03-- 數組和鏈表(下)-3.jpg (10.81 KB, 下載次數: 0)

2020-9-12 12:24 上傳

曾經有個禿頂的面試官問了我一個問題：

數組相對于鏈表，為什么我們都說數組查找效率快？

Python 大星：數組占用的內存空間是連續的

面試官：還有其他的嗎？

Python 大星：......

以 int 類型為例，data_type_size 占 4 個字節 ，length 為 10，計算機分配連續的內存空間 1000 - 1039，其中，內存塊的首地址為 base_address = 1000。

Python 算法 03-- 數組和鏈表(下)-4.jpg (43.08 KB, 下載次數: 0)

2020-9-12 12:24 上傳

當我們隨機訪問數組中的一個元素，

它會首先通過下面的尋址公式，計算出該元素存儲的內存地址：

Python 算法 03-- 數組和鏈表(下)-5.jpg (21.27 KB, 下載次數: 0)

2020-9-12 12:24 上傳

我們從這個公式可以看出，如果數組下角標從 1 開始，那么公式將多做一步減法，這也是為什么數組下角標一般從 0 開始的原因之一。

Python 算法 03-- 數組和鏈表(下)-6.jpg (22.1 KB, 下載次數: 0)

2020-9-12 12:24 上傳

回到最開始的面試題，為什么我們都說數組查找效率快？

● 數組占用的內存空間是連續的

● 數組中都為同一類型的元素

● CPU 緩存會讀入一片連續的內存空間

因為數組結構是連續的內存地址， 所以數組全部或者部分元素被連續存在 CPU 緩存里面

Python 算法 03-- 數組和鏈表(下)-7.jpg (38.05 KB, 下載次數: 0)

2020-9-12 12:24 上傳

數組低效的 “插入” 和 “刪除”？

● 插入

Python 算法 03-- 數組和鏈表(下)-8.jpg (58.73 KB, 下載次數: 0)

2020-9-12 12:24 上傳

插入

如果在數組末尾插入元素 x，不需要移動數組中的其他元素，時間復雜度為 O(1)。如果在數組首位插入元素 x，數組中的其他元素都需要往后移動一位，最壞時間復雜度是 O (n)。因為我們在每個位置插入元素的概率是一樣的，所以平均情況時間復雜度為 (1+2+…n)/n=O (n)。

● 刪除

Python 算法 03-- 數組和鏈表(下)-9.jpg (47.5 KB, 下載次數: 0)

2020-9-12 12:24 上傳

刪除

跟插入數據類似，如果刪除數組末尾的數據，則最好情況時間復雜度為 O (1)；如果刪除開頭的數據，則最壞情況時間復雜度為 O (n)；平均情況時間復雜度也為 O (n)。

Python 算法 03-- 數組和鏈表(下)-10.jpg (10.65 KB, 下載次數: 0)

2020-9-12 12:24 上傳

以單向鏈表為例

Python 算法 03-- 數組和鏈表(下)-11.jpg (33.07 KB, 下載次數: 0)

2020-9-12 12:24 上傳

單向鏈表

● 鏈表低效的“查找”？

我們把鏈表的第一個節點叫頭節點，頭結點記錄鏈表的基地址，最后一個節點叫尾節點(尾節點最后指向 NULL)。

因為鏈表的空間是分散的，所以不具有隨機訪問性，如要需要訪問某個位置的數據，需要從第一個數據開始找起，依次往后遍歷，直到找到待查詢的位置，故查找最后一個元素時，則最壞的情況時間復雜度為 O (N)。

● 鏈表高效的“插入” 和 “刪除”

Python 算法 03-- 數組和鏈表(下)-12.jpg (56.55 KB, 下載次數: 1)

2020-9-12 12:24 上傳

圖 1 - 插入

Python 算法 03-- 數組和鏈表(下)-13.jpg (56.92 KB, 下載次數: 0)

2020-9-12 12:24 上傳

圖2 - 刪除

由于鏈表的存儲空間本身不是連續，在鏈表中插入或者刪除元素，不需要為了內存的連續性而移動其他元素。由圖 1 和 圖 2中，我們可以看出只需要改變相鄰節點的指針即可，故鏈表在插入或者刪除的時間復雜度為 O (1)。

數組和鏈表對比圖

Python 算法 03-- 數組和鏈表(下)-14.jpg (26.72 KB, 下載次數: 0)

2020-9-12 12:24 上傳

>>>Python 算法 02--數組和鏈表(上)

總結

以上是生活随笔為你收集整理的python中链表和数组_Python的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。