定義

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

單鏈表

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

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

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

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

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

單鏈表的創(chuàng)建

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

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

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

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

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

????/*?如果是首次插入結(jié)點(diǎn)，那么應(yīng)該創(chuàng)建頭結(jié)點(diǎn)?*/
????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)建鏈表有一個(gè)特點(diǎn)就是，它所形成的鏈表的順序是反的，也就是說后插入的鏈表結(jié)點(diǎn)反而在前面，如果從第一個(gè)結(jié)點(diǎn)開始遍歷的話，那遍歷得到的元素的順序是倒過來的；那怎么樣才能使得鏈表的插入的順序和遍歷的順序一致呢？這個(gè)時(shí)候就需要引入尾插法創(chuàng)建單鏈表了。

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

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

代碼如下所示：

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

????/*?先創(chuàng)建頭結(jié)點(diǎn)?*/
????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;
}


按照順序插入一個(gè)結(jié)點(diǎn)

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

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

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?