数据结构基础之双链表

矫情吗；* 2022-08-04 14:42 189阅读 0赞

**双链表**

**双向链表（Double Linked List）**

双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

![0_131217960063P7.gif][]

![0_1312180517MuzH.gif][]

非空双向链表

①双链表由头指针head惟一确定的。  
　②带头结点的双链表的某些运算变得方便。  
　③将头结点和尾结点链接起来，为双（向）循环链表。

**双向链表的结点结构和形式描述**

形式描述  
typedef struct dlistnode\{  
DataType data;  
struct dlistnode \*prior,\*next;  
\}DListNode;  
typedef DListNode \*DLinkList;  
DLinkList head;

**双向链表的前插和删除本结点操作**

由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。

双链表的前插操作：

void DInsertBefore(DListNode \*p,DataType x)  
\{//在带头结点的双链表中，将值为x的新结点插入\*p之前，设p≠NULL  
DListNode \*s=malloc(sizeof(DListNode));//①  
s->data=x;//②  
s->prior=p->prior;//③  
s->next=p;//④  
p->prior->next=s;//⑤  
p->prior=s;//⑥  
\}

**双链表上删除结点\*p自身的操作：**

void DDeleteNode(DListNode \*p)  
\{//在带头结点的双链表中，删除结点\*p，设\*p为非终端结点  
p->prior->next=p->next;//①  
p->next->prior=p->prior;//②  
free(p);//③  
\}

> 注：与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。  
>

上述两个算法的时间复杂度均为O(1)。

[0_131217960063P7.gif]: /images/20220731/cdafa614504242c9963ddcb2ef3c255d.png
[0_1312180517MuzH.gif]: /images/20220731/918aa215885944cf90e5ac86cea49441.png

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构之模拟双链表

package com.qiangqiang; / \ Created with IntelliJ IDEA. \ @auth

超、凢脫俗/ 2023年01月01日 01:55/ 0 赞/ 140 阅读

相关（四）Java数据结构之双链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1

我不是女神ヾ/ 2022年12月13日 01:39/ 0 赞/ 151 阅读

相关数据结构双链表（5）

双向链表 1、单链表&双链表区别单向链表，在查找的方向只能是一个方向，而双向链表可以向前或者向后查找单向链表不能自我删除，需要靠辅助节点。而双向链表

朱雀/ 2022年11月24日 14:18/ 0 赞/ 180 阅读

相关 java数据结构之循环双链表

感谢[tu451953337][]的分享原文链接地址：[点击打开链接][Link 1] 这个循环双链表写的相当不错，注释解析也很清晰。是个不错的博文！ 1. publi

我就是我/ 2022年08月22日 15:15/ 0 赞/ 198 阅读

相关数据结构基础之双链表

双链表双向链表（Double Linked List）双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域p

矫情吗；*/ 2022年08月04日 14:42/ 0 赞/ 190 阅读

相关数据结构——双链表

双链表增加一个指向前驱结点的指针，使得链表可以向前，向后查找。但是操作略微复杂点。数据结构 //双链表 typedef struct DLinkLis

浅浅的花香味﹌/ 2022年08月03日 03:15/ 0 赞/ 168 阅读

相关数据结构之双端链表

双端链表指的是双向链表中头结点始终保持着对尾结点的引用。准备数据：一、结点类： / 链表节点，相当于火车的车厢 @author Administrat

﹏ヽ暗。殇╰゛Y/ 2022年06月18日 11:26/ 0 赞/ 197 阅读

相关数据结构-4-双链表

数据结构-4-双链表在单链表的实现中，我们可以清晰感觉到，要访问链表的尾时必须要遍历链表，这样效率就打了折扣

喜欢ヅ旅行/ 2022年05月27日 02:35/ 0 赞/ 196 阅读

相关数据结构之双链表

1.0 可以说算是背景吧因为你用循环链表的话你想找到指针值执向的后继节点很容易，那你要是想找指针所指结点的前一个，那实在是太操蛋了，你还得在找一圈，就想好你在操场上跑步

朴灿烈づ我的快乐病毒、/ 2022年05月24日 22:08/ 0 赞/ 208 阅读

相关 Java数据结构之链表-双端链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)

朴灿烈づ我的快乐病毒、/ 2022年02月13日 14:49/ 0 赞/ 307 阅读