当前位置：首页 > news >正文

带头双向循环链表及链表总结

news 文章来源：https://blog.csdn.net/lzfnb666/article/details/129459805 2025/4/20 18:20:12

1、链表种类大全

1、链表严格来说可能用2*2*2=8种结构，从是否带头，是否循环，是否双向三个角度区分。

2、无头单向循环链表一般不会在实际运用中直接存储数据，而会作为某些更复杂结构的一个子结构，毕竟它只在头插、头删时具有效率上的优势。

3、带哨兵卫的头有利于解决尾插时多种讨论的复杂情况。

双向有利于insert、erase的实现，这两个函数涉及到对pos位置结点的前一个结点的操作，而双向链表由于存放了prev指针，可以轻松找到前一个结点（不用为了找前一个结点而再次遍历），从而完成相关功能。

循环有利于直接通过phead->prev找到tail，不用遍历，提高尾部操作的效率。

2、接口函数

//打印
void LTPrint(LTNode* phead);
//初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPustFront(LTNode* phead,LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x);
//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
//pos位置删除
void LTErase(LTNode* pos);

结点的创建

typedef int LTDataType;typedef struct LTNode
{struct LTNode* prev;struct LTNode* next;LTDataType data;}LTNode;

与之前相同，以int类型作为链表存储的数据类型。

3、初始化

在之前的无头单向非循环链表中，我们用一个plist指针指向链表，创建时只需要将plist置空即可，操作简单，不需要通过函数实现。

在顺序表的实现中，要考虑到sz（顺序表当前存储的数据个数），capacity（顺序表当前容量），还有一个指向顺序表的初始指针（避免使用数组导致的一些缺点），过程较复杂需要通过函数。

在带头双向循环链表中，由于需要创建一个哨兵卫的头结点，且为循环结构，next，prev都指向tail，无元素时tail为自己，可以通过init函数来实现。

//初始化
LTNode* LTInit()
{//初始化时创建一个哨兵卫头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (NULL == phead){perror("malloc fail");return NULL;}phead->next = phead->prev = phead;phead->data = -1;return phead;}

phead的data暂且设置一个-1，其它值也可以。

4、打印

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

phead一定不为NULL，因此可以assert(phead)防止使用者误传入NULL。

phead头结点不为实际值，因此从phead->next开始遍历，cur只要不为phead的都要进入循环完成打印。

5、尾部操作

1、创建新结点

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (NULL == newnode){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode;}

插入操作前，需要malloc一个新结点。为防止野指针，在创建过程中就将其next和prev置为空

2、判断链表是否为空

删除操作前，需要判断链表是否为空。

//判断链表原来是否为空的函数
bool IsEmpty(LTNode* phead)
{return phead->next == phead;
}

这里采用bool值，返回值为true（非0），和false（0）两种，需要包含stdbool.h头文件，这里的phead->next如果等于phead，即链表中只有哨兵卫头结点，即为空，返回为1（非0），代表链表的状态为空

3、尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);if (NULL == newnode){perror("BuyLTNode fail");return;}//按照之前的思路，尾插需要先找尾// 这里phead的prev直接找尾   需要4步指针操作LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;}

先利用phead->prev找到原来的尾结点tail，然后创建新的尾结点，随后通过4步指针操作建立newnode与tail和phead的联系。（不用遍历找尾，提高了效率）

带哨兵卫的头结点的优势，不用讨论原链表为空的情况。

4、尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//先判断原来是否为空assert(!IsEmpty(phead));LTNode* tail = phead->prev;LTNode* prev = tail->prev;free(tail);tail = NULL;phead->prev = prev;prev->next = phead; }

assert内为！IsEmpty，即为空时报错。

分别用tail和prev标记要删除的尾结点以及前一个结点，free掉tail，利用两个指针建立prev与phead的联系，使其成为新尾。

多删除时assert报错

6、头部操作

1、头插

//头插
void LTPustFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);if (NULL == newnode){perror("BuyLTNode fail");return;}newnode->next = phead->next;phead->next->prev = newnode;newnode->prev = phead;phead->next = newnode;}

通过4个指针建立newnode与phead、phead->next的联系，要注意顺序，先建立与phead->next

的，否则其会被改变无法找到。

当然，在开始时新建立一个next指针指向phead->next的结点也可以。

2、头删


//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!IsEmpty(phead));LTNode* first = phead->next;phead->next = first->next;first->next->prev = phead;free(first);first = NULL;}

先利用first标记要删除的头结点，然后用两个指针建立phead与first的next结点之间的关系，最后free掉first。

头部操作本身就是链表的优势，因此仍不需要遍历

7、查找及指定位置pos操作

1、查找函数

//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x)
{assert(phead);assert(!IsEmpty(phead));LTNode* pos = phead->next;while (pos != phead){if (pos->data == x){return pos;}pos = pos->next;}printf("没找到\n");exit(0);
}

从phead->next的位置开始遍历，找到了则用pos返回该结点的地址，使用者可以用一个ret指针在外部接收，找不到则终止程序。查找前先确认链表不为空。

通过调试观察到，ret拿到了值为3的结点的地址

还可以继续展开，观察带头双向循环链表的内部结构，是怎样完成循环的。

2、insert指定位置前插入

//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prevptr = pos->prev;prevptr->next = newnode;newnode->next = pos;newnode->prev = prevptr;pos->prev = newnode;}

先用prevptr找到pos的前一个结点，然后利用4个指针建立newnode与这两个结点的关系，完成中间位置插入。

可以用pos->prev指针直接找到前一个结点，不需要查找外的额外遍历，提高了效率。

3、erase指定位置删除

//pos位置删除
void LTErase(LTNode* pos)
{assert(pos);//LTNode* prevpos = pos->prev;//LTNode* nextpos = pos->next;//prevpos->next = nextpos;//nextpos->prev = prevpos;//free(pos);//pos = NULL;pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

同样找到pos前一个位置的结点，连接pos前一个与后一个结点，然后free掉pos

4、优化头尾操作

只要有了insert和erase两个函数，就可以轻易完成头尾的4个操作函数，只需要复用上述两个即可

例如在pos前插入一个节点，实际效果为尾插。

insert(pos->next)效果为头插

erase(phead->next)为头删

erase(phead->prev)为尾删

8、链表的销毁

//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);printf("销毁成功\n");
}

从phead->next位置开始遍历销毁即可，最后使用者在外部对创建的链表手动置空

掌握了以上操作，20分钟写一个链表不是难事

1、链表种类大全

2、接口函数

3、初始化

4、打印

5、尾部操作

1、创建新结点

2、判断链表是否为空

3、尾插

4、尾删

6、头部操作

1、头插

2、头删

7、查找及指定位置pos操作

1、查找函数

2、insert指定位置前插入

3、erase指定位置删除

4、优化头尾操作

8、链表的销毁

1、链表种类大全

2、接口函数

3、初始化

4、打印

5、尾部操作

1、创建新结点

2、判断链表是否为空

3、尾插

4、尾删

6、头部操作

1、头插

2、头删

7、查找及指定位置pos操作

1、查找函数

2、insert指定位置前插入

3、erase指定位置删除

4、优化头尾操作

8、链表的销毁

相关文章：