欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 创投人物 > 双向链表

双向链表

2024/11/30 11:49:07 来源:https://blog.csdn.net/2402_84433929/article/details/144050408  浏览:    关键词:双向链表

目录

链表的分类

概念

双向链表的实现

① 结构

② 初始化

③ 打印

④ 插入数据

⑤ 删除数据

⑥ 查找数据

⑦ 在pos位置之前插入数据

⑧ 删除pos位置的数据

⑨ 销毁链表

总结


链表的分类

虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构:单链表和双向带头循环链表

(1)无头单向非循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构,如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

(2)带头双向循环链表:结构最复杂,⼀般⽤在单独存储数据。实际中使⽤的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使⽤代码实现以后会发现结构会带来很多优势,实现反⽽简单了,后⾯我们代码实现了就知道了。

前面我们讲了单链表,而今天我要介绍的是双向带头循环链表,其余的结构大家可以通过我介绍的这两个结构去实现剩余的结构。

概念

带头链表⾥的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这⾥“放哨的”

双向链表的实现

结构

typedef int LTDatatype;
typedef struct ListNode {LTDatatype data;struct ListNode* prev;struct ListNode* next;
}ListNode;

初始化

因为双向链表是带有头结点的,所以我们初始化时直接创建一个新结点给双向链表,另外赋不赋值都可以,个人建议最好赋个-1给它吧,-1就代表这是一个无效数据。

//创建一个新结点
ListNode* LTBuyNode(LTDatatype x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}// 创建并返回链表的头结点
ListNode* ListInit()
{ListNode* newnode = LTBuyNode(-1);return newnode;
}

打印

我们后面会实现很多功能,可以通过打印链表的方式验证我们的代码是否正确

//双向链表打印
void ListPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

插入数据

//尾插
void ListPushBack(ListNode* phead, LTDatatype x)
{ListNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void ListPushFront(ListNode* phead, LTDatatype x)
{assert(phead);ListNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}

删除数据

我们删除数据前要先进行判断,此时我们不可以直接判断该链表是否为空了,因为双向链表为空时,里面是还有一个结点的,那就是前面提到的“哨兵位”,所以当双向链表只有“哨兵位”这个结点时,该双向链表就为空。这和我们前面讲的单链表不一样,大家要注意一下!

//删除判断
bool LTEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;
}

判断完后才进行删除数据操作

//尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(!LTEmpty(phead));ListNode* del = phead->prev;ListNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}//头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(!LTEmpty(phead));ListNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

查找数据

//双向链表查找
ListNode* ListFind(ListNode* phead, LTDatatype x)
{ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

在pos位置之前插入数据

// 双向链表在pos的前面进行插入
void ListInset(ListNode* pos, LTDatatype x)
{assert(pos);ListNode* newnode = LTBuyNode(x);newnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}

删除pos位置的数据

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

销毁链表

//双向链表销毁
void ListDestory(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* Next = pcur->next;ListErase(pcur);pcur = Next;}free(phead);phead = NULL;
}

双向链表的功能实现到这里就结束啦,大家如果想实现其他功能可以去尝试一下。

总结

最后和大家分析一下顺序表和链表的区别

不同点顺序表0链表(单链表)
存储空间上物理上一定连续逻辑上连续,但物理不一定连续
随机访问支持O(1)不支持O(N)
任意位置插入或删除元素可能需要搬移元素,效率低O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容和空间浪费没有容量的概念,按需申请释放,不存在空间浪费
应用场景元素高效存储+频繁访问任意位置高效插入和删除

本章的内容就到此结束啦!下篇文章见,希望大家多多来支持一下!

感谢大家三连支持!

敬请期待下篇文章!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com