双向链表的插入删除操作_双向链表的删除操作

作者：我家小花儿 | 2024-04-20 09:06:06

踩

双向链表的删除操作

特点：

在单链表的每个节点里再增加一个指向其前驱的指针域(prior)

如果是非空表那么头节点prior为空，尾节点next为空

如果是空表那么prior和next都为空

双向链表结构具有对称性，即p->prior->next=p=p->next->prior

插入删除操作需要同时修改两个方向上的指针，时间复杂度为O(n)

定义：

代码如下：

操作：

插入：

思路：

假设需要插入的节点为x，前驱为a，后继为b

先使x的prior指向a，然后让a的next指针指向x

使x的next指向b，然后让b的prior指针指向x

代码如下：

删除：

思路：

设前驱为x，要删除的节点为y，后继为z

y->prior->next=p->next;（x的后继指针指向z）

y->next->prior=p->prior;（z的前继指针指向x）

代码如下：

双向循环链表：

特点：

非空表：

让头节点的前驱指针指向链表的尾节点

让尾节点的后续指针指向头节点

空表：

头指针和尾指针都指向自身

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/456512