2.3　單鏈表

鏈表采用鏈式結構存儲數據。在鏈式存儲結構中，一個最小的存儲單元稱為一個結點，結點類似于鏈條中的一個環。多個結點串在一起構成一個鏈，形成如圖2-8所示的一條鏈條。

圖2-8　鏈條示意圖

使用鏈式存儲可以克服順序表需要預先知道數據大小和插入刪除元素造成的數據移動等缺點，鏈式存儲結構可以充分利用內存空間，實現靈活的內存動態管理。但是鏈式存儲失去了數組隨機存取的特點，同時增加了結點的指針域，空間開銷較大。

單向鏈表也稱作單鏈表，是鏈表中很簡單的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。

下面將闡述鏈表增加元素、查找元素和刪除元素的過程。

單鏈表中的數據是以結點來表示的。每個結點的構成包括元素值和指向下一個結點（通常稱作后繼結點）的引用。單鏈表中第一個結點通常稱作頭結點。單鏈表如圖2-9所示。

圖2-9　單鏈表示意圖

2.3.1　單鏈表添加元素

在單鏈表的實現中，需要一個結點類Node，用于表示鏈表中的一個結點。Node中含有一個用于存儲數據的data屬性和指向鏈表中后一個結點的引用。

單鏈表添加元素之前如圖2-10所示。

將值為element的新結點插入第index的位置上。首先找到索引為index-1的結點，然后生成一個數據為element的新結點，并將index-1處結點的next引用指向新結點，新結點的next引用指向原來index處的結點。單鏈表添加元素之后的示意圖如圖2-11所示。

圖2-10　單鏈表添加元素之前示意圖

圖2-11　單鏈表添加元素之后示意圖

2.3.2　單鏈表查找元素

在單鏈表中查找element元素，必須從單鏈表的第一個元素開始向后遍歷，直至找到目標元素為止。單鏈表的查找過程如圖2-12所示。

圖2-12　單鏈表查找元素示意圖

2.3.3　單鏈表刪除元素

將值為element的元素從單鏈表中刪除，需要從單鏈表的頭結點開始查找，找到element元素所在的index位置后，將index-1位置上的結點的next引用指向index+1位置上的結點。

單鏈表刪除元素之前如圖2-13所示。

圖2-13　單鏈表刪除元素之前示意圖

單鏈表刪除元素之后如圖2-14所示。

圖2-14　單鏈表刪除元素之后示意圖

2.3.4　單鏈表的實現

在鏈表的實現中，用內部類Node表示鏈表中的一個結點。Node中含有一個用于存儲數據的data屬性和指向鏈表中后一個結點的引用next。鏈表的代碼如下：

創建鏈表測試類，驗證鏈表功能。測試類的代碼如下：

執行鏈表測試類，測試結果如下：

    ----------向單鏈表新增元素----------
    0 1 2 3 4 5 6 7 8 9
    ----------單鏈表是否為空----------
    false
    ----------單鏈表刪除元素后----------
    1 2 3 4 5 6 7 8 9

2.3.5　單鏈表常見面試考點

（1）單鏈表的概念：單鏈表是使用鏈式結構存儲的線性表。單鏈表只有一個方向。

（2）單鏈表的存儲：單鏈表是使用離散的存儲結構存儲數據的。每個結點都保存了數據和指向后繼結點的引用。

（3）單鏈表的優點：

·　單鏈表不需要使用連續的存儲空間存儲數據。

·　單鏈表沒有固定的容量限制。

·　添加或刪除單鏈表中的元素只需修改相關結點的引用，無須移動其他元素。

（4）單鏈表的缺點：

·　訪問鏈表中的元素所需的時間復雜度為O(n)。

·　每個結點保存下一個結點的引用，占用更多存儲空間。

·　單鏈表只能從頭結點向后查找元素，不能從后向前查找元素。