05 双链表：搜索链表中节点的速度还可以更快吗？
你好，我是王健伟。
上节课，我们学习了单链表的相关操作，我们会用它来对数据进行顺序存储，如果需要频繁增加和删除数据，同样也可以用到单链表。而它也可以衍生出好多种链表结构，双链表（也称双向链表）就是其中一种。
在单链表中，有一个指针域用于指向后继节点。这带来的问题是，如果要寻找单链表中某个已知节点的前趋节点，就会比较繁琐了，我们必须从链表头出发开始寻找，算法的平均情况时间复杂度为O(n)。
那要怎么解决这个问题呢？
在单链表的基础上，我们可以增加一个用于指向前趋节点的指针，也称为前趋指针，当然，第一个节点的前趋指针指向nullptr，如果是带头节点的链表，那么就是头节点的前趋指针指向nullptr。这样，当查找某个节点的前趋节点就会非常容易，查找算法的时间复杂度也会从O(n)变为O(1)。
这种增加了前趋指针的链表，被称为双链表。如果画得形象一点，双链表（带头节点）数据存储的描述图应该如图9所示：
双链表的很多操作和单链表相同，比如元素获取、求长度、判断是否为空、链表释放等操作，因为这些操作并不需要用到前趋指针。而有一些常用操作双链表与单链表不同，下面，我还是使用带头结点的代码实现方式，来实现双向链表。
双链表的类定义、初始化操作
我们还是先说双链表的类定义以及初始化操作。
//双链表中每个节点的定义
template <typename T> //T代表数据元素的类型
struct DblNode
{
T data; //数据域，存放数据元素
DblNode<T>* prior; //前趋指针，指向前一个同类型（和本节点类型相同）节点
DblNode<T>* next; //后继指针，指向下一个同类型（和本节点类型相同）节点
};
接着定义双链表、书写双链表构造函数的代码。
//双链表的定义
template <typename T>
class DblLinkList
{
public:
DblLinkList(); //构造函数
~DblLinkList(); //析构函数
public:
bool ListInsert(int i, const T& e); //在第i个位置插入指定元素e
bool ListDelete(int i); //删除第i个位置的元素
bool GetElem(int i, T& e); //获得第i个位置的元素值
int LocateElem(const T& e); //按元素值查找其在双链表中第一次出现的位置
void DispList(); //输出双链表中的所有元素
int ListLength(); //获取双链表的长度
bool Empty(); //判断双链表是否为空
private:
DblNode<T>* m_head; //头指针（指向链表第一个节点的指针，如果链表有头结点则指向头结点）
int m_length; //双链表当前长度（当前有几个元素），为编写程序更加方便和提高程序运行效率而引入，但不是必须引入
};
//通过构造函数对双链表进行初始化
template <typename T>
DblLinkList<T>::DblLinkList()
{
m_head = new DblNode<T>; //先创建一个头结点
m_head->next = nullptr; //该值暂时为nullptr，因为还没有后继节点
m_head->prior = nullptr; //该值一直为nullptr
m_length = 0; //头结点不计入双链表的长度
}
之后，在main主函数中加入代码创建一个双链表对象就可以了，如果你此时编译代码，可能会遇到错误提示，只需要参考课件把提示缺少的代码补足即可。
双链表元素插入操作
双链表的元素插入操作实现代码与单链表大部分相同。值得注意的是，因为引入了前趋指针，所以必须正确设置原有节点与新插入节点的前趋指针指向。
设想一下，如果想要在a1和a2节点之间插入一个新节点e，那么这个节点e的指向示意图应该是什么样的呢？
如图10所示：
再说实现代码。和单链表的同名实现代码ListInsert相比，我们需要新增几行代码来对新插入的节点e和a2节点的前趋指针赋值。
下面的代码中，几行标有数字的代码行所实现的功能与图10中所标记的数字一致，完整的实现代码，可以参考课件。为了防止代码执行出现错误，代码的执行顺序也要严格遵照下面的示例。
DblNode<T>* node = new DblNode<T>;
node->data = e;
①node->next = p_curr->next;//让新节点链上后续链表，因为pcurr->next指向后续的链表节点
②node->prior = p_curr;
if(p_curr->next != nullptr)
③ p_curr->next->prior = node;
④p_curr->next = node;//让当前位置链上新节点，因为node指向新节点
在我们上节课讲解的单链表中，如果我们要向某个已知节点之前插入新节点，那么需要利用头指针m_head从前向后找到该已知节点的前趋节点。不过，有了双链表之后，就可以直接利用该已知节点的前趋指针实现这个功能了。
你可以自行实现这个操作相关的算法代码，下面是算法命名和相关参数。
template<class T>
bool DblLinkList <T>::InsertPriorNode(DblNode<T>* pcurr, DblNode<T>* pnewnode)
{
//在节点pcurr之前插入新节点pnewnode，请自行添加相关代码......
}
在main主函数中，我们继续增加代码测试元素插入操作（如果编译代码遇到错误提示，只需要参考课件把提示缺少的代码补足即可）。
sdbllinkobj.ListInsert(1, 12);
sdbllinkobj.ListInsert(1, 24);
sdbllinkobj.ListInsert(3, 48);
sdbllinkobj.ListInsert(2, 100);
sdbllinkobj.DispList();
新增代码的执行结果如下：
双链表元素删除操作
那如果是要删除双链表的第i个位置的元素呢？操作同样和单链表的相应操作类似，只是要注意前趋指针的设置。
设想一下，如果想把刚刚插入在a1和a2节点之间节点e删除，示意图应该怎么画呢？
你会发现，我们需要做的，就是让a1节点的next指针指向a2节点，让a2节点的prior指针指向a1节点。
理解了删除操作的思路，我们再说代码。与单链表的同名实现代码ListDelete相比，我们需要新增一行代码来对被删除节点后继节点（a2）的前趋指针赋值。
完整的实现代码可以参考课件，先看下核心代码。
DblNode<T>* p_willdel = p_curr->next; //p_willdel指向待删除的节点
DblNode<T>* p_willdelNext = p_willdel->next; //p_willdelNext指向待删除节点的下一个节点
①p_curr->next = p_willdel->next; //第i-1个节点的next指针指向第i+1个节点
if (p_willdelNext != nullptr)
② p_willdelNext->prior = p_curr; //第i+1个节点的prior指针指向第i-1个节点
在main主函数中，我们继续增加代码测试元素删除操作。
新增代码的执行结果如下：
在单链表中，如果删除某个已知节点，那么需要利用头指针m_head从前向后找到该将被删除节点的前趋节点。有了双链表之后，我们直接就可以利用该已知节点的前趋指针实现这个功能，你可以自行实现这个操作相关的算法代码。我把算法命名和相关参数也放在了这里。
template<class T>
bool DblLinkList<T>::DeleteNode(DblNode<T>* pdel)
{
//删除pdel所指向的节点，请自行添加相关代码......
}
双链表的翻转操作就不单独给出代码了，相信你参考单链表的翻转操作，再对比一下单链表和双链表的不同，就完全能够独立完成。这里提醒你一下，每个节点的前趋指针，是不是正确设置了呢？
双链表的特点
这节课的操作讲解并没有上节课多，但你一定发现了，它们都是在单链表的基础上进行了变化和改动。所以这里，我们来对照着单链表，总结一下双链表的特点，帮助你更好地理解今天的内容。
在单链表中，因为指向后继节点指针的存在，所以如果给定一个已知的节点，寻找其后继节点的时间复杂度为O(1)，但如果寻找前趋节点，则因为每次都要从链表头出发开始寻找，所以算法的最坏情况时间复杂度为O(n)。
而双向链表因为前趋指针的存在，寻找一个已知节点的前趋节点的时间复杂度变为了O(1)，大大提高了寻找效率。
双链表中的某节点p前趋节点的后继指针以及后继节点的前趋指针，代表的都是p节点本身。也就是：
p->prior->next = p->next->prior = p
需要注意的是，存放前趋指针要额外消耗存储空间。
另外，我们想一想，如果在单链表或者双链表中引入一个last指针，让它始终指向链表的尾节点，因为有了这个last指针的存在，在链表的尾部插入数据，是不是就会非常简单呢？不过我们要注意，在插入和删除节点时要维护这个last指针的有效指向，此外，对于带头节点的链表，因为刚开始链表中并没有实际的数据节点，所以last指针也和head指针一样，都指向头节点。
不但如此，对于双链表，当按位置查找某个节点时，若位置不超过链表长度（m_length）的一半，还可以利用head指针从左到右查找，而如果位置超过了链表的一半，就可以利用last指针辅助prior指针从右到左查找。
小结
这节课，我们讲解了双链表的相关内容，包括带头节点双链表的类定义及初始化操作、元素插入操作、元素删除操作等。同时还给出了双链表的特点总结。
这一系列的讲解，都是为了让我们更了解双链表的工作原理。除非有特殊需要，一般不需要自己实现单链表和双链表，因为标准模板库中已经提供了。
另外，标准模板库中的list容器的内部实现就是一个双链表。通过本节的讲解，你一定也会对list容器的工作原理以及优缺点有了非常清晰的认识了。想一想，如果让你自己来实现本节中所讲述的各种代码，你做得到吗？
归纳思考
- 想一想单链表与双链表的区别在哪里？
- 你能参考单链表的翻转操作代码，写出双链表的翻转操作代码吗？
- C++标准模板库中的vector容器和list容器的区别有哪些（这可是面试中常被问到的问题）？list容器和forward_list容器的区别又是什么？你可以尝试总结一下。
欢迎你在留言区和我互动。如果觉得有所收获，也欢迎你把课程分享给更多的朋友一起学习进步。我们下节课见！
- 雪无痕 👍（0） 💬（1）
p->prior->next = p->net->prior = p，这里p->net应为p->next
2023-06-15 - Yj.yolo 👍（0） 💬（1）
vector容器和list容器有以下区别： （1）vector内存连续，list内存不连续 （2）vector会预分配内存，capacity为vector实际内存大小，list内存分配为实际数据大小 （3）vector内存达到capacity容量时将vector数组全部拷贝到新的capacity大小的内存区域，会比list多进行内存拷贝 （4）vector实现对应数组，因此可以直接下标访问vector[i]，而list容器内存不连续因此无法下标访问；因此数据涉及大量的随机访问（读操作）则最好使用vector （5）vector插入删除中间元素时数组会整体移动，而list插入删除直接修改链表指针；因此高效插入删除时还是list好些
2023-06-05 - Geek_7ba740 👍（0） 💬（1）
可以理解为读多写少用vector，写多读少用list，不确定的话用vector吗
2023-04-08 - Fang 👍（0） 💬（0）
p->prior->next = p->next->prior = p
2024-07-29 - 铁甲依然在 👍（0） 💬（0）
我写了双链表的反转代码 //双链表的链表反转 template<typename T> void DbLinkList<T>::ReverseList() { if (m_length < 1) { return; } DblNode<T>* pothersjd = m_head->next->next; //指向从第二个节点的后续节点 m_head->next->next = nullptr; //第一个节点的后续指点指针值为空 DblNode<T>* ptemp; while (pothersjd != nullptr) { ptemp = pothersjd; //临时节点 pothersjd = pothersjd->next; //第二节点后移动 ptemp->prior = m_head; //后一段节点的前驱节点值为头节点 ptemp->next = m_head->next; //后一段节点的后驱节点为头节点的后驱节点 m_head->next->prior = ptemp; //头节点前的前一段节点的前驱节点为新插入的节点 m_head->next = ptemp; //头节点的后驱节点为新插入的节点 } }
2023-10-10