線性表除了陣列的表示方法之外, 還有一種表示方法就是連結串列. 與向量不同的是, 連結串列中的元素並非按照線性的方式在記憶體中進行存儲的

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 指標是否可以存放資料, 都是可以寫出來的