有頭雙向回圈鏈表

🌻🌻筆記和原始碼自取：
🍄筆記地址
🍄原始碼地址

最近接觸了單鏈表，也做了很多題目，但單鏈表的增刪查改真的很麻煩

🌸又最近學習了雙向鏈表，尤其是 有哨兵位頭節點的雙向回圈鏈表

寫起來和用起來真的很爽！！🌸

1. 初始化鏈表

我們需要一個哨兵位頭節點便于尾插頭插

🍀代碼如下：

//初始化鏈表
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

2. 鏈表尾插

首先創建新的節點

//創建新的節點
LTNode* BuyListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	assert(newnode);//沒有會警告，按道理malloc都是會成功的

	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

🌸插入步驟一：

🌸步驟二：

🌸步驟三：

🌸步驟四：

🍀代碼如下：

//尾插
void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;

}

🍀先寫一個列印函式用來測驗：

//列印鏈表
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

🍀測驗插口：

//測驗尾插
void testList1()
{
	LTNode* plist = NULL;
	plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);
}

🍀效果：

3. 鏈表頭插

將newnode插入進去

🌸步驟一和二：

🌸步驟三和四：

🍀代碼：

//頭插
void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

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

}

🍀測驗用例：

//測驗頭插
void testList2()
{
	LTNode* plist = NULL;
	plist = ListInit();

	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);

	ListPrint(plist);
}

🍀效果：

4. 鏈表尾刪

將最后一個節點洗掉

新的尾節點是tail

🌸第一步：

🌸第二步：

🌸第三步：

🍀代碼：

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//不能刪掉哨兵位

	LTNode* tail = phead->prev->prev;
	phead->prev = tail;
	free(tail->next);
	tail->next = phead;

}

🍀測驗用例：

//測驗尾刪
void testList3()
{
	LTNode* plist = NULL;
	plist = ListInit();

	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);

	//尾刪
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);


	ListPrint(plist);
}

🍀效果

5. 鏈表頭刪

洗掉鏈表中cur

🌸第一步：

🌸第二步：

🌸第三步：

🍀代碼：

//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);

}

🍀測驗用例：

//測驗頭刪
void testList4()
{
	LTNode* plist = NULL;
	plist = ListInit();

	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);

	//頭刪
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);


	ListPrint(plist);
}

🍀結果：

6. 鏈表中間插入

其實這一步和尾插有些類似

🌸步驟圖：

7. 鏈表中間洗掉

🌸和尾刪差不多注意不要刪了哨兵

//中間洗掉
void ListErase(LTNode* pos)
{
	assert(pos);
	assert(pos->next);//防止哨兵被刪

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);

}

🍀測驗代碼

//測驗中間插入 + 中間洗掉
void testList5()
{
	LTNode* plist = NULL;
	plist = ListInit();

	//插入
	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);

	//查找
	LTNode* insert = ListFind(plist, 3);

	//中間插入
	ListInsert(plist->prev, 10);//模擬頭插
	ListInsert(plist, 11);//模擬尾插
	ListInsert(insert, 22);//模擬中間

	ListPrint(plist);

	//中間洗掉
	ListErase(insert->next);//洗掉22
	ListErase(plist->next);//頭刪
	ListErase(plist->prev);//尾刪

	ListPrint(plist);
}

🍀測驗結果：