pg电子怎么样

1-2 鏈表

鏈表是數據結構之一，其中的數據呈線性排列。在鏈表中，數據的添加和刪除都較為方便，就是訪問比較耗費時間。

這就是鏈表的概念圖。Blue、Yellow、Red這3個字符串作為數據被存儲于鏈表中。每個數據都有1個“指針”，它指向下一個數據的內存地址。

在鏈表中，數據一般都是分散存儲于內存中的，無須存儲在連續空間內。

因為數據都是分散存儲的，所以如果想要訪問數據，只能從第1個數據開始，順著指針的指向一一往下訪問（這便是順序訪問）。比如，想要找到Red這一數據，就得從Blue開始訪問。

這之后，還要經過Yellow，我們才能找到Red。

如果想要添加數據，只需要改變添加位置前后的指針指向就可以，非常簡單。比如，在Blue和Yellow之間添加Green。

將Blue的指針指向的位置變成Green，然后再把Green的指針指向Yellow，數據的添加就大功告成了。

數據的刪除也一樣，只要改變指針的指向就可以，比如刪除Yellow。

這時，只需要把Green指針指向的位置從Yellow變成Red，刪除就完成了。雖然Yellow本身還存儲在內存中，但是不管從哪里都無法訪問這個數據，所以也就沒有特意去刪除它的必要了。今后需要用到Yellow所在的存儲空間時，只要用新數據覆蓋掉就可以了。

解說

對鏈表的操作所需的運行時間到底是多少呢？在這里，我們把鏈表中的數據量記成n。訪問數據時，我們需要從鏈表頭部開始查找（線性查找），如果目標數據在鏈表最后的話，需要的時間就是O（n）。

另外，添加數據只需要更改兩個指針的指向，所以耗費的時間與n無關。如果已經到達了添加數據的位置，那么添加操作只需花費O（1）的時間。刪除數據同樣也只需O（1）的時間。

參考：3-1線性查找

補充說明

上文中講述的鏈表是最基本的一種鏈表。除此之外，還存在幾種擴展方便的鏈表。

雖然上文中提到的鏈表在尾部沒有指針，但我們也可以在鏈表尾部使用指針，并且讓它指向鏈表頭部的數據，將鏈表變成環形。這便是“循環鏈表”，也叫“環形鏈表”。循環鏈表沒有頭和尾的概念。想要保存數量固定的最新數據時通常會使用這種鏈表。

循環鏈表

另外，上文鏈表里的每個數據都只有一個指針，但我們可以把指針設定為兩個，并且讓它們分別指向前后數據，這就是“雙向鏈表”。使用這種鏈表，不僅可以從前往后，還可以從后往前遍歷數據，十分方便。

但是，雙向鏈表存在兩個缺點：一是指針數的增加會導致存儲空間需求增加；二是添加和刪除數據時需要改變更多指針的指向。

雙向鏈表