目录
一、双向带头循环链表概述
1.什么是双向带头循环链表
2.双向带头循环链表的优势
3.双向带头循环链表简图
二、双向带头循环链表的增删查改图解及代码实现
1.双向带头循环链表的头插
2.双向带头循环链表的尾插
3.双向带头循环链表的头删
4.双向带头循环链表的尾删
5.双向带头循环链表在pos位置前插入节点
6.双向带头循环链表删除pos位置节点
一、双向带头循环链表概述
1.什么是双向带头循环链表
双向:每个节点都带有一个指向下一个节点的指针(next)和一个直向前一个节点的指针(prev);
带头:即链表带有哨兵位头节点,该节点只包含两个指针,不存储有效数据;
循环:哨兵位头节点有一个next指针指向第一个有效数据节点,还有一个prev指针指向哨兵位节点的前一个节点即链表的尾节点,因此实现了链表的循环;
双向带头循环链表的节点类型:
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
2.双向带头循环链表的优势
双向带头循环链表不需要我们遍历每个节点来找尾节点,对于链表的尾插而言就变得非常简单。由于较单向非循环链表而言,双向带头循环链表多了一个指向前一个节点的指针prev,所以在结构上较为复杂,但实际应用中少了很多的麻烦。
3.双向带头循环链表简图
二、双向带头循环链表的增删查改图解及代码实现
1.双向带头循环链表的头插
示意图:
代码实现:文章来源地址https://www.toymoban.com/news/detail-654537.html
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* NewNode = Node_New(x);
ListNode* First = pHead->next;
NewNode->next = First;
First->prev = NewNode;
NewNode->prev = pHead;
pHead->next = NewNode;
}
2.双向带头循环链表的尾插
示意图:
代码实现:
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* NewNode = Node_New(x);
ListNode* Tail = pHead->prev;
NewNode->prev = Tail;
Tail->next = NewNode;
NewNode->next = pHead;
pHead->prev = NewNode;
}
3.双向带头循环链表的头删
示意图:
代码实现:
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
assert(pHead);
if (pHead->next == pHead)
{
return;
}
ListNode* First = pHead->next;
ListNode* Next = First->next;
pHead->next = Next;
Next->prev = pHead;
free(First);
First = NULL;
}
4.双向带头循环链表的尾删
示意图:
代码实现:
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
assert(pHead);
if (pHead->next == pHead)
{
return;
}
ListNode* Tail = pHead->prev;
ListNode* Prev = Tail->prev;
Prev->next = pHead;
pHead->prev = Prev;
free(Tail);
Tail = NULL;
}
5.双向带头循环链表在pos位置前插入节点
示意图:
代码实现:
// 双向链表在pos位置的前面插入节点
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* NewNode = Node_New(x);
ListNode* Prev = pos->prev;
Prev->next = NewNode;
NewNode->prev = Prev;
NewNode->next = pos;
pos->prev = NewNode;
}
6.双向带头循环链表删除pos位置节点
示意图:
文章来源:https://www.toymoban.com/news/detail-654537.html
代码实现:
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
ListNode* Prev = pos->prev;
ListNode* Hind = pos->next;
Prev->next = Hind;
Hind->prev = Prev;
free(pos);
pos = NULL;
}
到了这里,关于双向-->带头-->循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!