一、概述（本文以最簡單的單向鏈表為例，其它復雜的鏈表以后再說明）
-
鏈表和陣列不同，鏈表在創建的時候不會預先在記憶體中開辟空間，
-
鏈表的存盤邏輯上是連續的，物理上是不連續的
-
鏈表在存盤資料的記憶體中會有兩塊資料，一塊用來存資料，一塊用來存盤指向下一個資料節點的指標
二、圖示
-
由上圖我們可以看出，鏈表在邏輯上它的存盤是連續的
-
但是在記憶體實際的存盤卻是碎片化的
三、操作鏈表的時間復雜度
-
查詢
-
鏈表中沒有索引供我們訪問，所以由上圖我們可以看出來，要想訪問鏈表中的某一個元素，必須從頭開始找，利用元素的next指標，一個挨著一個的查找，
-
所以鏈表查詢元素的時間復雜度為O(n)
-
-
插入
-
由上圖我們可以看出，在該鏈表的a元素與b元素中插入一個c元素，我們只需要a.next=c; c.next=b;就可以了；
-
所以鏈表的插入元素時間復雜度為O(1)
-
-
洗掉
-
如上圖所示，洗掉該鏈表中的b元素，我們只需要將a.next=c; 即可
-
所以鏈表洗掉元素的時間復雜度為O(1)
轉載請注明出處：https://www.cnblogs.com/Infancy/p/12591581.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67586.html
標籤：其他