線性表除了陣列的表示方法之外, 還有一種表示方法就是連結串列. 與向量不同的是, 連結串列中的元素並非按照線性的方式在記憶體中進行存儲的
SGI STL 中的第二層記憶體配置器就是前向連結串列最好的應用
我們首先用圖表的方式看一下前向連結串列的基本結構
與上一次不同的是, 這次我們加入了一個新的 Node : last
. 這個主要是為了耦合 STL 中的 end()
與 cend()
成員函式
要注意的是, 我們本次採用記憶體配置的方法是 operator new
, 也就是說只配置記憶體, 不會對這塊記憶體進行初始化. 如果我們對 first
或者 last
指標進行解參考, 將會得到一個未定的值
另外, 對於 first
或者 last
指標, 它們是不可以被插入資料或者刪除的. 因此, 我們都將會用 insertAfter
或者 deleteAfter
來替代 insert
或者 delete
. 也就是在某個位置之後插入元素或者刪除某個位置之後的元素
1. 插入
由於指向最後的元素一直都是 last
指標, 而且 last
指標中不存放任何資料, 所以插入變得非常簡單. 除此之外, 因為函式的命名為 insertAfter
, 所以只要將新申請的結點的 next
向想要插入的位置的 next
連線, 然後將資料放入新的結點, 最終將想要插入位置對應的 next
向新結點連線即可
我們可以將這段文字轉換為圖像, 可以結合圖像觀看更加清晰 :
2. 刪除
與插入相同, 因為前向連結串列擁有 last
指標, 而且 last
指標不可放置元素, 那麼刪除也變得非常簡單. 我們只要選取刪除位置的那一個結點, 讓它的 next
向下一個結點的 next
連線即可. 這裡也要注意, 要刪除的那個位置並不是真正被刪除的結點, 因為函式的名稱為 eraseAfter
, 所以對應結點的下一個結點才是真正被刪除的結點. 這也可以使得 0 也可以作為正確的引數傳入 :
大家可以深入理解, 相對於沒有 last
指標或者擁有一個可以存放資料的 last
指標, 為什麼擁有一個不可放置資料的 last
指標, 會讓插入與刪除變得非常簡單 (少了一個條件判斷陳述式)
當然, 前向連結串列不止這一種形式. 你可以寫成沒有 last
指標, first
指標可以存放資料等等. 不管有沒有 last
指標, first
指標或者 last
指標是否可以存放資料, 都是可以寫出來的
資料結構 ForwardList : GitHub 點擊直達
資料結構 ForwardList 使用說明 : GitHub 點擊直達
自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《【資料結構-重構】前向連結串列》https://jonny.vip/2018/07/22/%e3%80%90%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%87%8d%e6%a7%8b%e3%80%91%e5%89%8d%e5%90%91%e9%80%a3%e7%b5%90%e4%b8%b2%e5%88%97/
Leave a Reply