目錄

一.? 鏈表的定義

? ? ? ? 1.鏈表的結(jié)構(gòu).

? ? ? ? 2.為啥要存在鏈表及鏈表的優(yōu)勢.

二. 無頭單向鏈表的常用接口

? ? ? ? 1.頭插\尾插

? ? ? ? 2.頭刪\尾刪

? ? ? ? 3.銷毀鏈表/打印鏈表

? ? ? ? 4.在pos位置后插入一個值

? ? ? ? 5.消除pos位置后的值

? ? ? ? 6.查找鏈表中的值并且返回它的地址

? ? ? ? 7.創(chuàng)建一個動態(tài)開辟的結(jié)點

三.順序表與鏈表的優(yōu)缺點對比.

---

? ? ? ? 文章開始->:

? ? 一.鏈表的定義

? ? ? ? 首先在學(xué)習(xí)單鏈表之前我們已近學(xué)過順序表這一數(shù)據(jù)結(jié)構(gòu)了，我們知道在使用順序表的時候，當(dāng)我們空間不夠的時候我們需要擴容，還有在我們進行頭插和頭刪的時候我們需要移動元素，這時進行這些操作的時候是非常浪費時間的，并且擴容的時候還有可能浪費一定的空間當(dāng)然這也是順序表的缺點，而為了解決這些麻煩我們就弄出來了另外一個數(shù)據(jù)結(jié)構(gòu)-->(鏈表)。

? ? ? ? 鏈表的定義:在邏輯結(jié)構(gòu)上元素是連續(xù)的，但是實際的物理結(jié)構(gòu)上鏈表是非連續(xù)，非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序其實是通過指針來連接的。

? ? ? ? 下面就是正常的邏輯結(jié)構(gòu)

?

? ? ? ? 所以鏈表這種結(jié)構(gòu)可以很簡單的解決順序表的問題，他在管理數(shù)據(jù)的時候并不需要擴容，而是當(dāng)我們需要空間的時候他會取開辟一塊空間然后我們只需要去改變指針的指向就可以將數(shù)據(jù)給連接起來了，這也省去了移動元素的時間。

? ? ? ? 總結(jié)單鏈表的優(yōu)點：單鏈表在使用內(nèi)存空間的時候并不需要想順序表那樣進行擴容，而是我們需要空間的時候會自動去內(nèi)存中開辟一塊空間，也不需要再插入元素的時候移動元素，我們只需要改變指針的指向就可以實現(xiàn)鏈表邏輯上的順序管理了。

? ? ? ? 鏈表其實最大的好處就是可以進行頭插和頭刪.

? ? ? ? 下圖就是我們插入元素時候的操作:->

????????

?這樣我們就不需要移動元素只需要改變指針的指向就行了。

????????

接下來就是我們的重點進入常用接口的詳細講解-->

二.無頭單鏈表的常用接口

? ? ? 首先我們要理解的就是無頭:所謂的無頭就是我們并沒有先申請一個結(jié)點，而是我們的頭指針直接指向了第一個節(jié)點，如果鏈表是空的那么我們我們的頭指針指向的是空指針 。

? ? ? ??首先我們來看一看鏈表的結(jié)構(gòu)

? ? ? ? ? ?在邏輯上-->

? ? ? ? 在實際上-->

????????

? ? ? ? ?實際上我們內(nèi)存當(dāng)中并沒有指針指向的說法，只是我們?yōu)榱朔奖憷斫怄湵磉@一數(shù)據(jù)結(jié)構(gòu)而引入進來的。

鏈表定義的代碼如下：

?typedef int SlistDataType;
????typedef struct Slist
{
?? ?struct Slist* next;
?? ?SlistDataType data;
}ST;

1.銷毀鏈表/打印鏈表:? ?在這里我們要注意就是實參與形參的區(qū)別不然我們的操作可能會出現(xiàn)問題，打印的話我們直接遍歷就行。

????????這個接口是必須要有，因為我們在創(chuàng)建鏈表之前肯定得先有鏈表這一結(jié)構(gòu)，而銷毀鏈表是為了防止我們程序出現(xiàn)內(nèi)存泄漏的問題。

? ? ? ? 銷毀鏈表：因為我們所申請的空間是在堆區(qū)上開辟的空間，而堆區(qū)上開辟的空間需要我們自己來釋放空間，并且鏈表所開辟的空間并不是一個連續(xù)塊的空間，所以我們需要來遍歷鏈表這樣保證我們將我們所開辟的空間來進行釋放完整，防止內(nèi)存泄漏。

????????

void DestorySlist(STNode* plist)
{assert(plist);//這里我們需要一個一個的刪除鏈表的結(jié)點while (plist != NULL){STNode* newplist = plist->next;//存放下一個結(jié)點free(plist);plist = newplist;}}

? ? ? ? 打印鏈表：我們只需要遍歷到結(jié)點為空的情況就行了

? ? ? ? 下面是打印的代碼：

????????

void PrintSlist(STNode* plist)
{assert(plist);while (plist != NULL){printf("%d->", plist->data);plist = plist->next;}printf("NULL\n");
}

? ? ?

? 2.動態(tài)開辟一個結(jié)點:在我們進行插入有關(guān)操作的時候我們需要申請一塊空間來存放要插入的值，所以這一步操作也是不能省略的:

? ? ? ? 我們直接上代碼:

????????

STNode* BuySlistNode(SlistDataType x)
{STNode* newnode = (STNode*)malloc(sizeof(STNode));//判斷開辟的空間成功沒if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//這樣設(shè)計可以使得我們最后一個結(jié)點不需要在進行單獨的設(shè)空return newnode;}

?3.尾插\頭插:這里我們需要用到二級指針，因為我們知道改變結(jié)構(gòu)體需要結(jié)構(gòu)體指針，而改變結(jié)構(gòu)體指針，我們需要結(jié)構(gòu)體指針的指針，即二級指針來使用。當(dāng)我們在進行尾插的第一個插入的時候，我們需要改變結(jié)構(gòu)體指針，所以得用二級指針。,而頭插每次都需要改變結(jié)構(gòu)體指針

? ? ? ? 下面代碼:尾插

????????

//注意二級指針
void PushBackSlist(STNode** pplist, SlistDataType x)
{STNode* newnode = BuySlistNode(x);if (*pplist == NULL){//插入第一個*pplist = newnode;}else{STNode* tail = *pplist;//我們得先找尾指針while(tail->next!=NULL){ tail = tail->next;}tail->next = newnode;}
}

? ? ? ? 尾插的圖片：

? ? ?

?

? 頭插代碼:在這里我們需要注意的是在進行改變指針的時我們需要先進行將新節(jié)點的next指針先指向頭，讓后在將頭改變，如果反了的話我們會使newnode->next指向自身。

????????

void PushFrontSlist(STNode** pplist, SlistDataType x)
{STNode* newnode = BuySlistNode(x);newnode->data = x;newnode->next = *pplist;*pplist = newnode;}

????????頭插圖：

4.頭刪/尾刪

? ? ? ? 頭刪：我們首先在刪除之前判斷鏈表是否為空，如果為空我們就會報錯，如果不為空則會繼續(xù)進行操作，在這里當(dāng)鏈表中只有一個結(jié)點的時候，那么我們就需要修改結(jié)構(gòu)體指針了。

? ? ? ? 下面是代碼：

void PopFrontSlist(STNode** pplist)
{//為空assert(*pplist);//一個結(jié)點if ((*pplist)->next == NULL){STNode* del = *pplist;free(del);*pplist = NULL;}//多個結(jié)點else{STNode* del = *pplist;STNode* newnode = (*pplist)->next;free(del);*pplist = newnode;}
}

? ? ? ? 測試時圖片：

????????

? ? ? ? ?尾刪：這里也要先判斷鏈表是否為空，然后如果只有一個元素我們需要改變結(jié)構(gòu)體指針，其他的我們則只需要將前面一個的指針指向NULL，就行了。

? ? ? ? 尾刪代碼：

????????

void PopBackSlist(STNode** pplist)
{//判斷是否為空assert(*pplist);//一個結(jié)點if ((*pplist)->next == NULL){STNode* del = *pplist;free(del);*pplist = NULL;}else{STNode* cur = *pplist;//找前一個while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

? ? ? ? 尾刪測試：

????????

?????????5.鏈表的查找接口:如果找到了則返回這個值的地址，如果沒找到則打印未找到，思路：我們只需要遍歷數(shù)組即可。

STNode* FindSlist(STNode* plist, SlistDataType x)
{assert(plist);STNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}printf("未找到\n");return NULL;
}

? ? ? ? 測試：

????????

? ? ? ? ?6.在pos位置后插入，與消除pos位置后的接口

? ? ? ? 插入：首先我們得判斷pos是否有意義，如果有則代表有意義，我們就保存pos位置后的結(jié)點，然后pos->next=newnode，newnode->next=posafter;

? ? ? ? 代碼：

void InsertafterSlist( STNode* pos, SlistDataType x)
{assert(pos);STNode* posafter = pos->next;STNode* newnode = BuySlistNode(x);pos->next = newnode;newnode->next = posafter;
}

? ? ? ? 測試：

????????????????

? ? ? 刪除pos后面的值：我們先判斷pos是否有意義，有意義直接將pos后面的free掉，pos->next=NUll;

? ? ? ? 代碼:

????????

void EraseafterSlist(STNode* pos)
{assert(pos);STNode* posafter = pos->next;pos->next =posafter->next ;free(posafter);}

? ? ? ? ?測試圖：

????????

? ? ? ? 注意：這后面三個接口通常都是一起使用的。

? ? ? ? 到這里我們常用的接口已近講解完畢了，接下來進行最后一部分的講解--->

? ? 三：順序表與鏈表優(yōu)缺點對比

? ? ? ? 順序表的優(yōu)點：順序表可以隨機訪問開辟空間的地址，且在內(nèi)存當(dāng)中是連續(xù)的一塊空間，，支持隨機訪問，緩存利用率比較高。

? ? ? ? ? ? ? ? ? ? ? ?缺點：再進行插入操作的時候需要擴容，而擴容其實底層原理是很麻煩的，這里可以看我前面寫過的動態(tài)內(nèi)存開辟的那一張設(shè)計realloc擴容，這里就不詳細介紹了，且擴容之后還會浪費空間，其次是在進行頭刪/頭插的時候我們需要移動元素，這里會導(dǎo)致很多的空間被持續(xù)使用，浪費了大量空間，而且擴容可能擴的非常多，任意插入與刪除元素的效率低，時間復(fù)雜度為O(n).

? ? ? ? 順序表適合頻繁訪問的場景。

? ? ? ? 鏈表的優(yōu)點：再進行任意位置插入與刪除的時候，不需要挪動元素時間復(fù)雜度為O(1),也不需要擴容操作，只需新增一個結(jié)點就行了，然后改變指針的指向就行了。????????

? ? ? ? 缺點：就是不能隨機訪問內(nèi)存。且緩存利用率低。

? ? ? ? 鏈表適用于任意位置插入與刪除的情況。

? ? ? ? 總而言之：數(shù)據(jù)結(jié)構(gòu)各有各的優(yōu)點，也各有各的缺點，這些數(shù)據(jù)結(jié)構(gòu)適合應(yīng)用的場景不同而已。

? ? ? ? ? ? ? ? ?~~本章結(jié)束，感謝大家的耐心觀看，如果你覺得有用的話，可以點個贊哦！

????????????????

?