概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
成都創(chuàng)新互聯(lián)公司主要從事成都做網(wǎng)站、成都網(wǎng)站建設、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務蒙山,10余年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:028-86922220這與我們之前所了解的數(shù)組不同，數(shù)組在內(nèi)存中開辟一塊連續(xù)的空間，根據(jù)一個元素的位置就可以輕易地找到數(shù)組中其余元素的地址，而鏈表不同，鏈表每一個節(jié)點（鏈表的基本組成單位，可以理解為數(shù)組的一個元素）的地址并不是連續(xù)的，為了找到可以訪問鏈表的每一個節(jié)點，我們需要在每個節(jié)點存儲下一個節(jié)點的地址，也就是用一個指針來指向下一個節(jié)點。下圖可以幫助我們理解鏈表的結(jié)構(gòu)：
鏈表的每個節(jié)點可以理解為由兩部分組成：節(jié)點存儲的數(shù)據(jù)（data）和指向下一個節(jié)點地址的指針（next）。其中，鏈表的最后一個節(jié)點（尾節(jié)點）的指針（next）為NULL。
二、鏈表的分類實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1.根據(jù)鏈表的指向可以分為：單向鏈表和雙向鏈表
單向鏈表就是我們最開始介紹的，每個節(jié)點由data和next組成。而雙向鏈表每個節(jié)點由data、next和prev(指向上一個節(jié)點的指針)；雙向鏈表的解決了鏈表插入刪除節(jié)點時無法保存上一個節(jié)點地址的麻煩。（這在第三部分用C語言實現(xiàn)鏈表可以感受到）
2.根據(jù)鏈表是否帶頭可以分為：帶頭鏈表和不帶頭鏈表
不帶頭鏈表就是我們最開始介紹的，第一個節(jié)點（頭節(jié)點）存貯有效數(shù)據(jù)。而帶頭節(jié)點的頭節(jié)點是一個不存儲有效數(shù)據(jù)的節(jié)點，在有的教材上稱為帶哨兵位的頭。
3.根據(jù)鏈表尾節(jié)點next的指向可以分為：單鏈表和循環(huán)單鏈表
循環(huán)鏈表的特點是尾節(jié)點的next指向第一個節(jié)點，而不是NULL。
4.最常用的兩種鏈表1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2.帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。
接下來我們用C語言來實現(xiàn)無頭單項非循環(huán)鏈表。
1.鏈表的創(chuàng)建根據(jù)鏈表對結(jié)構(gòu)的介紹，我們知道鏈表的最基本單位是節(jié)點，每個節(jié)點由兩個變量（data和next）組成，因此，節(jié)點對應的類型應該是結(jié)構(gòu)體，結(jié)構(gòu)體成員分別是data和next。
重慶分公司
重慶分公司
#define SLTDataType int
typedef struct SinglyListNode
{
SLTDataType data;
struct SinglyListNode* next;
}SLTNode;
從圖中我們發(fā)現(xiàn)，尾插進行的操作其實是三步：創(chuàng)建新節(jié)點（newnode），找到原鏈表的尾節(jié)點（tail）,將newnode插入到tail之后。
由于在之后我們要經(jīng)常用到創(chuàng)建新節(jié)點，所以我們將這個步驟封裝成一個函數(shù)：BuyListNode
//x是插入節(jié)點的data值
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}接下來，我們要尋找原鏈表的尾節(jié)點，定義一個tail從鏈表的第一個節(jié)點開始，逐步向后移動，直到最后一個節(jié)點，即tail->next==NULL時，tail即為尾節(jié)點。然后，將newnode插入到tail之后，也就是tail->next = newnode。
當然，我們對tail進行了訪問，就要考慮tail會不會為NULL，也就是鏈表為空的情況，這時候，只要直接將newnode賦給鏈表就行。
//為什么是SLTNode** 這個二級結(jié)構(gòu)體指針呢？
void SinglyListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyListNode(x);
//if SinglyList is null
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//step 1:find tail node
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//step 2:add new node
tail->next = newnode;
}
}要注意，我們調(diào)用這個函數(shù)的方式應該如下：
void TestSinglyList1()
{
SLTNode* plist = NULL;
SinglyListPushBack(&plist, 1);
SinglyListPushBack(&plist, 2);
}我們傳入的是一個結(jié)構(gòu)體指針plist，想要改變plist，不能直接在SinglyListPushBack內(nèi)部使用一個一級的結(jié)構(gòu)體指針，因為這時，函數(shù)里的參數(shù)是形參，形參的改變不影響實參plist。想到用swap函數(shù)交換兩個整形a、b的值時，我們傳入a、b的地址：swap(&a,&b)。同樣的，我們要傳入plist的地址(&plist)，一個一級指針的地址是一個二級指針，所以SinglyListPushBack調(diào)用的參數(shù)為SLTNode** pphead。
（2）在鏈表的頭部插入數(shù)據(jù)--SinglyListPushFront
頭插比起尾插更簡單，只需將newnode放在原鏈表第一個節(jié)點之前：newnode->next = *pphead，然后將鏈表的頭節(jié)點更改為newnode，*pphead = newnode。
void SinglyListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
尾刪需要通過和尾插一樣的方式找到尾節(jié)點tail，然后將倒數(shù)第二個節(jié)點作為新的尾節(jié)點。但是我們只根據(jù)tail是無法找到上一個節(jié)點的，因此我們要額外定義一個prev來記錄上一個節(jié)點。最后，將倒數(shù)第二個節(jié)點作為新的尾節(jié)點：prev->next = NULL。
同樣的，我們要注意prev和tail會不會為NULL的情況，當tail為NULL，鏈表為空；當prev為NULL，鏈表只有一個節(jié)點，對這兩種情況單獨討論即可。
void SinglyListPopBack(SLTNode** pphead)
{
//鏈表為空
if (*pphead == NULL)
return;
//鏈表只有一個節(jié)點
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//鏈表有兩個及以上節(jié)點
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
頭刪要進行的操作與頭插類似，都是改變plist的指向，只需要讓plist指向第二個節(jié)點即可。當然還是要注意考慮當*pphead為NULL，也就是鏈表為空時，就不用刪除了。
為了更方便地釋放第一個節(jié)點，我們額外定義一個next來記錄第二個節(jié)點，next = (*pphead)->next，接著釋放*pphead，最后將next賦給*pphead。（注意順序，不要提前釋放頭節(jié)點，否則找不到第二個節(jié)點）
void SinglyListPopFront(SLTNode** pphead)
{
if (*pphead==NULL)
return;
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}因為鏈表不適合二分查找、排序等操作，所以只要簡單地從第一個節(jié)點開始遍歷到尾節(jié)點，如果找到了指定數(shù)據(jù)，就返回該節(jié)點，如果沒有指定數(shù)據(jù)，則返回NULL。
SLTNode* SinglyListFind(SLTNode* phead, SLTDataType key)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == key)
return cur;
cur = cur->next;
}
return NULL;
}在刪除某個節(jié)點時，記要刪除的節(jié)點為pos，pos有SinglyListFind確定，先給定一個值key，由SinglyListFind找到值為key的節(jié)點后返回給pos，然后刪除該節(jié)點。
刪除這一步將pos的前一個節(jié)點（prev）連接到pos后一個節(jié)點上:prev->next = pos->next。由于我們無法直接由pos得到prev，所以每一次都要記錄下來pos前的一個節(jié)點。并且，當pos為頭節(jié)點時prev為NULL，我們只需要將進行之前頭刪的操作：*pphead = (*pphead)->next。
void SinglyListErase(SLTNode** pphead, SLTNode* pos)
{
if (*pphead != pos)
{
SLTNode* tmp = *pphead;
while (tmp->next != pos)
{
tmp = tmp->next;
}
tmp->next = pos->next;
}
else
*pphead = (*pphead)->next;
free(pos);
pos = NULL;
}? 由于在某個節(jié)點（pos）之前插入存在一個節(jié)點需要記錄之前的節(jié)點，時間復雜度較高，我們只考慮在某個節(jié)點之后插入一個節(jié)點的情況，這里的pos和前面的刪除一樣，都來源于SinglyListFind。
在往尾部插入節(jié)點時，不用考慮插入的位置，只要將pos的next指向newnode，再將newnode的next指向原鏈表中pos的下一個節(jié)點。
void SinglyListInsert(SLTNode* pos, SLTDataType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}void SinglyListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
