✨Blog:🥰不会敲代码的小张:)🥰
🉑推荐专栏:C语言🤪、Cpp😶🌫️、数据结构初阶💀
💽座右铭:“記住,每一天都是一個新的開始😁😁😁”
前言
上一章节:无头单向非循环链表
具体链表介绍内容请见上一章节
本章节主要介绍双向链表以及带头节点和循环的概念和实现,并且本章是在上一章节的基础上加以改造,虽然结构复杂了点,但是要比单链表更好实现🤪
双链表介绍
从上面的图中我们可以看到,每一个节点都会有一个指针指向前一个和后一个,然后头节点指向最后一个节点,最后一个节点指向头节点,这就是带头双向循环链表。
那为什么会有单链表和双链表之分呢?
在单链表删除或者查询一个元素时,我们只能单向读取,然后如果删除的话,我们要保存前一个节点,为克服单链表的单向性,可以使用双链表更好的解决此问题。
头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)
链表的创建
prev指针指向前一个,next指针指向后一个
typedef int LDataType;
typedef struct ListNode
{
LDataType data;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
创建新节点
//创建新的节点
ListNode* BuyListNode(LDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyListNode");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
初始化头节点
最开始的头节点前后指针都指向自己,如果有元素插入进来再更改指针指向的位置
//初始化头节点
ListNode* LsitInit()
{
ListNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
销毁链表结点
把头节点的后一个的节点给cur指针,也就是第一个节点的位置
cur指针指向头节点的时候,以及遍历完了链表,所以循环不再进去
然后保留cur的下一个节点,free掉cur,再把next给cur,继续向后走
//销毁节点
void ListDestroy(ListNode* phead)
{
assert(phead);//断言phead不能为空
ListNode* cur = phead->next;//头节点的下一个才是第一个元素
while (cur != phead)//cur的next不能等于头节点
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
打印链表
//打印节点数据
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
printf("head<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
判断链表是否为空
如果头节点的next指针指向自己,说明链表为空
bool ListEmpty(ListNode* phead)
{
assert(phead);
return phead->next == phead;
}
尾插
只需要更改指针关系,找到最后一个节点的位置,在尾部链接要插入的节点,把新插入的节点前指针和后指针链接到对应的位置即可
//尾插
void ListPushback(ListNode* phead, LDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
尾删
找到最后一个节点tail,保留tail的前一个tailprev
把tailprev的next指向头节点,头节点的prev指向tailprev
//尾删
void ListPopback(ListNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* tail = phead->prev;
ListNode* tailprev = tail->prev;
tailprev->next = phead;
phead->prev = tailprev;
free(tail);
tail = NULL;
}
头插
更改指针关系的时候一定要注意先后顺序,不然一旦指针更改可能就会链接到错误的地方
void ListPushFront(ListNode* phead, LDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
//ListInsert(phead->next, x);
}
头删
注意:只要是删除链表节点,就要判断链表是否为空,如果为空就直接报错
tail指针指向第一个节点,让头节点指针指向tail的next
tail的next的prev指向头节点
最后free掉tail指向的节点
//头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* tail = phead->next;
phead->next = tail->next;
tail->next->prev = phead;
free(tail);
tail = NULL;
//ListErase(phead->next);
}
在pos的前一个位置插入
注:pos要配合着查找函数一起使用,比如查找6,找到之后返回6的地址给指针。
记录pos前一个的节点,然后再更改指针之间的关系
//在pos的前一个位置插入
void ListInsert(ListNode* pos, LDataType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);
ListNode* prev = pos->prev;
pos->prev = newnode;
newnode->next = pos;
prev->next = newnode;
newnode->prev = prev;
}
删除pos位置节点
//删除pos位置节点
void ListErase(ListNode* pos)
{
assert(pos);
assert(!ListEmpty(pos));
ListNode* prev = pos->prev;
prev->next = pos->next;
pos->next->prev = prev;
free(pos);
pos = NULL;
}
查找
定义一个cur指针指向第一个节点,如果cur的data和要查找的值一样就返回cur,如果不想等就让cur向后走,直到cur走到头节点循环结束。文章来源:https://www.toymoban.com/news/detail-460770.html
//查找
ListNode* ListFind(ListNode* phead, LDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data != x)
cur = cur->next;
else
return cur;
}
return NULL;
}
创作不易,记得三连!笔者水平有限,如有错误的地方,还望指出,谢谢大家😋😋😋文章来源地址https://www.toymoban.com/news/detail-460770.html
到了这里,关于数据结构【链表】看完还怕拿不下链表?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!