定義

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時候，最開始接觸到的一種數(shù)據(jù)結(jié)構(gòu)就是線性表，對于線性表的定義是：零個或多個數(shù)據(jù)元素的有限序列，那對于線性表來講，又分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于順序存儲結(jié)構(gòu)來說，也就是數(shù)組，數(shù)組的每個元素之間的地址是連續(xù)的；對于鏈?zhǔn)酱鎯碚f，也就是平常所說的鏈表，鏈表每個元素之間的地址并不是連續(xù)的，而是分散的，他們之間的聯(lián)系通過結(jié)點的 next 指針來建立。本文盡可能地將鏈表的知識詳細(xì)地敘述，所涉及的鏈表類型包括：單鏈表，雙鏈表，循環(huán)鏈表，每個鏈表的操作涉及到創(chuàng)建鏈表，刪除鏈表，插入鏈表結(jié)點，刪除鏈表結(jié)點。

單鏈表

何為單鏈表呢，看定義往往讓人一時摸不到頭腦，直接通過圖的形式來展示：

可以看到結(jié)點與結(jié)點之間都是通過一個指針來建立聯(lián)系的，所以對于鏈表結(jié)點的定義往往遵循如下的形式：

typedef?struct?Node
{
????int?data;
????struct?Node?*next;
}ListNode,*LinkList;
而對于單鏈表來說，其還可以進(jìn)行細(xì)分，可以分為帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表，具體是什么意思呢？我們下面分別對這兩種形式進(jìn)行敘述。

帶頭結(jié)點的單鏈表

說到頭結(jié)點，就必須要與另外一個概念進(jìn)行對比闡述，就是頭指針，頭指針并不是一個結(jié)點，它的作用是指向鏈表的第一個結(jié)點，也就是說我們是通過頭指針來找到鏈表的；那頭結(jié)點的意思是什么呢？頭結(jié)點是一個結(jié)點，但是這個結(jié)點的數(shù)據(jù)域是沒有值的，它的存在是方便我們對于鏈表的操作，比方說如果要往鏈表中插入一個結(jié)點，而這個結(jié)點插入的位置就是第一個結(jié)點（如果有頭結(jié)點，那么頭結(jié)點就是第0個結(jié)點），如果沒有頭結(jié)點的存在，那么就需要更改頭指針的值，而如果有頭結(jié)點的存在，頭指針的值是一直不用變的。下圖是帶有頭結(jié)點的鏈表的示意圖：

單鏈表的創(chuàng)建

在知道了單鏈表的基本形式之后，那自然也就需要創(chuàng)建一個單鏈表了，在創(chuàng)建一個單鏈表時，主要分為兩種創(chuàng)建方法，分別是頭插法和尾插法，下面分別就這兩種方法進(jìn)行敘述。

頭插法創(chuàng)建單鏈表

其創(chuàng)建鏈表所遵循的一個基本步驟如下所示：

從上圖可以看出來頭插法創(chuàng)建單鏈表的一個基本過程，同時可以看到，因為有頭結(jié)點的存在，在每次新增結(jié)點的時候，頭指針的值也是不變的，依據(jù)上述原理，寫出創(chuàng)建單鏈表的代碼，如下所示：

void?AddNodeHead(LinkList?*head,?int?value)
{
????ListNode*?Node?=?(ListNode*)malloc(sizeof(ListNode));
????if?(Node?==?NULL)
????????????return;

????/*?如果是首次插入結(jié)點，那么應(yīng)該創(chuàng)建頭結(jié)點?*/
????if?(*head?==?NULL)
????{
????????*head?=?(ListNode*)malloc(sizeof(ListNode));
????????if?(*head?==?NULL)
????????????????return;?????
????????(*head)->next?=?NULL;
????}
????Node->data?=?value;
????Node->next?=?NULL;
????(*head)->next?=?Node;
}
頭插法創(chuàng)建鏈表有一個特點就是，它所形成的鏈表的順序是反的，也就是說后插入的鏈表結(jié)點反而在前面，如果從第一個結(jié)點開始遍歷的話，那遍歷得到的元素的順序是倒過來的；那怎么樣才能使得鏈表的插入的順序和遍歷的順序一致呢？這個時候就需要引入尾插法創(chuàng)建單鏈表了。

尾插法創(chuàng)建單鏈表

尾插法也就正如其名字所表征的含義一樣，它的意思是從尾部逐漸將結(jié)點插入，其所遵循的一個基本過程如下圖所示：

代碼如下所示：

void?AddNodeTail(LinkList?*head,int?value)
{
????LinkList?Node?=?(LinkList)malloc(sizeof(ListNode));
????if?(Node?==?NULL)
????????????return;
????/*?創(chuàng)建一個臨時結(jié)點?*/
????LinkList?TempNode?=?NULL;

????/*?先創(chuàng)建頭結(jié)點?*/
????if?(*head?==?NULL)
????{
????????*head?=?(LinkList)malloc(sizeof(ListNode));
????????(*head)->next?=?NULL;
????}

????TempNode?=?(*head);
????Node->data?=?value;
????Node->next?=?NULL;
????while?(TempNode->next)
????{
????????TempNode?=?TempNode->next;
????}
????TempNode->next?=?Node;
}


按照順序插入一個結(jié)點

如果按照上述兩種方式構(gòu)建的鏈表是每個元素都是從前往后依次遞減的，現(xiàn)在要將一個數(shù)按照順序插入到鏈表中，那么其所遵循的基本原理示意圖如下所示：

根據(jù)上述的結(jié)點插入示意圖,寫出如下所示的代碼：

void?IncertNode(LinkList?head,?int?value)
{
????if?(head?==?NULL)
????????return;

????LinkList?temp?=?head;
????LinkList?Node?=?(LinkList)malloc(ListNode);
????if?(Node?==?NULL)
????????return;

????while?(temp->next?