文章目录

• 前言
• 一、什么是带头双向循环链表
• 二、带头双向循环链表的实现
• • 2.1、动态开辟一个空间
  • 2.2、初始化与打印
  • 2.3、插入操作
  • • 尾插
    • 头插
    • 在pos之前插入
  • 2.4、删除操作
  • • 尾删
    • 头删
    • 删除pos处的位置
  • 2.4、查找与销毁操作

前言

本文我们所要实现的是循环链表，即带头双向循环链表

一、什么是带头双向循环链表

带头双向循环链表与无头单向非循环链表不同的是，它结构复杂，一般用于单独存储数据，实际中使用的链表数据结构，均是带头双向循环链表。而无头单向非循环链表结构简单，一般不会用来单独存储数据，实际更多用于其他数据结构的子结构。

二、带头双向循环链表的实现

在实现循环链表增删查改之前，首先应该创建一个循环链表

typedef int CLTDataType;typedef struct CListNode
{struct CListNode* next;struct CListNode* prev;CLTDataType data;
}CLTNode;

其中prev是前一个结点地址，next是下一个结点。

2.1、动态开辟一个空间

代码如下（示例）：

CLTNode* BuyListNode(CLTDataType x)
{CLTNode* newnode = (CLTNode*)malloc(sizeof(CLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

2.2、初始化与打印

1、初始化

代码如下（示例）：

CLTNode* LTInit()
{CLTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

2、打印

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

2.3、插入操作

尾插

void LTPushBack(CLTNode* phead, CLTDataType x)
{assert(phead);CLTNode* newnode = BuyListNode(x);CLTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

头插

头插一共两种写法

第一种：

先让新结点的next指向下一个结点，再让头结点的next指向新结点，有先后顺序。

代码如下：

void LTPushFront(CLTNode* phead, CLTDataType x)
{assert(phead);CLTNode* newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

第二种：

创建一个新指针，无先后顺序

代码如下：

void LTPushFront(CLTNode* phead, CLTDataType x)
{assert(phead);CLTNode* newnode = BuyListNode(x);CLTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

在pos之前插入

pos在head处时，进行尾插

pos在d1处时，进行头插

代码如下：

void LTInsert(CLTNode* pos, CLTDataType x)
{assert(pos);CLTNode* prev = pos->prev;CLTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

在头删和尾删也可直接调用此函数
头删：LTInsert(phead, x)
尾删：LTInsert(phead->next, x)

2.4、删除操作

尾删

void LTPopBack(CLTNode* phead)
{assert(phead);assert(phead->next != phead);CLTNode* tail = phead->prev;CLTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);
}

头删

代码如下：

void LTPopFront(CLTNode* phead)
{assert(phead);assert(phead->next != phead);CLTNode* first = phead->next;CLTNode* second = first->next;free(first);phead->next = second;second->prev = phead;}

删除pos处的位置

代码如下：

void LTErase(CLTNode* pos)
{assert(pos);CLTNode* prev = pos->prev;CLTNode* next = pos->next;free(pos);prev->next = next;next->prev = prev;
}

在头删和尾删也可直接调用此函数
头删：LTErase(phead->next)
尾删：LTErase(phead->prev)

2.4、查找与销毁操作

1、查找

代码如下：

CLTNode* LTFind(CLTNode* phead, CLTDataType x)
{assert(phead);CLTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2、销毁

代码如下：

void LTDestroy(CLTNode* phead)
{assert(phead);CLTNode* cur = phead->next;while (cur != phead){CLTNode* next = cur->next;free(cur);cur = next;}free(phead);
}