關(guān)注小莊 頓頓解饞(●’?’●)

上篇回顧
我們上篇學習了本質(zhì)為數(shù)組的數(shù)據(jù)結(jié)構(gòu)—順序表，順序表支持下標隨機訪問而且高速緩存命中率高，然而可能造成空間的浪費，同時增加數(shù)據(jù)時多次移動會造成效率低下，那有什么解決之法呢？這就得引入我們鏈表這種數(shù)據(jù)結(jié)構(gòu)

一.何為鏈表

🏠 鏈表概念

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的 。

特點：物理結(jié)構(gòu)不一定連續(xù)，邏輯結(jié)構(gòu)連續(xù)

我們的鏈表結(jié)構(gòu)類似我們的火車，有頭有尾，中間每個結(jié)點被有序鏈接；與火車不同的是，鏈表的結(jié)點可能不是緊挨著的。

類似這樣，我們可以得出：
1.每個結(jié)點由數(shù)據(jù)和下一結(jié)點地址兩部分組成，而每個結(jié)點構(gòu)成了一個鏈表。
2.每個結(jié)點保存的是下一個結(jié)點的地址，這樣就能找到下一個結(jié)點，最后為空就停止
3.每個結(jié)點的地址不是連續(xù)的，可以體現(xiàn)出鏈表的物理結(jié)構(gòu)不一定連續(xù)

注：我們的結(jié)點一般是在堆區(qū)開辟的，因為此時你在程序結(jié)束前不free就會一直存在這塊空間，同時可根據(jù)需要靈活申請結(jié)點存數(shù)據(jù)。

這樣我們就可以用一個結(jié)構(gòu)體封裝每個結(jié)點：

typedef int Datatype;
typedef struct ListNode
{Datatype x;struct ListNode* next;
}Node;

注： 這里我們可以用typedef來重命名我們要存儲的數(shù)據(jù)類型，這樣對于不同數(shù)據(jù)的操作我們只要改typedef即可。

🏠 鏈表的分類

我們根據(jù)鏈表三個特點：1.帶頭不帶頭 2.單向還是雙向 3.循環(huán)還是不循環(huán) 組合成了如上的8種鏈表
本篇博客，我們要實現(xiàn)的是單向不帶頭不循環(huán)鏈表（單鏈表），至于什么是帶頭，雙向，循環(huán)我們下回雙鏈表再進行講解

---

二.單鏈表的實現(xiàn)

無頭+單向+不循環(huán)鏈表的增刪差改

🏠 鏈表的打印

• 鏈表數(shù)據(jù)的打印

這個接口就很好的體現(xiàn)了結(jié)點結(jié)構(gòu)保存指針的妙處了~

//鏈表的打印
void SLTPrint(Node* phead)
{asser(phead);Node* cur = phead;while (cur){printf("%d ", cur->x);cur = cur->next;}
}

🏠 鏈表的頭插和尾插

• 鏈表的尾插

對于鏈表的尾插要注意幾個問題：1.申請新結(jié)點 2.鏈表是否為空

解決方法：1.對于鏈表為空，直接讓申請的新節(jié)點作為頭節(jié)點 2.對于不為空的鏈表，首先要找到尾結(jié)點，再進行插入 3.對于申請新節(jié)點，我們后續(xù)的頭插也要使用我們可以封裝成一個接口，同時結(jié)點在堆區(qū)申請，調(diào)用完接口就不會釋放了。

//申請新節(jié)點
Node* BuyNode(Datatype x)
{Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc failed");return;}newnode->next = NULL;newnode->x = x;return newnode;
}void SLTPushBack(Node** pphead, Datatype x)
{assert(pphead);//申請新節(jié)點Node* newnode = BuyNode(x);//鏈表為空if (NULL == *pphead){*pphead = newnode;return;}//鏈表不為空：1.找尾巴結(jié)點2.插入新節(jié)點Node* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

思考：這里為什么傳二級指針？如果不傳二級指針呢？

void SLTNPushBack(Node* pphead, Datatype x)
{//申請新節(jié)點Node* newnode = BuyNode(x);//鏈表為空if (NULL == pphead){pphead = newnode;return;}//鏈表不為空：1.找尾巴結(jié)點2.插入Node* ptail = pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}
int main()
{Node* n1 = NULL;SLTNPushBack(n1,1);return 0;
}

經(jīng)過觀察傳一級指針版本的調(diào)用前后，我們發(fā)現(xiàn)n1這個指針變量存儲的值并沒發(fā)生改變，究其原因如下圖

• 鏈表的頭插
  ,
  *對于鏈表的頭插要注意的問題：1.申請新節(jié)點 2.鏈表釋放為空 *

解決方法：1.鏈表為空時，申請的新結(jié)點作為頭結(jié)點 2.鏈表不為空時，讓newnode->next指向原來頭節(jié)點,再讓newnode成為新的頭節(jié)點。

void SLTPushFront(Node** pphead, Datatype x)
{assert(pphead);//申請新節(jié)點Node* newnode = BuyNode(x);//鏈表為空if (NULL == *pphead){*pphead = newnode;return;}newnode->next = *pphead;*pphead = newnode;
}

🏠 鏈表的尾刪和頭刪

• 鏈表的尾刪
  
  對于鏈表的尾刪，我們需要分三種情況！

1.鏈表為空時此時刪不了直接退出
2.鏈表只有一個結(jié)點時，釋放頭節(jié)點，置phead為空
3.鏈表有多個結(jié)點時，我們需要遍歷鏈表找到尾結(jié)點的前置結(jié)點，先釋放尾節(jié)點再將前置結(jié)點的next置為空
注：不能先將前置結(jié)點的next置為空，再釋放尾結(jié)點，此時就找不到尾結(jié)點的地址了。

//鏈表的尾刪和頭刪
void SLTPopBack(Node** pphead)
{assert(pphead);assert(*pphead);//判斷鏈表不為空if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}Node* pre = *pphead;while (pre->next->next){pre = pre->next;}free(pre->next);pre->next = NULL;
}

• 鏈表的頭刪

對于鏈表的頭刪，分為兩種情況就可以了，因為有了phead很方便~

1.鏈表為空時，刪不了直接斷言下
2.鏈表不為空時，記錄頭節(jié)點的下一個位置，先釋放頭節(jié)點，再更換phead指向的位置

注：這里也不能先更新phead再釋放頭結(jié)點

void SLTPopFront(Node** pphead)
{assert(pphead);assert(*pphead);Node* pNext = (*pphead)->next;free(*pphead);*pphead = pNext;
}

🏠 鏈表指定位置的插入和刪除

1.鏈表為空時，無法插入
2.pos位置結(jié)點剛好是頭結(jié)點，直接頭插或頭刪
3.pos位置結(jié)點不是頭節(jié)點，需要找到pos位置的前置結(jié)點，記錄位置。

void NodeInpos(Node** pphead, Node* pos, Datatype x)
{assert(pphead);//pos不為空 -》 鏈表一定不能為空assert(pos);assert(*pphead);//建立一個新節(jié)點Node* newnode = BuyNode(x);//pos剛好是頭結(jié)點的情況if (*pphead == pos){//運用頭插NodeinFront(pphead,x);return;}//pos剛好不是頭結(jié)點//1.先找出pos前面的結(jié)點pre  2.newnode->next = pre->next 3.pre-<next = newnodeNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}newnode->next = pre->next;pre->next = newnode;
}void NodeDelpos(Node** pphead, Node* pos)
{assert(pphead);assert(pos);assert(*pphead);//pos剛好是第一個結(jié)點 執(zhí)行頭刪if (*pphead == pos){NodeDelFront(pphead);return;}//pos不是第一個結(jié)點 1.先找到那個pos前面結(jié)點pre 2.pre->next = pos->next 3.freeNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = pos->next;free(pos);pos = NULL;
}

🏠 鏈表的查找

Node* NodeFind(Node** phead, Datatype x)
{assert(phead);//遍歷鏈表Node* pcur = *phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//找不到則返回NULL
}

這里建議用一個臨時變量來遍歷~

🏠 鏈表的銷毀

void NodeDestroy(Node** pphead)
{assert(pphead);assert(*pphead);//1.創(chuàng)一個臨時變量存pcur->next的地址Node* pcur = *pphead;while (pcur){Node* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

注： 這里要保存好下一個結(jié)點地址，銷毀后就能繼續(xù)遍歷

三.單鏈表的分析以及與順序表的比較

🏠 單鏈表的優(yōu)缺點

通過實現(xiàn)我們的單鏈表，我們發(fā)現(xiàn)單鏈表有以下優(yōu)點

1.單鏈表不存在空間浪費(根據(jù)需求靈活在堆上申請新結(jié)點)
2.單鏈表的任意插入和刪除效率高
（分析: 這里是已經(jīng)確定插入的位置，對于鏈表只需改變指針的指向就能實現(xiàn)插入和刪除，時間復雜度是O(1)，而數(shù)組插入和刪除需要遍歷數(shù)組，時間復雜度是O(N)）

單鏈表也不是萬能的，它在一些應用場景也發(fā)揮不出來作用

1.不支持隨機訪問
2.緩存命中率低
3.查找效率低

總結(jié)：鏈表適用于頻繁任意插入和刪除的場景，不適用于隨機訪問和查找

🏠 單鏈表與順序表的比較

單鏈表	順序表
物理空間不一定連續(xù)	物理空間一定連續(xù)
不支持隨機訪問	支持下標隨機訪問
插入和刪除效率高 O(1)	插入和刪除效率低 O(N)
緩存命中率低	緩存命中率高
無空間的浪費	可能造成數(shù)據(jù)丟失和空間浪費
緩存利用率高

綜上 我們可以根據(jù)場景需求選擇不同的結(jié)構(gòu)，靈活運用數(shù)據(jù)~

---

本次分享到這結(jié)束了，下篇我們將講解雙向鏈表，不妨來個一鍵三連捏