数据结构|新手向超好理解的带头双向循环链表 c语言|链表

- 一、易错接口详解
- - 1.1 链表初始化
  - 1.2 链表的销毁
  - 1.3 尾删
  - 1.4 在任意节点前插入
- 二、简单接口实现
- - 2.1 打印函数
  - 2.2 尾插
  - 2.3 头插
  - 2.4 尾删
  - 2.5 计算链表有效节点个数
  - 2.6 通过值查找节点
  - 2.7 对任意节点(头节点除外)删除
- 三、头文件和相关定义

一、易错接口详解 1.1 链表初始化
初始化链表，即需要开辟一个头节点，这个头节点中的值没有意义，这个头节点的两个指针next和prev要指向自己。详情内容请跳转至第三大部分，即可查看结构体的定义。
第一步需要开辟相应的空间，于是封装一个创建新节点的函数BuyListNode。

static LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) {printf("malloc fail\n"); exit(-1); } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; newnode->prev = NULL; return newnode; }

加上static修饰，只会在该文件内被调用。
之后就调整这个新节点的next和prev指向头节点自己。

LTNode* ListInit() { LTNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }

调用BuyListNode函数时参数为0，因为头节点中的值没有意义，所以可以随意赋值。
1.2 链表的销毁
调用这个接口通常是在程序结束前将内存释放，还给操作系统，避免内存泄漏。
因为是循环链表，所以可以无限制地走下去，所以控制何时停止释放是关键。
要考虑特殊情况，参数为空指针就直接断言报错。
【数据结构|新手向超好理解的带头双向循环链表】若只有一个头节点（不含有效节点），那么就直接free掉头节点。

void ListDestroy(LTNode* phead) { assert(phead); if (phead->next == NULL) {free(phead); phead = NULL; return; } LTNode* cur = phead->next; while (cur != phead) {LTNode* next = cur->next; free(cur); cur = NULL; cur = next; } free(cur); cur = NULL; }

但是需要注意的是，调用该接口时，一般直接传入的是链表头节点地址（接口中对应的形参只是一份临时拷贝），而不是二级指针，这样会导致调用完这个接口后，该头节点指针变成野指针，即指向的空间已被释放，所以还需要调用者自己手动释放。这种情况可以类比free函数的调用。ListErase接口同理。
使用一级指针，外面用了以后，存在野指针的问题，但是他保持了接口的一致性。
用二级指针，解决了野指针问题。但从接口设计的角度，有点混乱。
1.3 尾删
尾删的调用必须保证链表中有不包括头节点的有效节点，同时头节点也不能为空。
判断链表是否为空的这个功能可以封装为一个函数。
尾删算法：尾节点的前一个节点的next指向头节点，头节点的prev指向尾节点的前一个节点，再free掉尾节点即可。

bool ListEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }void ListPopBack(LTNode* phead) { assert(phead); assert(!ListEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }

1.4 在任意节点前插入
单向链表在任意节点后插入的效率更高，因为不用通过首节点找尾，但是缺点是不能头插（这里指的是无头的链表）。
而带头双向循环就可避免这个缺点，因为不管怎么插效率都高，所以采用在任意节点前插入。
算法：保留指定节点的前一个节点，记作prev，创建一个新节点newnode，更改指定节点pos、prev、newnode的指针指向即可。

void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

二、简单接口实现 2.1 打印函数

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

2.2 尾插

void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); phead->prev->next = newnode; newnode->prev = phead->prev; phead->prev = newnode; newnode->next = phead; }

2.3 头插

void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead->next = newnode; newnode->prev = phead; next->prev = newnode; newnode->next = next; }

2.4 尾删

void ListPopFront(LTNode* phead) { assert(phead); assert(!ListEmpty(phead)); LTNode* fNode = phead->next; LTNode* next = fNode->next; free(fNode); fNode = NULL; phead->next = next; next->prev = phead; }

2.5 计算链表有效节点个数

size_t ListSize(LTNode* phead) { assert(phead); size_t count = 0; LTNode* cur = phead->next; while (cur != phead) {count++; cur = cur->next; } return count; }

2.6 通过值查找节点

LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) {if (cur->data =https://www.it610.com/article/= x) {return cur; } cur = cur->next; } return NULL; }

2.7 对任意节点(头节点除外)删除

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

三、头文件和相关定义

#pragma once #include #include #include #include typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; LTNode* ListInit(); void ListDestroy(LTNode* phead); void ListPrint(LTNode* phead); void ListPushBack(LTNode* phead, LTDataType x); void ListPushFront(LTNode* phead, LTDataType x); void ListPopBack(LTNode* phead); void ListPopFront(LTNode* phead); bool ListEmpty(LTNode* phead); size_t ListSize(LTNode* phead); LTNode* ListFind(LTNode* phead, LTDataType x); void ListInsert(LTNode* pos, LTDataType x); void ListErase(LTNode* pos);