数据结构-带头双向循环链表

前言：

链表有很多种，上一章结，我复盘了单链表，这一章节，主要针对双链表的知识点进行，整理复盘，如果将链表分类的话，有很多种，我就学习的方向考察的重点，主要针对这两种链表进行整理。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。带头双向循环链表如下图所示。 

 

---

目录

1. 带头双向链表的实现

 1.1封装链表节点结构体

1.2建立新的节点 

 1.3初始化链表

1.4尾插函数 

 1.5尾删

 1.6头插

1.7头删

1.8显示

1.9销毁

1.10查找

1.11插入

1.12擦除

1.13判空

---

 

1. 带头双向链表的实现

 1.1封装链表节点结构体

typedef int LDataType;typedef struct ListNode
{LDataType data;//自身数据struct ListNode* prev;指向前一个节点指针struct ListNode* next;指向后一个节点指针}LTNode;

1.2建立新的节点 

 链表的增删查改都会有新的节点，所以我们可以封装一个建立节点的函数，具体代码如下:

LTNode* BuyNode(LDataType x)
{LTNode* temp = (LTNode*)malloc(sizeof(LTNode));if (temp == NULL){perror("malloc:fail");exit(-1);}temp->data = x;temp->next = NULL;temp->prev = NULL;return temp;
}

 1.3初始化链表

 因为是带头节点，初始化会改变节点指向，如果按照单链表的操作习惯，我们可能穿指针变量的地址，用二级指针接收，但是也没必要，我们可以让函数返回的类型，为指针，具体代码如下：

LTNode* ListInit()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

1.4尾插函数 

 因为头结点的prev指向tail，tail的next节点指向head所以我们只要改变节点指向就可以完成尾插，如图所示：

具体代码如下： 

void PushBack(LTNode* pa, LDataType x)
{assert(pa);LTNode* newnode = BuyNode(x);LTNode* tail = pa->prev;tail->next = newnode;newnode->prev = tail;pa->prev = newnode;newnode->next = pa;}

 1.5尾删

 删掉最后一个节点，并改变节点指向

具体代码如下：

void PopBack(LTNode* pa)
{assert(pa);LTNode* tail = pa->prev;LTNode* middle = tail->prev;middle->next = pa;pa->prev = middle;free(tail);tail = NULL;}

 1.6头插

 

代码如下：

void PushFront(LTNode* pa, LDataType x)
{assert(pa);LTNode* newnode = BuyNode(x);LTNode* middle = pa->next;newnode->next = middle;middle->prev = newnode;pa->next = newnode;newnode->prev = pa;
}

1.7头删

 代码如下

void PopFront(LTNode* pa)
{assert(pa);LTNode* middle = pa->next;LTNode* cur = middle->next;pa->next = cur;cur->prev = pa;free(middle);middle = NULL;
}

1.8显示

 增删查改之后，需要显示在终端，所以要有打印显示函数

void ListPrint(LTNode* pa)
{LTNode* cur = pa->next;while (cur != pa) {printf("%d<=>", cur->data);cur = cur->next;}printf("NULL\n");
}

1.9销毁

 在堆上创建的空间，使用完成后，要返还给操作系统。

void ListDestroy(LTNode* pa)
{LTNode* cur = pa->next;LTNode* prev = NULL;while (cur != pa){LTNode* prev = cur;cur = cur->next;free(prev);}free(pa);pa->next = pa->prev = NULL;
}

1.10查找

 查找指定数值得节点，当查找到的时候返回该数值得地址，如果没有查找到则返回空指针。

LTNode* ListFind(LTNode* pa, LDataType x)
{assert(pa);LTNode* cur = pa->next;while (cur != pa){if (cur->data != x){cur = cur->next;}else{return cur;}}return NULL;}

1.11插入

 在当前节点的前一个位置插入节点

void ListInsert(LTNode* pa, LTNode* pos, LDataType x)
{assert(pa);assert(pos);LTNode* newnode = BuyNode(x);LTNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;prev->next = newnode;newnode->prev = prev;}

1.12擦除

 将当前节点去除掉。

void ListErase(LTNode* pa, LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;}

1.13判空

如果头节点的下个指向为自己这个表达式为真的话，则返回true 否则返回false。 

bool LTEmpty(LTNode* pa)
{return pa->next == pa;
}