带头循环双向链表
优势是什么
先看看长啥样子
每一个节点都记录该节点的前后的节点,这会有什么好处呢?
头插头删,尾插尾删特别方便时间复杂度都是O(1)
另一个优势是既能从前往后走,又能从后往前走。
带哨兵位头节点双向循环链表的基本操作
这一次,会写的规范一点。
准备3个文件,一个头件,一个链表操作文件,一个主函数所在的文件,和通讯录那一篇设计是一样的。
H:带头,D:双向,Loop:循环,List:链表
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
//开辟+初始化头节点
ListNode* AollocListNode(int x);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos, ListNode* pHead);
开辟节点+初始化
申请一个节点,并初始化。
有下面两种形式,但当链表为空的时候,是成环的,建议用下面一种。
这样设计以后函数形参中的指针是不可为NULL的,可以加一个assert判断一下。
ListNode* AollocListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->_data = x;
newnode->_next = newnode;
newnode->_prev = newnode;
return newnode;
}
打印
这里需要另外一个指针遍历去遍历链表,当回到头节点的时候即结束,如果使用pHead去遍历,那就死循环了。
void ListPrint(ListNode* pHead)
{
ListNode* p = pHead->_next;//指向第一个节点
while (p != pHead)
{
printf("%d->", p->_data);
p = p->_next;
}
printf("NULL\n");
}
销毁
销毁链表,释放所有节点
循环中,先把除头节点外的所有节点删除,出了循环再删除头节点。
循环结束的条件和打印一样,当指向头节点的时候就结束了
删除一个节点,指针的指向怎么改变呢?
拷贝第一个节点,头节点指向指向第二个节点,第二个节点指向头节点,指向完成后,就可以删除了。
void ListDestory(ListNode* pHead)
{
assert(pHead);
while (pHead->_next != pHead)
{
struct ListNode* t = pHead->_next;//先记录要被释放的节点(第一个节点)
pHead->_next = t->_next;
t->_next->_prev = pHead;
free(t);
}
free(pHead);
}
插入 头插
头插指的是在头节点后面插入一个新的节点作为第一个节点。
改变指向有两种形式,一种是再来一个临时变量记录中间节点。另一种是在原有的变量种改变指向。
这里详细介绍原有变量改变指向
①②顺序可以颠倒
有两种形式去找原第一个节点,可以通过,也可以通过头节点。
通过头节点去找原第一个节点,③④顺序不可颠倒。通过去找原第一个节点,③④顺序无所谓。
④:pHead->_next =
③:pHead->_next->_prev =
先执行④单循环链表,pHead->_next不再指向原第一个节点
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = AollocListNode(x);
newnode->_prev = pHead;
newnode->_next = pHead->_next;
pHead->_next->_prev = newnode;
pHead->_next = newnode;
//newnode->_next->_prev = newnode;
}
有中间变量的形式
这样看起来逻辑会更清晰,但我还是会用上面一种,要多用才多熟悉,这些指针指向,所以下面我都是不用中间变量的。
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = AollocListNode(x);
ListNode* t = pHead->_next;//记录原第一个节点
newnode->_next = t;
t->_prev = newnode;
pHead->_next = newnode;
newnode->_prev = pHead;
}
尾插
尾插:的下一个指向的是头节点,一种是靠pHead,另一种是靠原最后一个节点去找头节点。组合方式很多不一一列举,不创建另外的变量记录原最后一个节点时,原最后一个节点改变指向之前,头节点的指向不能动。
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = AollocListNode(x);
newnode->_next = pHead;
newnode->_prev = pHead->_prev;
pHead->_prev->_next = newnode;//原最后一个节点 指向新节点
pHead->_prev = newnode;//头节点指向新节点
}
删除 头删
这个很简单了,就是刚刚销毁操作,不带循环,当个快乐的cv工程师吧。
void ListPopFront(ListNode* pHead)
{
assert(pHead);
ListNode* t = pHead->_next;//记录第一个节点
pHead->_next = t->_next;
t->_next->_prev = pHead;
free(t);
}
尾删
也很简单,记录最后一个节点,在将倒数第二个节点和头节点相互连接,再去释放。
void ListPopBack(ListNode* pHead)
{
assert(pHead);
ListNode* t = pHead->_prev;//记录最后一个节点
t->_prev->_next = pHead;
pHead->_prev = t->_prev;
free(t);
}
找并返回地址,pos接收
通过data找节点,再把节点的地址返回。在通过这个pos执行下面两个操作。
循环结束的条件是回到了头节点。
ListNode ListFind(ListNode pHead, LTDataType x)
{
assert(pHead);
ListNode* p = pHead->_next;//指向第一个节点
while (p != pHead)
{
if (x == p->_data)
return p;
p = p->_next;
}
return NULL;
}
在pos前插入
双向单链表的优势来了,只要知道地址,不需要遍历,可以直接插入,时间复杂度O(1)。如果是单向的,还要找前驱。
需要对pos判断一下不能为NULL
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = AollocListNode(x);
newnode->_next = pos;
newnode->_prev = pos->_prev;
pos->_prev->_next = newnode;
pos->_prev = newnode;
}
删除在pos前的节点
删除的时同样要注意pos不能为NULL。不能删除头节点单循环链表,不然主函数中的头指针会非法访问。
void ListErase(ListNode pos, ListNode pHead)
{
assert(pos);
assert(pos->_prev != pHead);//判断pos前一个节点不为头节点
ListNode* t = pos->_prev;//记录pos前一个节点
t->_prev->_next = pos;
pos->_prev = t->_prev;
free(t);
}
.c
#include"HDLoopList.h"
//开辟+初始化节点
ListNode* AollocListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->_data = x;
newnode->_next = newnode;
newnode->_prev = newnode;
return newnode;
}
void ListPrint(ListNode* pHead)
{
ListNode* p = pHead->_next;//指向第一个节点
while (p != pHead)
{
printf("%d->", p->_data);
p = p->_next;
}
printf("NULL\n");
}
void ListDestory(ListNode* pHead)
{
assert(pHead);
while (pHead->_next != pHead)
{
struct ListNode* t = pHead->_next;//先记录要被释放的节点(第一个节点)
pHead->_next = t->_next;
t->_next->_prev = pHead;
free(t);
}
free(pHead);
}
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = AollocListNode(x);
newnode->_prev = pHead;
newnode->_next = pHead->_next;
pHead->_next->_prev = newnode;
pHead->_next = newnode;
//newnode->_next->_prev = newnode;
}
//void ListPushFront(ListNode* pHead, LTDataType x)
//{
// ListNode* newnode = AollocListNode(x);
// ListNode* t = pHead->_next;
//
// newnode->_next = t;
// t->_prev = newnode;
//
// pHead->_next = newnode;
// newnode->_prev = pHead;
//}
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = AollocListNode(x);
newnode->_next = pHead;
newnode->_prev = pHead->_prev;
pHead->_prev->_next = newnode;//原最后一个节点 指向新节点
pHead->_prev = newnode;//头节点指向新节点
}
void ListPopFront(ListNode* pHead)
{
assert(pHead);
ListNode* t = pHead->_next;//记录第一个节点
pHead->_next = t->_next;
t->_next->_prev = pHead;
free(t);
}
void ListPopBack(ListNode* pHead)
{
assert(pHead);
ListNode* t = pHead->_prev;//记录最后一个节点
t->_prev->_next = pHead;
pHead->_prev = t->_prev;
free(t);
}
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* p = pHead->_next;//指向第一个节点
while (p != pHead)
{
if (x == p->_data)
return p;
p = p->_next;
}
return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = AollocListNode(x);
newnode->_next = pos;
newnode->_prev = pos->_prev;
pos->_prev->_next = newnode;
pos->_prev = newnode;
}
void ListErase(ListNode* pos, ListNode* pHead)
{
assert(pos);
assert(pos->_prev != pHead);//判断pos前一个节点不为头节点
ListNode* t = pos->_prev;//记录pos前一个节点
t->_prev->_next = pos;
pos->_prev = t->_prev;
free(t);
}
test.c
#include"HDLoopList.h"
int main()
{
ListNode* phead = NULL;
phead = AollocListNode(0);
for (int i = 1; i
[1]: https://xuan.ddwoo.top/index.php/archives/372/
[2]: https://xuan.ddwoo.top/index.php/archives/368/
本文共 1179 个字数,平均阅读时长 ≈ 3分钟