1.學(xué)習(xí)第一步：

當(dāng)我們要學(xué)習(xí)和了解一個(gè)事物時(shí)，我們要做的第一步便是對(duì)這個(gè)事物有一個(gè)體的的了解?，F(xiàn)在我們要學(xué)習(xí)雙向帶頭循環(huán)鏈表的第一步也是這個(gè)，我們現(xiàn)在先來了解一下這種鏈表的結(jié)構(gòu)----

就像該圖所呈現(xiàn)的那樣，雙向循環(huán)鏈表就是長(zhǎng)這樣。但是你可千萬不要將head當(dāng)成head。?這里的head是一個(gè)哨兵位的頭!

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

?在上面的介紹中，相信在你的腦海中已經(jīng)有了帶頭雙向循環(huán)鏈表的樣子了?，F(xiàn)在我們就來實(shí)現(xiàn)一下吧。?

2.1：鏈表的誕生（鏈表初始化）?

鏈表的初始化的目的就是要將帶頭雙向循環(huán)鏈表的頭（head)給搞出來。當(dāng)然，在此之前還是要有一個(gè)鏈表結(jié)點(diǎn)的結(jié)構(gòu)。

結(jié)構(gòu)：

typedef int datatype;
 typedef struct ListNode{
	 datatype data;
	 struct ListNode* next;
	 struct ListNode* prev;

}ListNode;

第一個(gè)功能的實(shí)現(xiàn)——初始化鏈表：InitList()

void InitList(ListNode* head)
{
	head->next = head;
	head->prev = head;
	head->data = -1;
}

當(dāng)然，在初始化操作之前還得先創(chuàng)建一個(gè)節(jié)點(diǎn)傳進(jìn)InitList()中。這一步操作是在test.c文件中的。

void test1()
{
	ListNode* list =(ListNode*) malloc(sizeof(ListNode));//創(chuàng)建節(jié)點(diǎn)
	InitList(list);

}
int main()
{
	test1();
	return 0;
}

?第二個(gè)功能的實(shí)現(xiàn)——尾插：pushBack()

相對(duì)于單鏈表來說，簡(jiǎn)直小菜一碟！

void pushBack(ListNode* head,datatype x)

{
    assert(head);
	ListNode* newnode = Buynewnode(x);
	ListNode* tail = head->prev;

	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = head;
	head->prev = newnode;

}

第三個(gè)功能的實(shí)現(xiàn)——ListPrint(Listnode* head)

這個(gè)打印函數(shù)實(shí)現(xiàn)起來那就更加得心應(yīng)手了，只不夠這個(gè)函數(shù)的終止條件是比較特殊的。它的終止條件是當(dāng)指針走到哨兵位的頭結(jié)點(diǎn)時(shí)就停止。當(dāng)然這個(gè)指針的起始位置是哨兵位的下一位！

void Listprint(ListNode* head)
{
    assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
	
}

?第四個(gè)功能的實(shí)現(xiàn)——頭插

頭插的意思就是生成一個(gè)新的節(jié)點(diǎn)然后添加到哨兵位的頭節(jié)點(diǎn)的后面變成新的頭節(jié)點(diǎn)。

void pushFront(ListNode* head, datatype x)
{
    assert(head);
	ListNode* newnode = Buynewnode(x);
	ListNode* next = head->next;

	head->next = newnode;
	newnode->prev = head;

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

第八個(gè)功能——中間插入

?這個(gè)函數(shù)是個(gè)能將頭插，尾插兩種功能聯(lián)合起來實(shí)現(xiàn)的函數(shù)（改一下傳入的參數(shù)就行了）。

先找到指定的節(jié)點(diǎn)：

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead;
	while (cur->next != pHead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	if (cur->val == x)
	{
		return cur;
	}
	return NULL;
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-447003.html

在指定元素的后面插入：

void ListInsert(ListNode* pos, LTDataType x)//中間插入，在pos的后面插入一個(gè)節(jié)點(diǎn)
{
	assert(pos);
	ListNode* newnode = Buynewnode(x);
	ListNode* next = pos->next;

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

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

?第五個(gè)功能的實(shí)現(xiàn)——尾刪

尾刪尾刪就是要把鏈表尾部的節(jié)點(diǎn)給刪除掉，在這個(gè)帶頭雙向循環(huán)鏈表里實(shí)現(xiàn)這個(gè)功能是十分簡(jiǎn)單的！并且時(shí)間復(fù)雜度為O(1)效率特別高！

代碼：

void popBack(ListNode* head)
{
	assert(head);
	ListNode* del = head->prev;//記錄一下要?jiǎng)h除的尾節(jié)點(diǎn)
	ListNode* tailFront = del->prev;//找到尾結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

	tailFront->next = head;
	head->prev = tailFront;

	free(del);
	del = NULL;
}

第六個(gè)功能的實(shí)現(xiàn)——頭刪

頭刪的操作與尾刪差不多，只不過刪尾變成了刪頭。

void popFront(ListNode* head)
{
	assert(head);
	ListNode* del = head->next;
	ListNode* next = del->next;

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

	free(del);
	del = NULL;
}

?第七個(gè)功能——中間刪除

中間刪除是包含頭刪與尾刪的其實(shí)，假如你要將頭刪與尾刪的功能用一個(gè)函數(shù)進(jìn)行實(shí)現(xiàn)的話那就可以實(shí)現(xiàn)一個(gè)中間刪除函數(shù)。

void ListErase(ListNode* pos)//中間刪除，刪除pos后面的節(jié)點(diǎn),但是不能刪除哨兵位的頭
{
	assert(pos);
	ListNode* del = pos;

	ListNode* Frontnode = del->prev;
	ListNode* next = pos->next;

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

	free(del);
	del = NULL;
}

當(dāng)你要變成一個(gè)頭刪函數(shù)時(shí)，這個(gè)中間刪除的函數(shù)的參數(shù)改變一下就行了。

ListErase(head->next);//頭刪

ListErase(head->prev);//尾刪

?但是當(dāng)你要?jiǎng)h除一個(gè)既不是頭也不是尾的節(jié)點(diǎn)時(shí)，你就要再弄一個(gè)查找函數(shù)。

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead;
	while (cur->next != pHead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	if (cur->val == x)
	{
		return cur;
	}
	return NULL;
}

用這個(gè)函數(shù)定位到你要?jiǎng)h除的元素，然后再將其刪除！但是返回空指針的時(shí)候是不能進(jìn)行刪除的！

最后一個(gè)功能——銷毀鏈表

因?yàn)槟愕逆湵淼墓?jié)點(diǎn)是malloc出來的，所以你要在用完以后將其銷毀來避免內(nèi)存泄漏。

void ListDestory(ListNode* head)
{
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	while (cur !=pHead) {
		free(cur);
		cur = next;
		next = cur->next;
	}
	printf("銷毀成功!\n");
}

?

?

到了這里，關(guān)于雙向帶頭循環(huán)鏈表的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！