雍巧玲

（喀什大学计算机科学与技术学院,新疆 喀什 844000）

1 引言

随着社会的发展和科技的进步，计算机已被广泛应用。由于计算机计算速度快，存储容量大，使用方便，用途广，给科技发展助力不少，不少高校设置了计算机相关专业及相关课程。其中，“数据结构”是计算机专业课程中的一门核心基础课程，课程内容包含了数据的各种存储结构和组织数据的方式。在数据结构中，双向链表是一种典型的数据存储结构，也是教学当中的重点案例。目前，在出版的一些数据结构相关教材中，对于双向链表中节点插入的讲解示例中，大多数只展示了指针方向变化的一种顺序[1-4]。在双向链表中，每一个节点都带有两个指针域和一个数据域[5]。在链表中，每插入一个节点，会有四个指针的指向发生变化，按照一定的操作顺序，就能完成节点的插入工作。

2 双向链表节点插入算法描述

2.1 基于双向链表节点的类型定义

在双向链表中，一个节点包括一个数据域、一个前驱和一个后继，分别用data、prior和next表示。基于双向链表的节点类型C语言模板如下[1]：

2.2 基于双向链表的节点前插入算法

在双向链表插入节点算法中，在第i个节点前（后）插入一个值为e的新节点s，第i个节点位置的定位可以在链表中从左向右方向查找到，也可以从右向左方向查找到。算法中，p为查找到的第i个节点，将待插入节点s插入到p节点之前，同时要修改s与p节点的前驱和后继域的位置。

在链表中插入一个节点需要对各指针域做出修改，在单向链表中插入一个节点只需要对p和s两个节点的后继域的指向分别做出更改，而在双向链表中，需要对p和s两个节点的前驱和后继共四个指针的指向分别做出更改。……