第4章 鏈表

4.1 鏈表的基礎知識

鏈表是一種常見的基礎數據結構。在鏈表中，每個節點包含指向下一個節點的指針，這些指針把節點連接成鏈狀結構。

在創建鏈表時無須事先知道鏈表的長度。鏈表節點的內存分配不是在創建鏈表時一次性地完成，而是每添加一個節點分配一次內存。當插入一個節點時，只需要為新節點分配內存，然后通過調整指針的指向來確保新節點被鏈接到鏈表中。這樣，鏈表就能實現靈活的內存動態管理，可以充分地利用計算機的內存資源。

和數組相比，鏈表更適合用來存儲一個大小動態變化的數據集。如果需要在一個數據集中頻繁地添加新的數據并且不需要考慮數據的順序，那么可以用鏈表來實現這個數據集。鏈表中的插入操作可以用O（1）的時間來實現。

由于鏈表中的內存不是一次性分配的，因此鏈表節點在內存中的地址并不是連續的。如果想在鏈表中找到鏈表的第i個節點，就只能從頭節點開始朝著指向下一個節點的指針遍歷鏈表，它的時間效率為O（n）。而在數組中，根據下標用O（1）的時間就能找到第i個元素。

鏈表的創建、插入節點、刪除節點等操作都只需要20行左右的代碼就能實現，其代碼量比較適合作為面試題。由于鏈表是一種動態的數據結構，其操作是針對指針進行的，因此應聘者需要有較好的編程功底才能編寫出正確的操作鏈表的代碼。另外，鏈表這種數據結構很靈活，面試官可以用鏈表設計出具有挑戰性的面試題。基于上述幾個原因，與鏈表相關的題目深受面試官的青睞。

大多數出現在算法面試題中的鏈表都是單向鏈表。單向鏈表的節點包含指向下一個節點的指針，因此單向鏈表的節點可以定義為如下形式：