【数据结构 · 初阶】- 带头双向循环链表
目录
1.尾插
2.初始化
3.尾删、头插、头删
4.查找，返回 pos 指针
5.pos 前插入
优化头插，直接复用
优化尾插，直接复用
6.pos 位删除
头删尾删简化
7.销毁
整体代码
List.h
List.c
Test.c
循环：1.尾 next 指向哨兵位的头。2.哨兵位的头的 prev 指向尾
基本结构：
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;1.尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
//phead tail newnode
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}为什么要 assert ？
这里的 phead 是结构体指针，存放的是 plist 的值。plist 指向 malloc 的新节点。
malloc 的新节点的地址一定不为空。如果为空，就是传错了，所以要 assert
为什么不用二级指针？
改变的都是结构体的变量，用结构体指针足矣。这也是哨兵位的优势所在。
无头单向不循环（单链表）里面，要遍例来找尾；还要判断链表是否为空，如果为空，先赋值
这里就不用刻意找尾；且可以兼容空的情况，方便很多。下面是单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}2.初始化
目标：malloc 一个哨兵位的头节点，让 plist 指向哨兵位头节点
现象：要将头节点的地址传给 plist ，会改变 plist 的值
结论：要用二级指针，不能用一级指针
LTNode* plist = NULL;
LTInit(plist);
void LTInit(LTNode** pphead);
后面的插入，删除都是改变结构体成员，用一级指针，只有这里用二级指针。
还有更好的方式：OJ 题中普遍用
List.c
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("<=head=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("
");
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
//phead tail newnode
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}Test.c
void ListTest1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
}3.尾删、头插、头删
空链表不能删（只有哨兵位的头节点），所以要判断链表是否为空
bool LTEmpty(LTNode* phead)
{
assert(phead);
/*
if (phead->next == phead)
{
return true;
}
else
{
return false;
}
*/
return phead->next == phead;
}尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
tail = NULL;
}头插
（1）2个指针的错误写法
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
......
}如果先搞这两步，就不能轻易找到原来的第一个了
（2）2个指针的正确写法
一定先处理离的远的那一边
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
phead->next->prev = newnode;
newnode->next = phead->next;
phead->next = newnode;
newnode->prev = phead;
}（3）3个指针，顺序随便，效率更高
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* first = phead->next; // 第三个指针
first->prev = newnode;
newnode->next = first;
phead->next = newnode;
newnode->prev = phead
}头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* first = phead->next->next;
LTNode* del = phead->next;
phead->next = first;
first->prev = phead;
free(del);
del = NULL;
}4.查找，返回 pos 指针
LTNode* LTFind(LTNode* phead, LTDataType x); // List.h
LTNode* LTFind(LTNode* phead, LTDataType x) // List.c
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListTest2() // Test.c
{
LTNode* plist = LTInit();
......
LTNode* pos = LTFind(plist, 2);
}5.pos 前插入
要配合查找使用
单链表要遍例找前一个，现在不需要这么麻烦
要用2个指针，先动离的远的，即 pos->prev 和 newnode 的链接
为高效，我们用3个指针
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* prev = pos->prev; // 第3个指针
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}优化头插，直接复用
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);
}优化尾插，直接复用
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);
}
遍例是从 LTNode* cur = phead->next ；开始。从逻辑上就是尾插
6.pos 位删除
配合查找使用
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
//pos = NULL;
}pos置空没用，形参改变不影响实参。
为保持接口风格一致，没有必要用二级指针，通常由使用的人在外面置空
里面变如果改变外面的话，一定有 解引用 操作
void ListTest2()
{
LTNode* plist = LTInit();
......
LTNode* pos = LTFind(plist, 2);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
}LTErase 肯定不能删哨兵位的头节点
但 C语言中不好检查，所以我们暂且不做处理。删哨兵程序会挂
C++的结构好检查
头删尾删简化
void LTPopBack(LTNode* phead)
{
assert(phead);
LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
LTErase(phead->next);
}7.销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* next = cur->next;
while (cur != phead)
{
free(cur);
cur = next;
next = next->next;
}
free(phead);
//phead = NULL;
}
void ListTest2()
{
LTNode* plist = LTInit();
......
LTDestroy(plist);
plist = NULL;
}
整体代码
List.h
#pragma once
#include
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;
LTNode* LTInit();
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead); // 判断链表是否为空
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x); // pos前插入
void LTErase(LTNode* pos); // pos位删除
void LTDestroy(LTNode* phead); List.c
#include "List.h"
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("<=head=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("
");
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
/*
if (phead->next == phead)
{
return true;
}
else
{
return false;
}
*/
return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
/*
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
//phead tail newnode
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
*/
LTInsert(phead, x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
/*
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
tail = NULL;
*/
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*
LTNode* newnode = BuyListNode(x);
LTNode* first = phead->next;
first->prev = newnode;
newnode->next = first;
phead->next = newnode;
newnode->prev = phead
*/
LTInsert(phead->next, x);
}
//void LTPushFront(LTNode* phead, LTDataType x)
//{
// assert(phead);
// LTNode* newnode = BuyListNode(x);
// // 先
// phead->next->prev = newnode;
// newnode->next = phead->next;
// // 后
// phead->next = newnode;
// newnode->prev = phead;
//}
void LTPopFront(LTNode* phead)
{
assert(phead);
/*
assert(!LTEmpty(phead));
LTNode* first = phead->next->next;
LTNode* del = phead->next;
phead->next = first;
first->prev = phead;
free(del);
del = NULL;
*/
LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LTInsert(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;
}
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
//pos = NULL;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* next = cur->next;
while (cur != phead)
{
free(cur);
cur = next;
next = next->next;
}
free(phead);
//phead = NULL;
}Test.c
#include "List.h"
void ListTest1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
}
void ListTest2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 9);
LTPrint(plist);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
ListTest2();
return 0;
}
本篇的分享就到这里了，感谢观看，如果对你有帮助，别忘了点赞+收藏+关注。
小编会以自己学习过程中遇到的问题为素材，持续为您推送文章
