鏈表基礎總結
1. 簡單介紹
鏈表，即線性表的鏈式存儲結構，鏈表使用一組任意的存儲單元來存儲數據元素。如果某兩個數據元素在邏輯位置上相鄰，那麼他們在物理位置上不一定相鄰。如圖：
但是這樣看著太亂了，為了看著舒服，表示方便，我們把這張圖改成：
2. 單向鏈表的結構和特點
在上圖中，我們可以看出一個鏈表包含了存儲的數據元素（方框中的值）以及這些數據元素之間邏輯關係（箭頭，下一個數據元素的位置）。為了表示數據元素及邏輯關係，我們需要一個能存儲它們的「載體」，這個載體就是結點（node）。它長這樣：
一個結點有兩個部分：data是存儲數據的數據域，next是存儲它的下一個數據元素（在邏輯上）的位置資訊的指針域。
有了這兩個部分，一個具體的單向鏈表如下：
介紹到這裡，可以很容易地總結出單向鏈表的特點：
- 鏈表由若干結點組成
- 每個結點由數據域和指針域組成，數據域存儲數據，指針域存儲下一個結點的位置
- 單向鏈表是單向的，數據存取必須從第一個結點開始
- 鏈表的最後一個結點沒有後繼結點，所以其指針域置為Null，表示鏈表結束
2.1. 頭結點與頭指針
頭結點：即單鏈表的第1個存數據的結點之前的那個結點，該結點的數據域可以不存儲任何資訊，也可以存儲如鏈表長度等附加資訊，該結點的指針域指向第1個存數據的結點。
下面是一個帶頭結點的鏈表：
head.next是第1個存數據的結點
下面是一個不帶頭結點的鏈表：
head是第1個存數據的結點
頭指針（head）：不是一個單獨的結點，而是對第1個結點的引用。它通過存儲一個指向第1個結點的指針來保存整個鏈表
注意：第1個結點不一定是第1個存數據的結點
- 在帶頭結點的單鏈表中，頭指針指向第1個結點（頭結點）
- 在不帶頭結點的單鏈表中，頭指針指向第1個結點（第1個存數據的結點）
3. 單鏈表的操作
在介紹下面的操作時，會分兩種：帶頭結點的鏈表和不帶頭結點的鏈表。
/**
* 結點類
* @author Xing Xiaoguan
*/
public class Node {
int data;
Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
}
3.1. 增加結點
3.1.1. 帶頭結點的單鏈表
頭插法：新增加的結點放在頭結點後面。頭插法的結點順序和插入順序相反。下圖是頭插法的過程
尾插法：新增加的結點放在鏈表的最後面。下圖是尾插法的過程：
中間插法：新增加的結點插在鏈表中間。下圖是中間插法的過程：
由於是單向鏈表，所以我們必須先找到prevNode結點，才能進行插入操作。
nextNode不是必須的，可以使用prevNode.next代替。如果這樣代替了，插入操作的順序不能變，否則prevNode結點後的所有結點都會丟失。
3.1.2. 不帶頭節點的單鏈表
頭插法：新增加的結點被頭指針引用。下圖記錄了整個過程：
尾插法：新增加的結點放在鏈表的最後面。下圖描述了過程：
中間插法：不帶頭節點和帶頭結點的一樣。
3.1.3. 二者比較
比較上面的動圖可以看出：
不帶頭結點的鏈表在進行頭插和尾插時需要考慮空鏈表的情況，即插入第1個結點和插入其他結點的操作不同。
帶頭結點的鏈表在進行頭插和尾插時不需要考慮空鏈表的情況，即插入第1個結點和插入其他結點的操作相同。
顯然帶頭結點的鏈表在進行插入操作時更方便。
3.2. 遍歷鏈表
帶頭結點和不帶頭節點的鏈表在遍歷時要注意遍歷的起點和結束：第一個存數據的結點~最後一個存數據的結點。
帶頭結點的鏈表遍歷從head.next結點開始，不帶頭結點的鏈表遍歷從head開始。
//帶頭結點的遍歷
for (Node node = head.next; node != null; node = node.next)
System.out.print(node.data + " ");
//不帶頭結點的遍歷
for (Node node = head; node != null; node = node.next)
System.out.print(node.data + " ");
3.3. 查詢結點
查詢其實就是對遍歷的應用，不管是根據下標index查詢還是根據數據data查詢，其實都是在遍歷鏈表。
3.4. 刪除結點
3.4.1. 帶頭結點的單鏈表
刪除第一個存數據的結點：
刪除最後一個結點：
刪除中間結點：
3.4.2. 不帶頭結點的單鏈表
刪除第一個存數據的結點：
刪除中間結點和刪除最後一個結點的操作與帶頭結點的操作相同。
3.4.3. 二者比較
刪除第1個存數據的結點的操作不同，刪除中間結點和尾結點的操作相同。
3.5. 更新結點
更新結點是對查詢的應用，查詢到要更新的結點然後更新即可。
4. 程式碼
完整程式碼獲取請移步碼雲
//gitee.com/xingrenguanxue/code-in-blogs/tree/master/src/鏈表基礎總結/linkedlist
如有錯誤，還請指正
文章首發於公眾號『行人觀學』
