2.2.2双向链表 课件-2021-2022学年浙教版（2019）高中信息技术选修1

2.2 链表 双向链表 什么是双向链表？ 双向链表（又称双链表）每个节点有两个指针prev和next， 分别指向其前驱节点和后继节点，这样可以提供方便的双向 查找功能。 双向链表的表示？ Dui=[[“吴坚”，-1，1],[“王林”,0，2], [“黄刚”,1，3],[“李丰”,2，-1]] 节点 （由数据区域和前驱节点指针、后继节点指针构成） 我前面没人 我后面没人 我后面是黄刚 双向链表的特性 双向链表中当节点中prev指向为-1（即指向为空）时，表示该节点为链表 中的首个节点；相对的，当节点中next指向为-1时，表示该节点为链表中 的最后一个节点。 下图所示为用二维列表表示一个长度为6的双向链表 data 1 ^ data 2 data 3 data 4 data 5 data 6 列表名data 列表索引 数据域 prev指针 next指针 0 data6 4 -1 1 data4 5 4 2 data1 -1 3 3 data2 2 5 4 data5 1 0 5 data3 3 1 head 双向链表的基本操作 一、双向链表的创建 Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来 表示每一个节点，其中第一个元素存储数据，第二、三个元素分别存储 前驱指针prev和后继指针next。 创建一个拥有2个节点的双向链表dblinklist的代码如下： dblinklist=[[6,-1,1],[8,0,-1],] head=0 创建一个空链表dblinklist的代码如下： dblinklist=[] head=-1 二、双向链表节点的访问 链表节点只能通过头指针（head）进行访问，其他节点通过节点间的next指针 依次访问。 可以设计如下自定义函数输出链表的所有节点： def shuchu(a,head): p=head while a[p][2]!=-1 print(a[p][0],end=“---->”) p=a[p][2] print(a[p][0]) 三、双向链表节点的插入 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与 其前驱与后继节点的指针，将新节点插入到链表的正确位置。 从链表头部插入一个新节点（头插法）：例如，在双向链表a的头部