前言
上一篇文章講述了線性表中的順序表，這篇文章講述關(guān)于鏈表的定義、類別、實(shí)現(xiàn)、多種不同鏈表的優(yōu)缺點(diǎn)和鏈表與順序表的優(yōu)缺點(diǎn)。
關(guān)于上一篇文章的鏈接：線性表之順序表
一、鏈表的定義
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
二、鏈表的分類
1. 單向和雙向
2. 帶頭和不帶頭
3. 循環(huán)和不循環(huán)
4. 常用（無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表）
三、無頭單向非循環(huán)鏈表的接口及實(shí)現(xiàn)
1. 單鏈表的接口
#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 動(dòng)態(tài)申請一個(gè)節(jié)點(diǎn)
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestroy(SListNode* plist);
2. 接口的實(shí)現(xiàn)
#include "slist.h"
SListNode* BuySListNode(SLTDateType x)
{
//創(chuàng)造新節(jié)點(diǎn)
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
//新節(jié)點(diǎn)初始化
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//這里使用二級指針的原因是：
//若鏈表為空，需要改變的就是結(jié)構(gòu)體指針，需要結(jié)構(gòu)體指針的地址
//若傳入的是一級指針，這里傳入的只是臨時(shí)拷貝，無法改變函數(shù)外的變量
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
//若不為空，需要改變的是結(jié)構(gòu)體，只需要結(jié)構(gòu)體的指針
else
{
SListNode* tail = *pplist;
SListNode* newnode = BuySListNode(x);
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPrint(SListNode* plist)
{
while (plist)
{
printf("%d->", plist->data);
plist = plist->next;
}
printf("NULL");
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//這里使用二級指針的原因是：每次頭刪都需要改變頭節(jié)點(diǎn)
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
//無頭單鏈表尾刪刪除節(jié)點(diǎn)的時(shí)候有三種情況
void SListPopBack(SListNode** pplist)
{
//沒有節(jié)點(diǎn)
assert(*pplist);
//一個(gè)節(jié)點(diǎn)
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
//多個(gè)節(jié)點(diǎn)
else
{
//尾刪既可以找尾找尾的前一個(gè)節(jié)點(diǎn)，也可以創(chuàng)造一個(gè)變量記錄尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
//創(chuàng)造一個(gè)變量記錄尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
// SListNode* tail = *pplist;
// SListNode* prev = NULL;
// while (tail->next)
// {
// prev = tail;
// tail = tail->next;
// }
// free(prev->next);
// prev->next = NULL;
//找尾找尾的前一個(gè)節(jié)點(diǎn)
SListNode* tail = *pplist;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//無頭單鏈表頭刪刪除節(jié)點(diǎn)的時(shí)候有三種情況，但只有一個(gè)節(jié)點(diǎn)和多個(gè)節(jié)點(diǎn)的情況可以合并
void SListPopFront(SListNode** pplist)
{
//無節(jié)點(diǎn)時(shí)
assert(*pplist);
//有節(jié)點(diǎn)時(shí)
SListNode* del = *pplist;
*pplist = del->next;
free(del);
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
//斷言：在pos后面插入一個(gè)節(jié)點(diǎn)，最差的情況是pos為尾節(jié)點(diǎn)，但不能為NULL
assert(pos);
SListNode* cur = (SListNode*)malloc(sizeof(SListNode));
if (cur == NULL)
{
perror("malloc");
return;
}
cur->data = x;
cur->next = pos->next;
pos->next = cur;
}
void SListEraseAfter(SListNode* pos)
{
//需要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)不能為NULL，刪除節(jié)點(diǎn)也不能為NULL
assert(pos);
assert(pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
void SListDestroy(SListNode* plist)
{
SListNode* del = NULL;
while (plist)
{
del = plist;
plist = plist->next;
free(del);
}
}
四、帶頭雙向循環(huán)鏈表接口的及實(shí)現(xiàn)
1. 雙向鏈表的接口
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實(shí)現(xiàn)
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos);
2. 接口的實(shí)現(xiàn)
#include "list.h"
// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
ListNode* ListCreate()
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
if (phead == NULL)
{
perror("malloc");
return NULL;
}
//讓頭的 next 和 prev 都指向自己
//則雙向鏈表為空
phead->next = phead;
phead->prev = phead;
return phead;
}
// 創(chuàng)造新節(jié)點(diǎn)
ListNode* BuyTLNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
return newnode;
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
/*ListNode* tail = pHead->prev;
ListNode* newnode = BuyTLNode(x);
newnode->next = pHead;
newnode->prev = tail;
tail->next = newnode;
pHead->prev = newnode;*/
ListInsert(pHead, x); //復(fù)用
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
printf("header <--> ");
//打印的時(shí)候，由于頭內(nèi)的 data 的值沒用
//則從頭的的下一個(gè)節(jié)點(diǎn)開始打印
//并且在循環(huán)到頭的時(shí)候打印結(jié)束
ListNode* cur = pHead ->next;
while (cur != pHead)
{
printf("%d <--> ", cur->data);
cur = cur->next;
}
printf("\n");
}
// 判斷雙向鏈表是否為空
bool LTEmpty(ListNode* pHead)
{
assert(pHead);
return pHead->next == pHead;
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!(LTEmpty(pHead)));
/*ListNode* first = pHead->next;
ListNode* second = first->next;
pHead->next = second;
second->prev = pHead;
free(first);*/
ListErase(pHead->next); //復(fù)用
}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
/*ListNode* next = pHead->next;
ListNode* newnode = BuyTLNode(x);
newnode->next = next;
newnode->prev = pHead;
next->prev = newnode;
pHead->next = newnode;*/
ListInsert(pHead->next, x);//復(fù)用
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!(LTEmpty(pHead)));
/*ListNode* tail = pHead->prev;
ListNode* tailPrev = tail->prev;
tailPrev->next = pHead;
pHead->prev = tailPrev;
free(tail);*/
ListErase(pHead->prev); //復(fù)用
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
ListNode* cur = pHead ->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyTLNode(x);
ListNode* posPrev = pos->prev;
newnode->next = pos;
newnode->prev = posPrev;
posPrev->next = newnode;
pos->prev = newnode;
}
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
五、帶頭雙向循環(huán)鏈表VS無頭單向非循環(huán)鏈表
1. 帶頭雙向循環(huán)鏈表
1.1 帶頭雙向循環(huán)鏈表的優(yōu)點(diǎn)：
- 可以自由地在鏈表中任意位置插入和刪除節(jié)點(diǎn)，這是因?yàn)殡p向鏈表可以方便地找到前驅(qū)和后繼節(jié)點(diǎn)。
- 可以支持雙向遍歷，即可以從前往后或從后往前遍歷鏈表。
- 可以更加高效地實(shí)現(xiàn)某些特殊的操作，比如在鏈表中刪除指定節(jié)點(diǎn)，需要同時(shí)修改其前驅(qū)和后繼節(jié)點(diǎn)的指針，雙向鏈表則可以直接完成這個(gè)操作，而單向鏈表則需要遍歷到前驅(qū)節(jié)點(diǎn)才能完成。
1.2 帶頭雙向循環(huán)鏈表的缺點(diǎn)：
- 因?yàn)槊總€(gè)節(jié)點(diǎn)都要額外存儲(chǔ)一個(gè)前驅(qū)節(jié)點(diǎn)的指針，所以需要更多的內(nèi)存空間。
- 因?yàn)樾枰S護(hù)前驅(qū)和后繼節(jié)點(diǎn)的指針，所以在插入和刪除節(jié)點(diǎn)時(shí)需要更多的操作，導(dǎo)致時(shí)間復(fù)雜度較高。
2. 無頭單向非循環(huán)鏈表
2.1 無頭單向非循環(huán)鏈表的優(yōu)點(diǎn)：
- 因?yàn)槊總€(gè)節(jié)點(diǎn)只需存儲(chǔ)一個(gè)后繼節(jié)點(diǎn)的指針，所以需要較少的內(nèi)存空間。
- 在插入和刪除節(jié)點(diǎn)時(shí)，只需要修改前一個(gè)節(jié)點(diǎn)的指針，不需要修改后一個(gè)節(jié)點(diǎn)的指針，操作相對簡單，導(dǎo)致時(shí)間復(fù)雜度較低。
2.2 無頭單向非循環(huán)鏈表的缺點(diǎn)：
- 無法實(shí)現(xiàn)雙向遍歷，即無法從后往前遍歷鏈表。
- 在刪除指定節(jié)點(diǎn)時(shí)，需要先遍歷到其前驅(qū)節(jié)點(diǎn)，才能完成刪除操作，導(dǎo)致刪除效率較低。
3. 小結(jié)
總之，選擇哪種鏈表數(shù)據(jù)結(jié)構(gòu)應(yīng)該根據(jù)具體的應(yīng)用場景和需要做的操作來決定。如果需要頻繁地插入和刪除節(jié)點(diǎn)，且需要支持雙向遍歷，可以選擇帶頭雙向循環(huán)鏈表；如果需要占用較少的內(nèi)存空間，且不需要雙向遍歷，可以選擇無頭單向非循環(huán)鏈表。文章來源：http://www.zghlxwxcb.cn/news/detail-448784.html
六、鏈表VS順序表
1. 帶頭雙向循環(huán)鏈表
1.1 鏈表的優(yōu)點(diǎn)：
- 動(dòng)態(tài)內(nèi)存分配：鏈表可以在運(yùn)行時(shí)動(dòng)態(tài)地分配內(nèi)存，因此可以根據(jù)實(shí)際需要靈活地增加或減少節(jié)點(diǎn)數(shù)。
- 插入和刪除操作高效：由于鏈表中的元素不必在連續(xù)的內(nèi)存空間中存儲(chǔ)，所以插入和刪除操作非常高效，只需要修改指針，而不需要移動(dòng)所有后續(xù)元素。
- 大小不受限制：鏈表的大小不受限制，可以根據(jù)實(shí)際需要進(jìn)行擴(kuò)展。
2. 鏈表的缺點(diǎn)：
-
隨機(jī)訪問低效：由于鏈表中的元素不是按順序存儲(chǔ)的，因此隨機(jī)訪問某個(gè)元素的效率比較低，需要從頭開始遍歷
O(N)。 - 存儲(chǔ)空間開銷大：鏈表每個(gè)節(jié)點(diǎn)都需要額外的指針來指向下一個(gè)節(jié)點(diǎn)，這樣會(huì)增加存儲(chǔ)空間的開銷。
- 緩存不友好：由于鏈表中的元素不是按順序存儲(chǔ)的，因此可能會(huì)導(dǎo)致緩存未命中，降低訪問效率。
2. 順序表
2.1順序表的優(yōu)點(diǎn)
-
隨機(jī)訪問高效：下標(biāo)的隨機(jī)訪問效率高
O(1)。 - 尾刪尾插高效：順序表的尾插尾刪不需要移動(dòng)數(shù)據(jù)，效率高。
- 緩存友好：由于鏈表中的元素是按順序存儲(chǔ)的，緩存命中率高，訪問效率高。
2.2順序表的缺點(diǎn)
-
部分插入刪除操作低效：由于順序表中的元素是物理結(jié)構(gòu)上是連續(xù)的，當(dāng)數(shù)據(jù)插入刪除前面順序表的時(shí)候需要移動(dòng)數(shù)據(jù)，效率低
O(N)。 - 內(nèi)存大小受限：當(dāng)順序表內(nèi)存存滿后需要擴(kuò)容，擴(kuò)容需要代價(jià)，并且順序表通常會(huì)有內(nèi)存的浪費(fèi)情況。
結(jié)尾
如果有什么建議和疑問，或是有什么錯(cuò)誤，希望大家能夠提一下。
希望大家以后也能和我一起進(jìn)步??！
如果這篇文章對你有用的話，希望能給我一個(gè)小小的贊！文章來源地址http://www.zghlxwxcb.cn/news/detail-448784.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表之鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
