引言
上篇博客已經(jīng)介紹了順序表的實現(xiàn)：【數(shù)據(jù)結(jié)構(gòu)】詳解順序表。最后在里面也談及了順序表結(jié)構(gòu)的缺陷，即效率低，空間浪費等等問題，那么為了解決這些問題，于是乎我們引入了鏈表的概念，下面將對鏈表結(jié)構(gòu)進行講解
一、鏈表的介紹
首先肯定會問，到底什么是鏈表？鏈表的概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)，非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
在結(jié)構(gòu)上其與火車的結(jié)構(gòu)相似，分為一個個節(jié)點，再將每個節(jié)點連接起來，就形成了一個鏈表，其大致結(jié)構(gòu)如下：
但還要幾點需要注意：
- 鏈式結(jié)構(gòu)在邏輯上是連續(xù)的，但在物理空間上不一定是連續(xù)的；
- 這些節(jié)點一般是在堆上申請出來的，即使用
malloc函數(shù)來動態(tài)申請空間；- 每當需要增加一個數(shù)據(jù)時，便可申請一段空間，空間可能連續(xù)也可能不連續(xù)。
二、鏈表的幾種分類
鏈表的結(jié)構(gòu)大致可以分為8類，即：帶頭/不帶頭單向鏈表，帶頭/不帶頭雙向鏈表，帶頭/不帶頭單向循環(huán)鏈表，帶頭/不帶頭雙向循環(huán)鏈表。 今天我所介紹的是其中最簡單的結(jié)構(gòu)和最復(fù)雜的結(jié)構(gòu)：
- 單向不帶頭不循環(huán)鏈表：
單向不帶頭不循環(huán)鏈表結(jié)構(gòu)簡單，但實現(xiàn)起來并不簡單且復(fù)雜度高，所以一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。- 雙向帶頭循環(huán)鏈表：
帶頭雙向循環(huán)鏈表結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。表面上看這結(jié)構(gòu)十分的復(fù)雜，但在后面實現(xiàn)函數(shù)時會發(fā)現(xiàn)這種結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)起來反而更簡單了，復(fù)雜度也大大降低。
三、不帶頭單鏈表的一些常用接口
定義如下結(jié)構(gòu)體，表示鏈表的一個節(jié)點:
typedef int SLDataType;
typedef struct SlistNode
{
SLDataType val;//所需保存的數(shù)據(jù)
struct SListNode* next;//結(jié)構(gòu)體指針，指向下一個節(jié)點的地址
}SLNode;
3.1 動態(tài)申請一個節(jié)點
為了使鏈表在各個函數(shù)中都可以使用，所以我們需要動態(tài)開辟內(nèi)存來創(chuàng)建節(jié)點，再通過指針將他們相連接。在
CreatNode()函數(shù)中我們創(chuàng)建節(jié)點并將他們初始化：
//動態(tài)申請節(jié)點
SLNode* CreatNode(SLTDateType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
//檢測
if(newnode == NULL)
{
perror("CreatNode()::malloc");
return;
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
3.2 尾插數(shù)據(jù)
根據(jù)一般邏輯，我們想要尾插那就要先創(chuàng)建新節(jié)點并找到尾節(jié)點。那么我們定義指針
tail，然后利用循環(huán)找尾節(jié)點再鏈接新節(jié)點tail->next = newnode，另外還要額外判斷鏈表為空的情況，此情況直接尾插即可，具體如下：
//尾插
void SLPushBack(SLNode** pplist, SLDateType x)
{
SLNode* newnode = CreatNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
//找尾
SLNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
//鏈接
tail->next = newnode;
}
}
3.3 頭插數(shù)據(jù)
頭插就比較簡單了，只需要注意一點：不額外定義變量時，要先將新節(jié)點鏈到鏈表，即
newnode->next = *pplist，然后再改頭節(jié)點，即*pplist = newnode，如下：
void SLPushFront(SLNode** pplist, SLDateType x)
{
assert(pplist);
SLNode* newnode = CreatNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
3.4 尾刪數(shù)據(jù)
同樣想要尾刪，那就必須先找到尾節(jié)點，然后釋放空間。但釋放完空間后，上一個節(jié)點的
next仍然指向釋放空間的地址，這就可能造成越界訪問，野指針問題。所以我們還需要記錄尾節(jié)點的上一個節(jié)點tailPrev，然后通過這個指針將此節(jié)點next置為NULL。此外還需用assert()檢測鏈表不為NULL，分類討論鏈表只有一個節(jié)點和有多個節(jié)點的情況。如下：
//尾刪
void SLPopBack(SLNode** pplist)
{
assert(pplist && *pplist);
SLNode* tailPrev = NULL;
SLNode* tail = *pplist;
// 1.只有一個節(jié)點
if (tail->next == NULL)
{
free(tail);
*pplist = NULL;
}
// 2.兩個及以上的節(jié)點
else
{
//找尾及上一個節(jié)點
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
tailPrev->next = NULL;
}
}
3.5 頭刪數(shù)據(jù)
頭刪數(shù)據(jù)時，鏈表同樣不能為空，另外頭刪無需判斷鏈表節(jié)點數(shù)問題，這就比較容易實現(xiàn)了：
void SLPopFront(SLNode** pplist)
{
//不為空
assert(pplist && *pplist);
//記錄第一個節(jié)點
SLNode* first= *pplist;
*pplist = (*pplist)->next;
free(first);
}
3.6 查找數(shù)據(jù)
給定一個
val，再鏈表中向后尋找，找到時返回此節(jié)點地址pos，未找到返回NULL。我們只需定義一個結(jié)構(gòu)體指針SLNode* cur = plist;，讓他向后走，找到val時返回cur，直到cur = NULL時循環(huán)結(jié)束并返回NULL。因為這里無需改變鏈表指向，所以可以直接傳一級指針。
SLNode* SLFind(SLNode* plist, SLDateType x)
{
SLNode* cur = plist;
while (cur)
{
//尋找val
if (cur->val == x)
return cur;
cur = cur->next;
}
return NULL;
}
3.7 pos位置后插入數(shù)據(jù)
如下圖，先創(chuàng)建一個節(jié)點
newnode，然后將newnode->next指向pos位置的下一個節(jié)點，最后將pos->next指向新節(jié)點。
當然pos != NULL。
//指定位置插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{
assert(pos);
SLNode* newnode = CreatNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
3.8 刪除pos位置數(shù)據(jù)
先通過循環(huán)找到
pos前一個節(jié)點地址posPrev，和后一個節(jié)點地址posNext，然后釋放pos節(jié)點，鏈接posPrev和posNext。
同樣pos != NULL，還有一點是當pos為頭節(jié)點，就相當于頭刪，但無需判斷，同樣適用。
void SLErase(SLNode* pos, SLNode** pplist)
{
assert(pos && pplist);
SLNode* posPrev = *pplist, *posNext = pos->next, *cur = *pplist;
//找pos前一個節(jié)點
while(cur != pos)
{
posPrev = cur;
cur = cur->next;
}
//鏈接
posPrev->next = posNext;
free(pos);
}
3.9 釋放空間
因為這是一個鏈式結(jié)構(gòu)，且每個節(jié)點是
malloc動態(tài)開辟的，所以最后要將所以節(jié)點釋放，否則會造成內(nèi)存泄漏問題。只需定義一個結(jié)構(gòu)體指針SLNode* cur = *pplist，讓他向后依次釋放節(jié)點，直到cur = NULL。
void SLDestroy(SLNode** pplist)
{
assert(pplist);
SLNode* cur = *pplist;
while(cur)
{
//記錄下一個節(jié)點
SLNode* next = cur->next;
free(cur);
cur = next;
}
}
四、帶頭雙向鏈表的常見接口
通過上面對單向不循環(huán)鏈表的介紹，我們不難發(fā)現(xiàn)其實單鏈表的尾插，尾刪和指定位置刪除其實效率是不高的，時間復(fù)雜度為
O(n)。而雙向帶頭循環(huán)鏈表是不存在這個問題的，且因為鏈表帶頭節(jié)點的原因，在函數(shù)傳參是無需用到二級指針，在實現(xiàn)函數(shù)時也會發(fā)現(xiàn)很多時候也不需要單獨判斷鏈表沒節(jié)點的情況，因為頭節(jié)點本身就是一個節(jié)點，這也大大降低了代碼的難度。
雙向帶頭循環(huán)鏈表的每個節(jié)點都包含兩個指針：一個指向上一個節(jié)點，一個指向下一個節(jié)點。那么便可這樣設(shè)計節(jié)點：
typedef int DataType;
//節(jié)點設(shè)計
typedef struct DListNode
{
DataType val;
struct DListNode* _prev;//指向上一個節(jié)點的指針
struct DListNode* _next;//指向下一個節(jié)點的指針
}DLNode;
4.1創(chuàng)建頭節(jié)點（初始化）
頭節(jié)點和其他節(jié)點的結(jié)構(gòu)是相同的，就相當于鏈表自帶一個節(jié)點，并將此節(jié)點初始化成以下格式：
DLNode* InitDLNode(DLNode* phead)
{
//創(chuàng)建
DLNode* head = (DLNode*)malloc(sizeof(DLNode));
if (head == NULL)
{
perror("InitDLNode()::malloc");
return;
}
//形成循環(huán)結(jié)構(gòu)
head->_prev = head;
head->_next = head;
head->val = -1;
return head;
}
4.2pos位置前插入
對于
pos位置之前插入，可以先通過pos->_prev找到前一個節(jié)點的地址，然后再進行插入操作。因為是雙向循環(huán)鏈表的原因，找pos前一個節(jié)點也不需要循環(huán)，時間復(fù)雜度只有O(1)。
事實上當鏈表無有效節(jié)點（即只有頭節(jié)點）也不需要單獨判斷，這樣降低了代碼難度，具體實現(xiàn)代碼如下：
//指定位置插入
void DLNodeInsert(DLNode* pos, DataType x)
{
assert(pos);
DLNode* posPrev = pos->_prev;//pos前一個節(jié)點
DLNode* newnode = CreatNode(x);//創(chuàng)建新節(jié)點
//鏈接
posPrev->_next = newnode;
newnode->_prev = posPrev;
pos->_prev = newnode;
newnode->_next = pos;
}
4.3刪除pos位置數(shù)據(jù)
刪除
pos位置的數(shù)據(jù)，我們可以通過pos->_prev找到上一個節(jié)點的地址，再通過pos->_next找到下一個節(jié)點的地址。然后將這兩個節(jié)點鏈接起來，并釋放pos節(jié)點，如下：
當只有一個頭節(jié)點時我們還需額外判斷一下，代碼如下：
void DLNodeErase(DLNode* pos)
{
assert(pos);
assert(pos->_next != pos);//不能為頭節(jié)點
DLNode* posPrev = pos->_prev, * posNext = pos->_next;
//鏈接
posPrev->_next = posNext;
posNext->_prev = posPrev;
free(pos);
}
4.4其他
還有頭刪/插，尾刪/插這四個函數(shù)，但這四個函數(shù)并不需要額外實現(xiàn)，因為：
頭插/刪可以當作pos = phead->_next的指定位置插入/刪除，尾刪也可以當作pos = phead->_prev的指定位置刪除，尾插則是pos = phead的位置。頭/尾刪這兩個pos分別代表頭節(jié)點的后一個和前一個，且判斷assert(phead != phead->_next)也是必要的，這里就不代碼實現(xiàn)了。
五、總結(jié)
對比于順序表我們發(fā)現(xiàn)鏈表有很多優(yōu)點，也有一些缺點：
優(yōu)點：文章來源：http://www.zghlxwxcb.cn/news/detail-751987.html
- 鏈表的空間浪費較小，按需開辟空間；
- 任意位置插入和刪除數(shù)據(jù)效率更高，實現(xiàn)了
O(1)時間復(fù)雜度；缺點：文章來源地址http://www.zghlxwxcb.cn/news/detail-751987.html
- 不支持隨機訪問數(shù)據(jù)（致命缺陷）；
- 每個節(jié)點還要存儲鏈接下一個節(jié)點的指針，這也會造成一點空間浪費；
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】詳解鏈表結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]——鏈表詳解](https://imgs.yssmx.com/Uploads/2024/02/709350-1.png)
