一、帶頭雙向回圈鏈表

前面我們實作了無頭單向非回圈鏈表，特性為：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在OJ題中出現很多，所以我們才要模擬實作充分了解它的特性，

而無頭單向非回圈鏈表是有缺點的，那就是尾插和尾刪的時候都要找到最后一個結點，時間復雜度為O(N),并且要考慮到是否為頭結點洗掉起來很不方便，
針對這一些缺點我們再來實作帶頭雙向回圈鏈表，帶頭雙向回圈鏈表結構復雜，一般用在單獨存盤資料，結構復雜了一點，但是實作起來卻很簡單，

二、帶頭雙向回圈鏈表實作思路

和前面實作無頭單向非回圈鏈表類似，我們也要創建創建一個結點資料型別，里面為資料域和指標域，不過指標域里面要存放上一個結點的地址和下一個結點的地址，

typedef int DataTypedef; //對int型別重新起個名字叫DataType

struct ListNode
{
	DataTypedef data;        //資料域
	struct ListNode* next;   //指標域，存放下一個結點的地址
	struct ListNode* prev;   //指標域，存放上一個結點的地址
};

//對鏈表型別struct ListNode重新起個名字叫LNode
typedef struct ListNode LNode;

然后有了型別之后我們就在可以創建一個鏈表型別的指標plist，這個指標用來維護帶頭雙向回圈鏈表的頭結點（哨兵位），
接著用指標plist來維護在堆上開辟的哨兵位結點，但是有一點要非常注意：
要進行傳指標plist的地址，不能傳指標plist的內容；
因為想要改變指標plist存放的內容就要傳指標plist的地址，然后要用二級指標來接收plist的地址，從而解參考來改變指標plist所存的內容，這樣才會改變指標plist維護的哨兵位結點，

三、鏈表指標和結點記憶體布局圖

四、帶頭雙向回圈鏈表的初始化

初始化要開辟一個哨兵位結點，為后面的介面做準備，并且這個哨兵位的結點存放上一個和下一個結點的地址都是自己，這樣設計能減少很多麻煩，后面再來分析，我們先實作初始化，代碼如下：

//初始化函式
void ListInit(LNode** pphead)
{
	LNode* tmp = (LNode*)malloc(sizeof(LNode));
	if (tmp == NULL)
	{
		perror("erron ");
		exit(-1);
	}

	tmp->next = tmp;
	tmp->prev = tmp;
	tmp->data = 0;
	*pphead = tmp;
}

五、帶頭雙向回圈鏈表介面實作：

1.尾部插入資料

代碼實作如下：

//開辟新結點函式
LNode* BuyNewNode(DataTypedef x)
{
	LNode* newNode = (LNode*)malloc(sizeof(LNode));
	if (newNode == NULL)
	{
		perror("erron ");
		exit(-1);
	}
	newNode->data = x;
	return newNode;
}

//尾插
void ListPushBack(LNode* phead,DataTypedef x)
{
	assert(phead);
	LNode* newNode = BuyNewNode(x); //開辟一個結點

	//找到最后一個結點,哨兵位的前面就是尾結點
	LNode* tail = phead->prev;

	// tail   newNode  phead;
	//在最后一個結點后面鏈接一個新的結點
	tail->next = newNode;
	newNode->prev = tail;
	phead->prev = newNode;
	newNode->next = phead;
}

如果實作過無頭單向不回圈鏈表，在此程序中我們考慮的情況很多，比如大家肯定會問為什么不考慮鏈表為空只有一個哨兵位的情況呢？這樣特殊的情況還能實作嗎？

這里就體現了初始化的時候要把哨兵位的下一個和上一個結點存的是自己地址的好處了，這樣設計就算鏈為空也能實作，大家可以畫圖分析一下結構設計的非常巧妙，只要有哨兵位在，就不用考慮鏈表是否為空，這也是對無頭單向不回圈鏈表缺點的補充，

2.頭部插入資料

//頭插
void ListPushFront(LNode* phead, DataTypedef x)
{
	assert(phead);
	LNode* newNode = BuyNewNode(x);
	//先找到第一個結點
	LNode* next = phead->next;

	//phead   newNode   next
	//在哨兵位結點和第一個結點之間插入即可
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
}

3.尾部洗掉資料

代碼實作如下：

//尾刪
void ListPopBack(LNode* phead)
{
	assert(phead);
	//要保證鏈表有結點可以洗掉，不能洗掉哨兵位
	assert(phead->next != phead);
	LNode* tail = phead->prev;
	//要找到尾結點的前一個
	LNode* tailPrev = tail->prev;

	//tailPrev  phead
	//把尾結點的前一個和哨兵位連接起來即可
	tailPrev->next = phead;
	phead->prev = tailPrev;
	
	//最后要把尾結點釋放掉
	free(tail);
}

4.頭部洗掉資料

代碼實作如下：

//頭刪
void ListPopFront(LNode* phead)
{
	assert(phead);
	//要保證鏈表有結點可以洗掉，不能洗掉哨兵位
	assert(phead->next != phead);

	//找到第二個結點
	LNode* start = phead->next->next;
	//釋放掉頭結點
	free(phead->next);

	//phead   start
	//把哨兵位和第二個結點連接起來即可
	phead->next = start;
	start->prev = phead;
}

5.顯示資料

顯示資料把結點里面的資料域列印出來即可，代碼如下：

//顯示資料
void ListPrint(LNode* phead)
{
	assert(phead);
	//從哨兵位的下一個結點開始遍歷
	LNode* cur = phead->next;

	//等于哨兵位就是回到起始點，停止遍歷
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

6.查找資料

查找資料域里面的資訊，如果相等了就回傳改結點的地址，代碼如下：

//查找資料
LNode* ListFind(LNode* phead, DataTypedef x)
{
	assert(phead);
	//從哨兵位的下一個結點開始找
	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//找不到就回傳空指標
	return NULL;
}

7.在結點前面插入資料

代碼如下：

//在結點前面插入
void ListInsert(LNode* pos, DataTypedef x)
{
	assert(pos);
	//找到pos位置前面一個結點
	LNode* posPrev = pos->prev;
	LNode* newNode = BuyNewNode(x);


	//posPrev  newNode  pos
	//在它們之間插入即可
	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;

}

8.洗掉當前位置資料

實作代碼如下：

//洗掉當前結點資料
void ListErase(LNode* pos)
{
	assert(pos);
	//找到pos位置前一個和后一個結點
	LNode* posPrev = pos->prev;
	LNode* posNext = pos->next;

	// posPrev   posNext
	//把它們連起來即可
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

9.記憶體釋放

//記憶體釋放
void ListDestroy(LNode** pphead)
{
	assert(pphead);
	//從哨兵位的下一個結點開始釋放
	LNode* cur = (*pphead)->next;
	while (cur != *pphead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//最后把哨兵位給釋放掉
	free(*pphead);
	*pphead = NULL;
}

六、對頭插 尾插 頭刪 尾刪的改造

大家可以發現我們的插入和洗掉函式與頭插 尾插 頭刪 尾刪是非常相似的，所以我們可以不必要重新寫一個頭插 尾插 頭刪 尾刪；我們直接呼叫插入和洗掉函式即可，
改造如下：

//尾插
void ListPushBack(LNode* phead,DataTypedef x)
{
	assert(phead);
	
	//在哨兵位結點前面插入就是尾插
	//呼叫插入函式即可
	ListInsert(phead, x);
}

//頭插
void ListPushFront(LNode* phead, DataTypedef x)
{
	assert(phead);
	
	//在哨兵位結點的下一個結點前面插入就是頭插
	//直接呼叫插入函式
	ListInsert(phead->next, x);
}

//尾刪
void ListPopBack(LNode* phead)
{
	assert(phead);
	//要保證鏈表有結點可以洗掉，不能洗掉哨兵位
	assert(phead->next != phead);

	//洗掉哨兵位結點的前面一位就是尾刪
	//直接呼叫洗掉函式
	ListErase(phead->prev);
}

//頭刪
void ListPopFront(LNode* phead)
{
	assert(phead);
	//要保證鏈表有結點可以洗掉，不能洗掉哨兵位
	assert(phead->next != phead);

	//洗掉哨兵位的下一個結點就是頭刪
	//直接呼叫洗掉函式
	
	ListErase(phead->next);
}

這樣的改造我們就可以大大的提高我們實作的效率，就可以快速的實作一個帶頭雙向回圈鏈表，

七、總結（附原始碼）

以上就是帶頭雙向回圈鏈表實作內容了，其中前面我只有把源檔案List.c 和測驗檔案test.c拆開來分析了，如果想要帶頭雙向回圈鏈表的全部內容，闊以移步到gitee上獲取

源檔案獲取地址，點擊即可