小徒弟Karl非常想學鏈表，所以我打算寫一篇關于單鏈表的入門教程。既然是入門，那就要打好基礎，從頭說起。所以先說“線性表”。

一、什么是線性表

線性表是具有相同特性的數據元素的一個有限序列。
該序列中所含元素的個數叫做線性表的長度，如果n表示，那么n>=0。

當n=0時，表示線性表是一個空表，即表中不包含任何元素。

設序列中第i(i表示位序)個元素為ai(1≤i≤n)。
線性表的一般表示為：(a1,a2,…ai,ai+1,…,an)

其中a1為第一個元素，又稱做表頭元素，a2為第二個元素，an為最后一個元素，又稱做表尾元素。
例如，在線性表(1,4,3,2,8,10)中,1為表頭元素，10為表尾元素。

線性表的特點：
1、 有序
線性表里面的元素是一個挨著一個順序排下去的，就像大家排隊買票；
2、允許沒有元素，也就是空表；
3、第一個元素有且僅有一個后繼，最后一個元素有且僅有一個前驅，其他元素有且僅有一個前驅以及有且僅有一個后繼。

二、線性表的運算

線性表有一些基本運算，舉例如下:

(1) 初始化線性表——構造一個空的線性表；(2) 銷毀線性表——釋放線性表占用的內存空間；(3) 判線性表是否為空表；(4) 求線性表的長度——返回表中元素個數；(5) 遍歷線性表——當線性表不為空時，順序顯示表中各結點的值域；(6) 求線性表中指定位置的某個數據元素；(7) 定位查找LocateElem(L,e)：返回表L中第1個值域與e相等的位序。若這樣的元素不存在，則返回值為0。(8) 插入數據元素——在L的第i個元素之前插入新的元素e，L的長度增加1。(9) 刪除數據元素——刪除L的第i個元素，L的長度減1。

三、線性表的順序存儲——順序表

線性表只是一種邏輯結構，至于它在計算機中是如何存儲的，我們還要專門討論。因為線性表是有順序的，所以很容易想到用數組來存儲線性表。

線性表的順序存儲結構就是：把線性表中的所有元素按照其邏輯順序依次存儲到一塊連續的存儲空間中。

用數組來存儲線性表，其缺點是：
1、在插入、刪除時要移動大量的結點
2、表的大小在定義數組時指定，無法動態更改

為了克服以上缺點，有了線性表的鏈式存儲。

四、線性表的鏈式存儲—鏈表

在鏈式存儲中,每個存儲結點不僅包含元素本身的信息（稱之為數據域），而且包含元素之間邏輯關系的信息，即包含其后繼結點的地址信息，這稱為指針域。一般地，每個結點有一個或多個這樣的指針域。若一個結點中的某個指針域不需要指向任何結點，則僅它的值為空，用NULL表示。

五、單鏈表

在每個結點中除包含有數據域外，又設置一個指針域，用以指向其后繼結點，這樣的表稱為線性單向鏈接表，簡稱單鏈表。

1、不帶頭結點的單鏈表

這種單鏈表必須有一個頭指針（假設叫head），用以指向單鏈表中第一個結點。否則單鏈表會在內存中丟失。
示意圖如下：

2、帶頭結點的單鏈表

為了便于插入和刪除等算法的實現，在單鏈表的第一個元素之前增加一個特殊的節點——稱為頭節點，頭結點的數據域一般不使用，只使用其指針域。這種單鏈表在應用時，必須要知道頭結點的地址，否則單鏈表會在內存中丟失。

示意圖如下：

3、循環單鏈表

鏈表中最后一個結點的指針域不再是NULL，而是指向整個鏈表的第一個結點或者頭結點，從而使鏈表形成一個環。和單鏈表相同，循環單鏈表也有帶頭結點和不帶頭結點兩種。

下圖是帶頭結點的循環單鏈表：

總結

以上是生活随笔為你收集整理的单链表入门（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。