【C語言數(shù)據(jù)結(jié)構(gòu)（基礎(chǔ)版）】第三站：鏈表（二）-創(chuàng)新互聯(lián)

目錄

成都創(chuàng)新互聯(lián)擁有一支富有激情的企業(yè)網(wǎng)站制作團(tuán)隊(duì)，在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)深耕十年，專業(yè)且經(jīng)驗(yàn)豐富。十年網(wǎng)站優(yōu)化營銷經(jīng)驗(yàn)，我們已為上1000+中小企業(yè)提供了成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)解決方案，專業(yè)公司，設(shè)計(jì)滿意，售后服務(wù)無憂。所有客戶皆提供一年免費(fèi)網(wǎng)站維護(hù)!

一、單鏈表的缺陷以及雙向鏈表的引入

1.單鏈表的缺陷

2.雙向鏈表的引入

3.八大鏈表結(jié)構(gòu)

（1）單向和雙向

（2）帶頭和不帶頭

（3）循環(huán)和不循環(huán)

（4）八種鏈表結(jié)構(gòu)

二、帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

1.鏈表創(chuàng)建

2.鏈表的初始化

2.尾插

3.打印鏈表

4.實(shí)現(xiàn)頭插

5.鏈表的頭刪

6.鏈表的尾刪

7.鏈表的查找與修改

8.在pos之前插入一個數(shù)據(jù)

9.刪除pos位置的值

10.鏈表的銷毀

三、雙向帶頭循環(huán)鏈表的完整代碼

四、順序表和鏈表的區(qū)別和聯(lián)系

總結(jié)

一、單鏈表的缺陷以及雙向鏈表的引入 1.單鏈表的缺陷

在我們上一節(jié)內(nèi)容中，我們已經(jīng)學(xué)會了單鏈表的一些基本操作，但是呢其實(shí)我們也發(fā)現(xiàn)了單鏈表有很大的缺陷，我們在實(shí)現(xiàn)尾插，尾刪，在pos前一個位置進(jìn)行插入，刪除pos位置，這幾個接口的實(shí)現(xiàn)都需要找到前一個結(jié)點(diǎn)，而我們找到前一個結(jié)點(diǎn)的方法只能是遍歷，而且還得分情況，看看空鏈表會出現(xiàn)什么情況，只有一個結(jié)點(diǎn)的鏈表又會是什么情況。總之很麻煩

如上圖所示，無論是PopBack、Insert、還是Erase時間復(fù)雜度都達(dá)到了O(N)，效率不高。

究其根本原因是因?yàn)椋瑹o法實(shí)現(xiàn)從后找前，找不到前驅(qū)，必須從頭開始遍歷尋找

2.雙向鏈表的引入

那么如何解決這種現(xiàn)象呢？答案是采取雙向的鏈表，讓它可以從后找到前一個結(jié)點(diǎn)。

這樣的話，那么我們鏈表的聲明就應(yīng)該是這樣的

代碼為

typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDateType date;
}ListNode;
3.八大鏈表結(jié)構(gòu)

在這里就不得不提一下鏈表的種類了，鏈表共有八種。而八種是由三種屬性來排列組合形成的

1.單向??????? 雙向

2.不帶頭???? 帶頭

3.不循環(huán)???? 循環(huán)

如上的三種屬性，經(jīng)過排列組合后剛好可以形成八種結(jié)構(gòu)，而我們上節(jié)所說的正是單向不帶頭不循環(huán)鏈表

（1）單向和雙向

單向和雙向其實(shí)在前面已經(jīng)說過了。就是一個雙向彌補(bǔ)了單向找前一個結(jié)點(diǎn)比較麻煩的現(xiàn)象

（2）帶頭和不帶頭

什么是帶頭什么又是不帶頭呢？我們看下面的圖就知道了

這就是兩個最明顯的區(qū)別了，帶頭的鏈表比不帶頭的鏈表多一個結(jié)點(diǎn)，而這個結(jié)點(diǎn)其實(shí)是不存儲有效數(shù)據(jù)的，它是一個哨兵位

帶頭結(jié)點(diǎn)的好處：

不需要改變傳過來的指針，也就是意味著不需要傳二級指針

為什么步不需要傳二級指針呢，我們可以畫圖來理解一下

這是普通的不帶頭鏈表傳參圖，我們其實(shí)可以看出來，其實(shí)plist傳參的時候會拷貝成phead，然后我們改變的連接都是phead和newnode的結(jié)構(gòu)，而非plist，因?yàn)閜list和phead是兩個不同的變量，他們的地址都不一樣

而如果是帶頭結(jié)點(diǎn)的，我們也畫圖來理解一下

這樣形參和實(shí)參即便不一樣也無所謂了，因?yàn)槭俏覀兊纳诒粊砜刂莆覀兊逆湵淼?，plist和phead僅僅只是為了找到這個哨兵位。

哨兵位不存儲有效數(shù)據(jù)的的原因：

我們有時候會在書上看到哨兵位存儲一個數(shù)據(jù)，這個數(shù)據(jù)是代表著有幾個結(jié)點(diǎn)了。其實(shí)這是經(jīng)典的錯誤標(biāo)準(zhǔn)的零分，這里是絕對不可以存儲這個鏈表有幾個有效數(shù)據(jù)了，因?yàn)榧偃缯f我們鏈表的數(shù)據(jù)是char類型，那么它大就是127啊。假如說鏈表的長度是129呢？顯然著哨兵位就不可以存儲數(shù)據(jù)

（3）循環(huán)和不循環(huán)

這個就比較簡單了，不循環(huán)的鏈表最終指向NULL，而循環(huán)的鏈表最后一個結(jié)點(diǎn)又指向了頭節(jié)點(diǎn)

（4）八種鏈表結(jié)構(gòu)

三大屬性我們都有所了解了，那么它的鏈表就可由這三種排列組合形成八種鏈表結(jié)構(gòu)。

單向不帶頭不循環(huán)鏈表??????? 單向不帶頭循環(huán)鏈表??????

單向帶頭不循環(huán)鏈表?????????? 單向帶頭循環(huán)鏈表

雙向不帶頭不循環(huán)鏈表??????? 雙向不帶頭循環(huán)鏈表

雙向帶頭不循環(huán)鏈表?????????? 雙向帶頭循環(huán)鏈表

但是我們常用的就兩種鏈表：

1.單向不帶頭不循環(huán)鏈表：（在上一篇文章中已經(jīng)實(shí)現(xiàn)了）

結(jié)構(gòu)簡單，一般不會單獨(dú)用來存儲數(shù)據(jù)。實(shí)際中更多的是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)。如哈希桶，圖的鄰接表等

2.雙向帶頭循環(huán)鏈表：

結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。

當(dāng)然，我們本節(jié)也就是來實(shí)現(xiàn)這個雙向帶頭循環(huán)鏈表了，它的圖示應(yīng)該是這樣的

二、帶頭雙向循環(huán)鏈表的實(shí)現(xiàn) 1.鏈表創(chuàng)建

這個就很簡單了，我們直接定義一個結(jié)點(diǎn)指針讓他指向空即可

2.鏈表的初始化

我們先來聲明一下這兩個函數(shù)

我們先來實(shí)現(xiàn)初始化函數(shù)，銷毀鏈表的函數(shù)在后面實(shí)現(xiàn)

我們想一下，這個帶頭的循環(huán)雙向鏈表初始化后應(yīng)該是什么樣子呢？

它應(yīng)該是這樣的，它只有一個結(jié)點(diǎn)，而這個結(jié)點(diǎn)就是哨兵位，這個哨兵位的prev和next還得自己指向自己，而且plist還得指向這個哨兵位

那么我們現(xiàn)在就來實(shí)現(xiàn)它吧，我們會發(fā)現(xiàn)，我們想要初始化，那么必須得需要創(chuàng)建一個新的結(jié)點(diǎn)出來，但是我們知道后面還有尾插，頭插等都需要創(chuàng)建新的結(jié)點(diǎn)，不妨我們直接將創(chuàng)建結(jié)點(diǎn)寫成一個函數(shù)

//創(chuàng)建一個新結(jié)點(diǎn)
ListNode* BuyListNode(LTDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->date = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

這樣我們的結(jié)點(diǎn)就創(chuàng)建好了，那么我們接下來就是來完善這個初始化，如下圖所示

當(dāng)然，細(xì)心的人已經(jīng)發(fā)現(xiàn)問題了，這里肯定是行不通的，因?yàn)閜head是形參，最終的結(jié)果是讓phead給初始化了，而plist沒有被初始化，所以我們這里應(yīng)該傳二級指針。而之前所說的雙向循環(huán)帶頭鏈表不需要二級指針指的是除過哨兵位以外的結(jié)點(diǎn)，因?yàn)樯诒贿€是需要和plist連接起來的，而其他的操作只需要能找到這個哨兵位就可以了

當(dāng)然我們也可以不通過修改二級指針的方法來完成這個代碼，我們可以這樣做，我們也不進(jìn)行傳參了，我們初始化好這個鏈表之后將這個結(jié)點(diǎn)的地址給返回去，然后賦值給plist

這樣的話我們的聲明也會被改變了

代碼為

//創(chuàng)建一個新結(jié)點(diǎn)
ListNode* BuyListNode(LTDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->date = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
//初始化鏈表
ListNode* ListInit()
{
	ListNode* phead;
	phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
2.尾插

對于尾插我們先聲明它的函數(shù)

//鏈表的尾插
void ListPushBack(ListNode* phead, LTDateType x);

我們這這樣想的，假設(shè)原來的是我們下圖的連接

我們現(xiàn)在想要尾插一個4過去，那么我們首先要創(chuàng)建這個4的這個結(jié)點(diǎn)

然后我們需要的是連接這些點(diǎn)，我們現(xiàn)在有的是4的地址newnode，和哨兵位的地址phead

而我們想要找到尾的話也很簡單，因?yàn)槲覀儸F(xiàn)在是雙向的，所以tail=phead->prev

有了這三個地址，接下來就是連接了

我們先讓tail->next=newnode

然后讓newnode->prev=tail

這樣tail和newnode的連接就完成了

然后是newnode和phead的連接，我們先讓newnode->next=phead

接下來是phead->prev=newnode

當(dāng)然我們里面創(chuàng)建結(jié)點(diǎn)的時候，不要忘記把4改成了x

我們發(fā)現(xiàn)這個代碼其實(shí)比單鏈表的尾插要簡單了許多，雖然結(jié)構(gòu)復(fù)雜了，但是實(shí)現(xiàn)變得簡單了。而且這個也不用判斷為空鏈表會怎么樣。

當(dāng)然在這里，我們也知道phead是一定不為空的，所以我們也可以加上一句斷言

//鏈表的尾插
void ListPushBack(ListNode* phead, LTDateType x)
{
	assert(phead);
	//創(chuàng)建一個新的結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//尋找末尾結(jié)點(diǎn)
	ListNode* tail = phead->prev;
	//連接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
3.打印鏈表

我們已經(jīng)寫完了尾插，那么我們肯定希望能夠測試一下，那么我們不得不先寫一個打印鏈表的功能來測試一下了

打印的功能也很簡單，我們定義一個cur，并讓他一開始指向phead->next，也就是第一個結(jié)點(diǎn)，然后只要此時的cur和phead不一樣，那么我們就可以繼續(xù)打印。這也是利用了循環(huán)的特性

這樣的話我們的代碼實(shí)現(xiàn)如下

代碼如下

//鏈表的打印
void ListPrint(ListNode* phead)
{
	//當(dāng)前的要指向鏈表的第一個結(jié)點(diǎn)，也就是哨兵位的下一個結(jié)點(diǎn)
	ListNode* cur = phead->next;
	//判斷cur是否為哨兵位，如果不是哨兵位，則打印，是哨兵位
	//則說明循環(huán)已經(jīng)遍歷完了
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

而且這個代碼即便是空鏈表，也沒有任何問題的。因?yàn)槿绻麤]有有效結(jié)點(diǎn)的話，那么phead->next還是phead，所以根本不會打印的

那么我們現(xiàn)在來測試一下尾插和打印吧，圓滿的完成了我們的需求

4.實(shí)現(xiàn)頭插

我們現(xiàn)在來實(shí)現(xiàn)一下頭插吧，下面是函數(shù)的聲明

//鏈表的頭插
void ListPushFront(ListNode* phead, LTDateType x);

然后我們來用這個圖來演示一下，我們想要在這里面插入0這個結(jié)點(diǎn)

那么首先我們肯定得為0創(chuàng)建它的結(jié)點(diǎn)

然后就是開始連接了

我們先記錄下來原來的第一個結(jié)點(diǎn)

然后我們開始連接

對于這個連接其實(shí)對于順序沒有什么要求

我們先連接這兩個

然后連接這兩個

然后連接這兩個

最后連接這兩個

最后在加上斷言

我們這里剛剛寫錯了，下面紅圈已經(jīng)改為正確了

我們測試一下

符合我們的邏輯，而且這個函數(shù)對于空的鏈表也是可以連接起來的

代碼為

//鏈表的頭插
void ListPushFront(ListNode* phead, LTDateType x)
{
	assert(phead);
	//為x創(chuàng)建一個結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//先記錄一下原來的第一個結(jié)點(diǎn)
	ListNode* first = phead->next;
	//連接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

然后再這里我們在上面說了，那個是我們定義了first去記錄了之前的第一個結(jié)點(diǎn)，然后才會使得連接順序可以無所謂的。但是萬一我們要是沒有定義這個first的話，我們再去連接就必須得注意一下順序，否則會出問題的，在這里給出順序的圖解和代碼

然后我們測試運(yùn)行一下

結(jié)果是正確的

要考慮順序的代碼為

//鏈表的頭插(需要考慮順序的話)
void ListPushFront(ListNode* phead, LTDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}

其實(shí)就是先連接后面的，然后連接前面的，因?yàn)槿绻冗B前面的話，就會找不到后面的結(jié)點(diǎn)

5.鏈表的頭刪

先寫出函數(shù)聲明

//鏈表的頭刪
void ListPopFront(ListNode* phead);

我們接下來來實(shí)現(xiàn)，對于這個圖而言，我們想要刪掉頭節(jié)點(diǎn)，那么其實(shí)就相當(dāng)于將第一個結(jié)點(diǎn)給銷毀掉，連接起來phead和第二個結(jié)點(diǎn)

如下所示就是頭刪代碼的實(shí)現(xiàn)，當(dāng)然也要為了防止鏈表沒有數(shù)據(jù)的時候刪除掉哨兵位。

測試如下

代碼為

//鏈表的頭刪
void ListPopFront(ListNode* phead)
{
	assert(phead);
	//這是避免刪掉我的哨兵位
	assert(phead->next != phead);
	//第一個結(jié)點(diǎn)的地址
	ListNode* first = phead->next;
	//第二個結(jié)點(diǎn)的地址
	ListNode* second = first->next;
	//連接
	phead->next = second;
	second->prev = phead;
	//釋放第一個結(jié)點(diǎn)
	free(first);
	first = NULL;
}
6.鏈表的尾刪

其實(shí)鏈表的尾刪和頭刪除基本一致

下面是函數(shù)的聲明

//鏈表的尾刪
void ListPopBack(ListNode* phead);

測試結(jié)果為

代碼為

//鏈表的尾刪
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//定義倒數(shù)第一個結(jié)點(diǎn)
	ListNode* tail = phead->prev;
	//定義倒數(shù)第二個結(jié)點(diǎn)
	ListNode* prev = tail->prev;

	//連接
	phead->prev = prev;
	prev->next = phead;

	//銷毀原來的結(jié)點(diǎn)
	free(tail);
	tail = NULL;
}
7.鏈表的查找與修改

我們接下來先來實(shí)現(xiàn)鏈表的查找

下面是函數(shù)的聲明

//查找某一個值的結(jié)點(diǎn)地址
ListNode* ListFind(ListNode* phead, LTDateType x);

然后我們是這樣思考的，我們定義一個cur指針，讓它一開始指向phead->next，也就是第一個結(jié)點(diǎn)，讓cur一直往下走，當(dāng)cur不等于phead的時候，讓他繼續(xù)遍歷，一旦找到則返回cur，否則就是沒找到，返回NULL

代碼如下

//查找某一個值的結(jié)點(diǎn)地址
ListNode* ListFind(ListNode* phead,LTDateType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

我們來測試一下

符合我們的預(yù)期，那么如果我們想要修改我們找到的這個數(shù)據(jù)該如何做的？其實(shí)很簡單，因?yàn)橐呀?jīng)有這個指針了，直接修改就可以了

也就是說，查找功能附帶著修改功能

8.在pos之前插入一個數(shù)據(jù)

這個其實(shí)也是與查找函數(shù)緊密相連，先用查找找到pos，然后才能進(jìn)行修改

而它的實(shí)現(xiàn)其實(shí)與頭插，尾插基本一致

它的聲明為

//在pos之前插入一個值
void ListInsert(ListNode* pos, LTDateType x);

它的實(shí)現(xiàn)為

//在pos之前插入一個值
void ListInsert(ListNode* pos, LTDateType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	newnode->next = pos;
	pos->prev = newnode;
	prev->next = newnode;
	newnode->prev = prev;
}

測試為

9.刪除pos位置的值

這個也與尾刪頭刪基本一致

下面是函數(shù)的聲明

//刪除pos處的值
void ListErase(ListNode* pos);

函數(shù)的實(shí)現(xiàn)為

//刪除pos處的值
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* next = pos->next;
	ListNode* prev = pos->prev;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

測試為

在這里我們其實(shí)也能發(fā)現(xiàn)，其實(shí)Insert和Erase完全可以替代頭插尾插頭刪尾刪

10.鏈表的銷毀

這是最后一個接口，我們直接銷毀掉整個鏈表即可

函數(shù)聲明為

//鏈表的銷毀
void ListDestory(ListNode* phead);

思想是，設(shè)置一個cur，讓他去遍歷整個鏈表，只要cur！=phead，那么就銷毀這個空間。

代碼為

//鏈表的銷毀
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
三、雙向帶頭循環(huán)鏈表的完整代碼

我們現(xiàn)在所有的接口都已經(jīng)實(shí)現(xiàn)了，那么其實(shí)我們也能發(fā)現(xiàn)這個雙向帶頭循環(huán)鏈表的時間復(fù)雜度都是O(1)，（除過查找以外，查找后續(xù)會有更優(yōu)的寫法）

完整代碼如下：

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

void TestList1()
{
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	
	ListPrint(plist);

	ListPushFront(plist, 5);
	ListPushFront(plist, 6);
	ListPushFront(plist, 7);
	ListPushFront(plist, 8);

	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);

	ListPrint(plist);

	ListPopBack(plist);
	ListPrint(plist);
	ListNode* pos = ListFind(plist, 3);
	if (pos)
	{
		//查找并修改
		pos->date *= 10;
		printf("找到了,它乘10以后是%d\n",pos->date);

	}
	else
	{
		printf("沒找到\n");
	}
	ListPrint(plist);
	ListInsert(pos, 300);
	ListPrint(plist);

	ListErase(pos);
	ListPrint(plist);
	ListDestory(plist);
}
int main()
{
	TestList1();
	return 0;
}

List.h文件

#pragma once
#include#include#include
typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDateType date;
}ListNode;


//鏈表的初始化
ListNode* ListInit();
//鏈表的銷毀
void ListDestory(ListNode* phead);
//鏈表的打印
void ListPrint(ListNode* phead);
//鏈表的尾插
void ListPushBack(ListNode* phead, LTDateType x);
//鏈表的頭插
void ListPushFront(ListNode* phead, LTDateType x);
//鏈表的頭刪
void ListPopFront(ListNode* phead);
//鏈表的尾刪
void ListPopBack(ListNode* phead);
//查找某一個值的結(jié)點(diǎn)地址
ListNode* ListFind(ListNode* phead, LTDateType x);
//在pos之前插入一個值
void ListInsert(ListNode* pos, LTDateType x);
//刪除pos處的值
void ListErase(ListNode* pos);

List.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

//創(chuàng)建一個新結(jié)點(diǎn)
ListNode* BuyListNode(LTDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->date = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
//初始化鏈表
ListNode* ListInit()
{
	ListNode* phead;
	phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//鏈表的銷毀
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
//鏈表的打印
void ListPrint(ListNode* phead)
{
	//當(dāng)前的要指向鏈表的第一個結(jié)點(diǎn)，也就是哨兵位的下一個結(jié)點(diǎn)
	ListNode* cur = phead->next;
	//判斷cur是否為哨兵位，如果不是哨兵位，則打印，是哨兵位
	//則說明循環(huán)已經(jīng)遍歷完了
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}
//鏈表的尾插
void ListPushBack(ListNode* phead, LTDateType x)
{
	assert(phead);
	//創(chuàng)建一個新的結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//尋找末尾結(jié)點(diǎn)
	ListNode* tail = phead->prev;
	//連接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//鏈表的頭插
void ListPushFront(ListNode* phead, LTDateType x)
{
	assert(phead);
	//為x創(chuàng)建一個結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//先記錄一下原來的第一個結(jié)點(diǎn)
	ListNode* first = phead->next;
	//連接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
鏈表的頭插(需要考慮順序的話)
//void ListPushFront(ListNode* phead, LTDateType x)
//{
//	assert(phead);
//	ListNode* newnode = BuyListNode(x);
//
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//}

//鏈表的頭刪
void ListPopFront(ListNode* phead)
{
	assert(phead);
	//這是避免刪掉我的哨兵位
	assert(phead->next != phead);
	//第一個結(jié)點(diǎn)的地址
	ListNode* first = phead->next;
	//第二個結(jié)點(diǎn)的地址
	ListNode* second = first->next;
	//連接
	phead->next = second;
	second->prev = phead;
	//釋放第一個結(jié)點(diǎn)
	free(first);
	first = NULL;
}
//鏈表的尾刪
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//定義倒數(shù)第一個結(jié)點(diǎn)
	ListNode* tail = phead->prev;
	//定義倒數(shù)第二個結(jié)點(diǎn)
	ListNode* prev = tail->prev;

	//連接
	phead->prev = prev;
	prev->next = phead;

	//銷毀原來的結(jié)點(diǎn)
	free(tail);
	tail = NULL;
}
//查找某一個值的結(jié)點(diǎn)地址
ListNode* ListFind(ListNode* phead,LTDateType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos之前插入一個值
void ListInsert(ListNode* pos, LTDateType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	newnode->next = pos;
	pos->prev = newnode;
	prev->next = newnode;
	newnode->prev = prev;
}
//刪除pos處的值
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* next = pos->next;
	ListNode* prev = pos->prev;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}
四、順序表和鏈表的區(qū)別和聯(lián)系

順序表：

優(yōu)點(diǎn)

空間連續(xù)、支持隨機(jī)訪問

缺點(diǎn)

1.中間或前面部分的插入刪除時間復(fù)雜度O（N）

2.增容的代價比較大

鏈表：

優(yōu)點(diǎn)

1.任意位置插入刪除時間復(fù)雜度為O（1）

2.沒有增容消耗，按需申請結(jié)點(diǎn)空間，不用了直接釋放

缺點(diǎn)

以節(jié)點(diǎn)為單位存儲，不支持隨機(jī)訪問

總結(jié)

本節(jié)講解了雙向帶頭循環(huán)鏈表的實(shí)現(xiàn)，希望大家都有所收獲

如果對你有幫助，不要忘記點(diǎn)贊加收藏哦?。。?/p>

想看更多更加優(yōu)質(zhì)的內(nèi)容，一定要關(guān)注我哦?。?！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：【C語言數(shù)據(jù)結(jié)構(gòu)（基礎(chǔ)版）】第三站：鏈表（二）-創(chuàng)新互聯(lián)
當(dāng)前URL：http://bm7419.com/article34/igcse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、App設(shè)計(jì)、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站建設(shè)、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)