一、带头结点的循环双向链表
二、结点与接口定义
结点定义：
typedef int ListDataType;
typedef struct LinkedListNode
{
struct LinkedListNode* next;
struct LinkedListNode* prev;
ListDataType data;
}LinkedListNode;
接口定义：
LinkedListNode* LinkedListInit();
void LinkedListPrint(LinkedListNode* phead);
bool LinkedListEmpty(LinkedListNode* phead);
void LinkedListPushBack(LinkedListNode* phead, ListDataType x);
void LinkedListPushFront(LinkedListNode* phead, ListDataType x);
void LinkedListPopBack(LinkedListNode* phead);
void LinkedListPopFront(LinkedListNode* phead);
LinkedListNode* LinkedListFind(LinkedListNode* phead, ListDataType x);
// 在pos之前插入
void LinkedListInsert(LinkedListNode* pos, ListDataType x);
// 删除pos位置的值
void LinkedListErase(LinkedListNode* pos);
void LinkedListDestroy(LinkedListNode* phead);
三、实现
3.1 申请节点
我们将申请结点的代码封装成函数，方便后续使用
LinkedListNode* CreateLinkedListNode(ListDataType x)
{
LinkedListNode* newnode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
3.2 初始化
由于是带头结点的双向链表，因此在使用链表前，我们需要对链表进行初始化。
LinkedListNode* LinkedListInit()
{
LinkedListNode* phead = CreateLinkedListNode(230510);
phead->next = phead;
phead->prev = phead;
return phead;
}
3.3 打印
遍历链表，值得说的是，带头结点的双向链表的循环结束条件是 cur != phead
void LinkedListPrint(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* cur = phead->next;
printf("guard<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
3.4 尾插
尾插时，需要先找到尾结点，然后将新结点插入到尾结点后面。
void LinkedListPushBack(LinkedListNode* phead, ListDataType x)
{
assert(phead);
// 1.找到尾结点
LinkedListNode* tail = phead->prev;
// 2.插入到尾结点后面
LinkedListNode* newnode = CreateLinkedListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
3.5 头插
第一种写法，要注意现将newnode后面的结点进行链接，然后再讲newnode链接到phead后面。
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* newnode = CreateLinkedListNode(x);
// 与原来的第一个数据结点链接
newnode->next = phead->next;
phead->next->prev = newnode; // newnode->next->prev = newnode;
// newnode变为新的第一个数据结点
phead->next = newnode;
newnode->prev = phead;
}
第二种写法（推荐写法），我们使用变量记录phead的next，记为first，这样newnode插入到phead和first之间，这样逻辑比较清楚。
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* newnode = CreateLinkedListNode(x);
// 用变量记录第一个结点
LinkedListNode* first = phead->next;
// 与原来的第一个数据结点链接
newnode->next = first;
first->prev = newnode;
// newnode变为新的第一个数据结点
phead->next = newnode;
newnode->prev = phead;
}
3.6 尾删
phead的prev是尾tail，tail的prev是tailPrev。
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* tail = phead->prev;
LinkedListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
上面代码的问题是链表为空的情况报错，于是我们在该函数内部对空链表进行断言：
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 删除时链表不能为空
LinkedListNode* tail = phead->prev;
LinkedListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
3.7 判断链表为空断言
判断链表为空逻辑：
bool LinkedListEmpty(LinkedListNode* phead)
{
assert(phead);
return phead->next == phead;
}
使用链表为空的断言：
assert(!LinkedListEmpty(phead)); // 链表为空时error
3.8 头删
头删时需要将第一个结点删除，很容易便想到以下代码：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 删除时链表不能为空
LinkedListNode* next = phead->next;
phead->next = next->next;
phead->next->prev = phead; // next->next->prev = phead;
free(next);
}
为了提高可读性，推荐使用以下代码，定义first和second两个变量指向第一个和第二个：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead)); // 删除时链表不能为空
LinkedListNode* first = phead->next;
LinkedListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}
3.9 查找find
查找的本质就是遍历链表
LinkedListNode* LinkedListFind(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
3.10 插入insert-在pos之前插入
pos的来源一般是find的结果
void LinkedListInsert(LinkedListNode* pos, ListDataType x)
{
assert(pos);
LinkedListNode* prev = pos->prev;
LinkedListNode* newnode = CreateLinkedListNode(x);
// prev newnode pos
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
3.11 头插尾插复用insert
有了上面的insert在任意位置插入，我们可以修改尾插代码：
void LinkedListPushBack(LinkedListNode* phead, ListDataType x)
{
assert(phead);
// 在phead之前插入，也就是尾插
LinkedListInsert(phead, x);
}
同理也可以修改头插代码：
void LinkedListPushFront(LinkedListNode* phead, ListDataType x)
{
assert(phead);
LinkedListInsert(phead->next, x);
}
3.12 删除erase-删除pos位置
同insert一样，pos也应该是调用者通过find返回的结果。
void LinkedListErase(LinkedListNode* pos)
{
assert(pos);
LinkedListNode* posPrev = pos->prev;
LinkedListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
3.13 头删尾删复用erase
有了上面的erase在任意位置删除，我们可以修改尾删的代码：
void LinkedListPopBack(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead));
LinkedListErase(phead->prev);
}
同理也可以修改头删的代码：
void LinkedListPopFront(LinkedListNode* phead)
{
assert(phead);
assert(!LinkedListEmpty(phead));
LinkedListErase(phead->next);
}
3.14 销毁destroy
记得释放头结点phead：
void LinkedListDestroy(LinkedListNode* phead)
{
assert(phead);
LinkedListNode* cur = phead->next;
while (cur != phead)
{
LinkedListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
源码
gitee-LinkedList
总结
带头结点、双向、循环链表的实现都非常的简单，需要注意判空条件与遍历终止的条件。文章来源：https://www.toymoban.com/news/detail-438544.html
在代码写法上，对于某个节点的前一个或后一个的问题，我们最好分别使用变量去记录，这样代码的逻辑更清晰，可读性更高。例如尾插时的tail，尾删时的tail和tailPrev，以及头删时的first与second，erase中的posPrev与posNext，这些变量的使用，提高了代码的可读性。文章来源地址https://www.toymoban.com/news/detail-438544.html
到了这里，关于【数据结构】C语言实现双向链表（带头结点、循环）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
