C語言超詳細講解數(shù)據(jù)結構中雙向帶頭循環(huán)鏈表

更新時間：2022年04月11日 11:28:34 作者：三分苦

帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結構，都是帶頭雙向循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶來很多優(yōu)勢，實現(xiàn)反而簡單

一、概念

前文我們已經(jīng)學習了單向鏈表，并通過oj題目深入了解了帶頭節(jié)點的鏈表以及帶環(huán)鏈表，來畫張圖總體回顧下：

在我們學習的鏈表中，其實總共有8種，都是單雙向和帶不帶頭以及帶不帶環(huán)的任意組合

今兒要學習的是雙向 - 帶頭 - 循環(huán)鏈表，聽名字就覺著結構很復雜，要比曾經(jīng)學的單向 - 不帶頭 - 不循環(huán) 鏈表的結構復雜的多，確實也是。先來畫張圖整體感受下：

解釋：

雙向：就要確保每個數(shù)據(jù)存兩個指針next和prev。next指向下一個節(jié)點，prev指向上一個節(jié)點
帶頭：帶一個哨兵位的頭節(jié)點在數(shù)據(jù)的最前頭。
循環(huán)：尾節(jié)點的next指向哨兵位頭節(jié)點，而哨兵位的上一個節(jié)點prev指向尾節(jié)點，構成循環(huán)。

正文開始：

二、必備工作

2.1、創(chuàng)建雙向鏈表結構

因為是雙向鏈表，所以在結構體里頭必然有兩個指針，一個next指向下一個節(jié)點，一個prev指向上一個節(jié)點。

List.h 文件：

//創(chuàng)建雙向鏈表結構
typedef int LTDataType;   //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //存儲數(shù)據(jù)
	struct ListNode* next; //指向下一個
	struct ListNode* prev; //指向上一個
}LTNode; //方便后續(xù)使用，不需要重復些struct

2.2、初始化鏈表

思路：

在初始化的時候要傳地址，因為形參的改變不會影響實參，pphead的改變不會影響pList，要傳pList的地址，用**pphead來接收，此時就要assert斷言了，因為二級指針地址不可能位空。因為是雙向循環(huán)鏈表，所以要將創(chuàng)建好的哨兵位節(jié)點的next和prev均指向自己。

List.h 文件：（1）

//初始化鏈表（二級指針版）
void ListInit(LTNode* pphead);

List.c 文件：（1）

//初始化鏈表（二級指針版）
void ListInit(LTNode** pphead)
{
	//傳二級指針，那么當然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節(jié)點，所以一開始就要給一個節(jié)點
	//為了循環(huán)，要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優(yōu)先級，*pphead要加括號
	(*pphead)->prev = *pphead;
}

注意：

上一種方法我們傳的是二級指針，那么可以傳一級指針嗎，其實也是可以的，只需寫個函數(shù)返回指針即可

List.h 文件：（2）

//初始化鏈表（一級指針版本）
LTNode* ListInit();

List.c 文件：（2）

//初始化鏈表（一級指針版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.3、動態(tài)申請節(jié)點

List.c 文件：

//創(chuàng)建新節(jié)點
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新創(chuàng)建的節(jié)點
}

2.4、打印鏈表

思路：

既然是打印，首先要搞明白一點，哨兵位不用來存放有效數(shù)據(jù)，那么就不需要打印，定義一個cur指針來迭代，那么應該從phead的next開始打印，當cur走完一遍，重又回到phead的時候停止

List.h 文件：

//打印鏈表
void ListPrint(LTNode* phead);

List.c 文件：

//打印鏈表
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5、銷毀鏈表

思路：

既然是銷毀鏈表了，那么自然是要把鏈表的所有元素包括哨兵位都給銷毀掉，但畢竟剛開始傳phead的時候是不能為空的，所以要斷言，在把所有有效數(shù)據(jù)銷毀后最后再銷毀哨兵位即可。

法一：遍歷

定義一個指針cur，從phead的next第一個有效數(shù)據(jù)開始free，保存下一個，再free，依次遍歷下去

法二：附用ListErase函數(shù)

此法也可以，不過每次Erase完，都會把前后兩個節(jié)點再鏈接起來，雖說最后都會銷毀，但duck不必多此一舉，所有直接采用法一比較好

List.h 文件：

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

List.c 文件：

//銷毀鏈表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷毀從第一個節(jié)點到尾部的數(shù)據(jù)
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節(jié)點phead
	free(phead);
	phead = NULL;
}

Test.c 文件：

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}

三、主要功能

3.1、在pos節(jié)點前插入數(shù)據(jù)

思路：

假設我們已經(jīng)進行了尾插4個數(shù)字，現(xiàn)在想在數(shù)字3的前面插入30，那么首先就要查找有無數(shù)字3，若有，則插入。注意：這里需要用到后文才講到的查找函數(shù)，這里直接引用了，詳解看后文即可，問題不大！

首先，將30放到新創(chuàng)建的節(jié)點newnode里頭，為了實現(xiàn)雙向，要先把3的前一個數(shù)據(jù)2的next指向新節(jié)點newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。

List.h 文件：

//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x);

List.c 文件：

//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//創(chuàng)建插入數(shù)據(jù)的新節(jié)點
	LTNode* newnode = BuyLTNode(x);
	//鏈接左側
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//鏈接右側
	newnode->next = pos;
	pos->prev = newnode;
}

Test.c 文件：

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數(shù)字3就插入
	}
	ListPrint(pList);//打印
}

效果如下：

尾插

思路：

首先，因為此鏈表是帶哨兵位的頭節(jié)點，所以頭節(jié)點必然不為空，剛開始就要assert斷言。其次，單鏈表尾插需要找尾，雙向鏈表雖然也需要，不過非常簡單，不需要再遍歷鏈表了，因為哨兵位頭節(jié)點的phead的上一個節(jié)點指向的就是尾，這就充分體現(xiàn)了雙向循環(huán)的好處，找到了尾節(jié)點就需要再創(chuàng)建一個節(jié)點存儲插入數(shù)據(jù)，方便尾插。

List.h 文件：

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

List.c 文件：1.0

//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言，防止頭節(jié)點為空
	LTNode* tail = phead->prev; //找到尾節(jié)點，便于后續(xù)插入數(shù)據(jù)
	LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點
	//將此新插入的尾節(jié)點與上一個節(jié)點鏈接起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節(jié)點與哨兵位phead鏈接起來構成循環(huán)
	newnode->next = phead;
	phead->prev = newnode;
}

Test.c 文件：

void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
}

效果如下：

注意：

在上文中，我們學習了在pos前插入數(shù)據(jù)，那么設想一下，當pos就等于phead的時候，它（phead）的前不就是鏈表的尾部嗎，那么理所應當，尾插也可以這樣完成：

List.c 文件：2.0

//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); 
	ListInsert(phead, x);
}

頭插

思路：

前面我們已經(jīng)學習了在pos前插入數(shù)據(jù)，那么頭插的實現(xiàn)就尤為簡單了，當pos為原第一個數(shù)據(jù)phead->next時，此時就是在其之前插入數(shù)據(jù)，那么實現(xiàn)的不久是頭插嗎，如下：

List.h 文件：

//頭插
void ListPushFront(LTNode* phead, LTDataType x);

List.c 文件：

//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

Test.c 文件：

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個數(shù)字
	}
	ListPrint(pList);//打印
}

效果如下：

3.2、刪除pos處節(jié)點數(shù)據(jù)

思路：

刪除pos處數(shù)據(jù)其實也很簡單，有點類似于把pos處直接忽略的思想，或者說是繞過去。首先，需要找到pos的上一個節(jié)點prev和下一個節(jié)點next，將prev和next互相鏈接即可，直接跳過了pos，這樣就實現(xiàn)了刪除pos處節(jié)點的數(shù)據(jù)，記得把pos處給free釋放掉。這里我們以pos為2示例：

List.h 文件：

//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos);

List.c 文件：

//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個指針保存pos兩邊的節(jié)點
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next鏈接起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 文件：

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處數(shù)據(jù)
		pos = NULL; //形參的改變不會影響實參，最好在這置空pos
	}
	ListPrint(pList);//打印
}

效果如下：

尾刪

思路：

雙向循環(huán)鏈表的特點將再次得以體現(xiàn)，根據(jù)其特性，我們知道phead的prev指向尾節(jié)點，用tail指針保存，再定義一個指針tailPrev指向tail的prev，現(xiàn)僅需將tailPrev的next指向哨兵位節(jié)點phead，再把哨兵位phead的prev重新置成tailPrev即可，但是別忘記把刪掉的尾節(jié)點給釋放掉，得free(tail)。記得要斷言鏈表不能為空，因為不能刪除哨兵位節(jié)點。

List.H 文件：

//尾刪
void ListPopBack(LTNode* phead);

List.c 文件：1.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節(jié)點
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節(jié)點
	free(tail);
	tail = NULL;
	//將鏈表循環(huán)起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

Test.c 文件：

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}

效果如下：

注意：

前文我們已經(jīng)學了刪除pos處節(jié)點的數(shù)據(jù)，那么當pos為phead->prev時，刪除的是不是就是尾節(jié)點，所以，尾刪理所應當可以這樣寫：

List.c 文件：2.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節(jié)點
	ListErase(phead->prev);
}

頭刪

思路：

有了上文之鑒，我們可以直接利用前面寫的刪除pos處數(shù)據(jù)的函數(shù)來完成，當pos為phead->prev時，pos的位置就是尾，此時刪除的就是尾。當然還得注意一點，需要額外assert斷言防止刪除的數(shù)據(jù)為哨兵位的節(jié)點。

List.h 文件：

//頭刪
void ListPopFront(LTNode* phead);

List.c 文件：

//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節(jié)點
	ListErase(phead->next);
}

Test.c 文件：

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	//頭插3個數(shù)字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾刪3個數(shù)字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//頭刪3個數(shù)字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
}

效果如下：

3.3、查找數(shù)據(jù)

思路：

查找數(shù)據(jù)其實也比較簡單，首先，定義一個指針cur指向哨兵位phead的next，依次遍歷cur看cur->data是否為查找的數(shù)據(jù)x，如果是，則返回cur，否則繼續(xù)（cur=cur->next），若找不到則返回NULL。

List.h 文件：

//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);

List.c 文件：

//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}

四、總代碼

List.h 文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//創(chuàng)建雙向鏈表結構
typedef int LTDataType;   //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //存儲數(shù)據(jù)
	struct ListNode* next; //指向下一個
	struct ListNode* prev; //指向上一個
}LTNode; //方便后續(xù)使用，不需要重復些struct
 
//初始化鏈表（二級指針版本）
/*void ListInit(LTNode** pphead);*/
//初始化鏈表（一級指針版本）
LTNode* ListInit();
 
//打印鏈表
void ListPrint(LTNode* phead);
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//銷毀鏈表
void ListDestory(LTNode* phead);
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾刪
void ListPopBack(LTNode* phead);
//頭插
void ListPushFront(LTNode* phead, LTDataType x);
//頭刪
void ListPopFront(LTNode* phead);
 
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x);
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos);

List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//創(chuàng)建新節(jié)點
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新創(chuàng)建的節(jié)點
}
//初始化鏈表（二級指針版）
/*void ListInit(LTNode** pphead)
{
	//傳二級指針，那么當然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節(jié)點，所以一開始就要給一個節(jié)點
	//為了循環(huán)，要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優(yōu)先級，*pphead要加括號
	(*pphead)->prev = *pphead;
}*/
//初始化鏈表（一級指針版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//打印鏈表
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}
//銷毀鏈表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷毀從第一個節(jié)點到尾部的數(shù)據(jù)
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節(jié)點phead
	free(phead);
	phead = NULL;
}
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言，防止頭節(jié)點為空
	/*
	法一：
	LTNode* tail = phead->prev; //找到尾節(jié)點，便于后續(xù)插入數(shù)據(jù)
	LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點
	//將此新插入的尾節(jié)點與上一個節(jié)點鏈接起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節(jié)點與哨兵位phead鏈接起來構成循環(huán)
	newnode->next = phead;
	phead->prev = newnode;
	*/
	//法二：
	ListInsert(phead, x);
}
//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節(jié)點
	/*
	法一：
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節(jié)點
	free(tail);
	tail = NULL;
	//將鏈表循環(huán)起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
	*/
	//法二：
	ListErase(phead->prev);
}
 
//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節(jié)點
	ListErase(phead->next);
}
 
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//創(chuàng)建插入數(shù)據(jù)的新節(jié)點
	LTNode* newnode = BuyLTNode(x);
	//鏈接左側
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//鏈接右側
	newnode->next = pos;
	pos->prev = newnode;
}
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個指針保存pos兩邊的節(jié)點
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next鏈接起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
}
 
void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}
 
void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數(shù)字3就插入
	}
	ListPrint(pList);//打印
}
 
void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個數(shù)字
	}
	ListPrint(pList);//打印
}
 
void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處數(shù)據(jù)
		pos = NULL; //形參的改變不會影響實參，最好在這置空pos
	}
	ListPrint(pList);//打印
}
 
void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	//頭插3個數(shù)字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾刪3個數(shù)字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//頭刪3個數(shù)字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}
 
void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數(shù)字
	}
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	TestList7();
	return 0;
}

五、拓展

對比順序表和鏈表

不同點	順序表	鏈表
存儲空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機訪問	支持O(1)	不支持O(N)
任意位置插入或者刪除元素	可能需要搬移元素，效率低O(N)	只需修改指針指向
插入	動態(tài)順序表，空間不夠時需要擴容	沒有容量的概念
應用場景	元素高效存儲+頻繁訪問	任意位置插入和刪除數(shù)據(jù)
緩存利用率	高	低

優(yōu)缺點對比：

順序表

鏈表

優(yōu)點

1、物理空間是連續(xù)的，方便用下標隨機訪問。

2、CPU高速緩存命中率會更高。（補充）

1、按需申請釋放空間。

2、任意位置可以O(1)插入刪除數(shù)據(jù)。

缺點

1、正因為物理空間連續(xù)，空間不夠需要擴容，擴容本身又一定消耗，其次擴容機制還存在一定的空間浪費。

2、頭部或者中部插入刪除，挪動數(shù)據(jù)，效率低，O(N)。

1、不支持下標的隨機訪問。

2、有些算法不適合在它上面進行，如：二分查找、排序等。

到此這篇關于C語言超詳細講解數(shù)據(jù)結構中雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關C語言雙向帶頭循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

C語言共用體（Union）詳解及示例代碼
本文主要介紹C語言共用體,這里整理了相關資料及示例代碼，幫助大家學習理解此部分的知識，有興趣的小伙伴可以參考下
2016-08-08
C語言開發(fā)實現(xiàn)通訊錄管理系統(tǒng)
這篇文章主要為大家詳細介紹了C語言開發(fā)實現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-08-08
C語言數(shù)組棧實現(xiàn)模板
這篇文章主要為大家詳細介紹了C語言數(shù)組棧實現(xiàn)模板，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-12-12
C++ Primer Plus 第四章之C++ Primer Plus復合類型學習筆記
數(shù)組（array）是一種數(shù)據(jù)格式，能夠存儲多個同類型的值。每個值都存儲在一個獨立的數(shù)組元素中，計算機在內(nèi)存中依次存儲數(shù)組的各個元素，今天給大家重點介紹C++ Primer Plus復合類型的實例詳解，感興趣的朋友一起看看吧
2021-07-07
OpenCV提取圖像中圓線上的數(shù)據(jù)具體流程
在對圖像進行處理時，經(jīng)常會要提取出圖像中某條直線、圓線或者ROI區(qū)域內(nèi)的感興趣數(shù)據(jù)，進行重點關注。本文主要介紹了利用OpenCV獲取圖像中圓線上的數(shù)據(jù)，需要的可以參考一下
2021-11-11
C++右值引用與移動構造函數(shù)基礎與應用詳解
左值和右值都是針對表達式,左值是指表達式結束后依然存在的持久對象,右值是指表達式結束時就不再存在的臨時對象,下面這篇文章主要給大家介紹了關于C++11右值引用和移動語義的相關資料,需要的朋友可以參考下
2023-02-02
C++?高精度乘法運算的實現(xiàn)
本文主要介紹了C++?高精度乘法運算的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2023-01-01
C++中簡單讀寫文本文件的實現(xiàn)方法
本篇文章是對C++中簡單讀寫文本文件的方法進行了詳細的分析介紹，需要的朋友參考下
2013-05-05
VC中SendMessage和PostMessage的區(qū)別
這篇文章主要介紹了VC中SendMessage和PostMessage的區(qū)別,較為全面的分析了SendMessage和PostMessage運行原理及用法上的不同之處,非常具有實用價值,需要的朋友可以參考下
2014-10-10
VS Code遠程連接Linux服務器調(diào)試C程序的操作方法
這篇文章主要介紹了VS Code遠程連接Linux服務器調(diào)試C程序的操作方法,打開遠程 Linux 服務器上的文件夾本文以 /root/ 為例,給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧
2023-12-12

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網(wǎng)絡編程

在線工具

數(shù)據(jù)庫

CMS

常用工具

C語言超詳細講解數(shù)據(jù)結構中雙向帶頭循環(huán)鏈表

目錄

一、概念

二、必備工作

2.1、創(chuàng)建雙向鏈表結構

2.2、初始化鏈表

2.3、動態(tài)申請節(jié)點

2.4、打印鏈表

2.5、銷毀鏈表

三、主要功能

3.1、在pos節(jié)點前插入數(shù)據(jù)

尾插

頭插

3.2、刪除pos處節(jié)點數(shù)據(jù)

尾刪

頭刪

3.3、查找數(shù)據(jù)

四、總代碼

List.h 文件

List.c 文件

Test.c 文件

五、拓展

相關文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

C語言超詳細講解數(shù)據(jù)結構中雙向帶頭循環(huán)鏈表

目錄

一、概念

二、必備工作

2.1、創(chuàng)建雙向鏈表結構

2.2、初始化鏈表

2.3、動態(tài)申請節(jié)點

2.4、打印鏈表

2.5、銷毀鏈表

三、主要功能

3.1、在pos節(jié)點前插入數(shù)據(jù)

尾插

頭插

3.2、刪除pos處節(jié)點數(shù)據(jù)

尾刪

頭刪

3.3、查找數(shù)據(jù)

四、總代碼

List.h 文件

List.c 文件

Test.c 文件

五、拓展

相關文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

一、概念

2.1、創(chuàng)建雙向鏈表結構

2.2、初始化鏈表

2.3、動態(tài)申請節(jié)點

2.4、打印鏈表

2.5、銷毀鏈表

三、主要功能

3.1、在pos節(jié)點前插入數(shù)據(jù)

3.2、刪除pos處節(jié)點數(shù)據(jù)

3.3、查找數(shù)據(jù)

五、拓展