双向链表的结点插入

引入：

在单链表中，查找其直接后继的时间复杂度为O（1），而查找其直接前驱的时间复杂度为O（n）。

好比如下单链表：

若查找2的直接后继，记指针p指向值为2的节点（p->data=2），则2的直接后继是p->next；但若查找2的直接前驱时，无法通过p直接获取（单链表无前驱指针），需从头指针head开始遍历，直到找到节点q满足q->next == p（q即为p的前驱），遍历最坏需走n步，因此时间复杂度为O(n)；故面对这种情况，为降低时间复杂度，我们引入双向链表。

双向链表简介：

第一个格子为prev（指向前一个结点），第二个格子为data（存放数据），第三个格子为next（指向后一个结点）；

与单向链表不同的是，双向链表多了一个可以指向前一个结点的指针（即prev），假设图中头结点head后一个结点为q，则有q->prev = head；head->next = q；这样，链表就能通过next和prev两个指针向前或向后遍历，不再是单方向的流动。

双向链表的核心优势：

• 查找直接前驱 / 后继的时间复杂度均为 O (1)（通过prev/next指针直接获取），解决了单链表查找前驱 O (n) 的问题；
• 插入 / 删除操作时，无需像单链表那样从头遍历找前驱节点，仅需通过prev指针直接定位，操作效率提升；
• 注意：双向链表的代价是每个节点多占用一个指针的内存空间（空间换时间）。

在双向链表中，头插法的使用：

流程图：

在已知双向链表的基础上使用头插法，按如上图的步骤更改箭头的指向

核心代码及理解：

在双向链表中，尾插法的使用：

流程图：

第一步：将存放新数据的结点记为p，p->prev =tail（尾结点）；

第二步：tail->next = p；将原来的尾结点的next指向新的尾结点new；

第三步：第三步：p->next = NULL（新节点作为新尾节点，后继指向NULL）；

若为「双向循环链表」，第三步需改为p->next = L（头结点），同时L->prev = p（头结点的前驱指向新尾节点），维持循环结构。

核心代码及理解：

在双向链表中，指定位置插入节点的使用：

第一步：在双向链表中，指定位置插入（pos从1开始计数），优先找“前驱节点”（更符合操作习惯），遍历的终止条件是“找到第pos-1个节点”，且必须判断遍历过程中指针是否为空（避免pos超出链表长度）（下面的代码图展示的是前驱结点）

第二步：将数据e存放在新的结点q中

第三步：改变prev和next的指向，让数据e被插入链表中

流程图：

核心代码：

通过遍历找到指定位置的前一个结点：

更改指针的指向，让新结点插入链表中来：

• p8和p9的代码图源于b站逊哥