第1章 鏈表

鏈表作為最基本的數據結構，它不僅在實際應用中有著非常重要的作用，而且也是程序員面試筆試中必考的內容。具體而言，它的存儲特點為：可以用任意一組存儲單元來存儲單鏈表中的數據元素（存儲單元可以是不連續的），而且，除了存儲每個數據元素ai外，還必須存儲指示其直接后繼元素的信息。這兩部分信息組成的數據元素ai的存儲映像稱為結點。N個結點鏈在一塊被稱為鏈表，當結點只包含其后繼結點信息的鏈表就被稱為單鏈表，而鏈表的第一個結點通常被稱為頭結點。

對于單鏈表，又可以將其分為有頭結點的單鏈表和無頭結點的單鏈表，如下圖所示。

在單鏈表的開始結點之前附設一個類型相同的結點，稱為頭結點，頭結點的數據域可以不存儲任何信息（也可以存放如線性表的長度等附加信息），頭結點的指針域存儲指向開始結點的指針（即第一個元素結點的存儲位置）。需要注意是，在Java中沒有指針的概念，而類似指針的功能都是通過引用來實現的，為了便于理解，本章仍然使用指針（可以認為引用與指針是類似的）來進行描述，而在實現的代碼中，都是通過引用來建立結點之間關系。

具體而言，頭結點的作用主要有以下兩點：

（1）對于帶頭結點的鏈表，當在鏈表的任何結點之前插入新結點或刪除鏈表中任何結點時，所要做的都是修改前一個結點的指針域，因為任何結點都有前驅結點。若鏈表沒有頭結點，則首元素結點沒有前驅結點，在其前面插入結點或刪除該結點時操作會復雜些，需要進行特殊的處理。

（2）對于帶頭結點的鏈表，鏈表的頭指針是指向頭結點的非空指針，因此，對空鏈表與非空鏈表的處理是一樣的。

由于頭結點有諸多的優點，因此，本章中所介紹的算法都使用了帶頭結點的單鏈表。

下面是一個單鏈表數據結構的定義示例：