---

大纲图

---

双向链表

Algorithms_基础数据结构(02)_链表&链表的应用案例之单向链表中梳理了 单向链表的基本操作，接下来我们继续来看下双向链表吧。

---

双向链表的基本结构

单向链表只有一个方向，结点只有一个后继指针next指向后面的结点。

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。

虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？

-----> B+Tree:Mysql索引 叶子节点 双向链表

---

双向链表的基本操作

头插

---

尾插

---

中间部位插入

---

删除头部

---

删除尾部

---

删除中间位置的数据

---

查找

通常，双向链表同单链表一样，都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素。

---

更新

更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是：通过遍历找到存储有该数据元素的结点，直接更改其数据域即可。

---

Code

---

总结

重要区别：

• 1.数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。

• 2.链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。

• 3.数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它， 导致“内存不足（out ofmemory）”。如果声明的数组过小，则可能出现不够用的情况。注意下标越界的问题。

• 4.动态扩容：数组需再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，使用的时候也需要考虑占用内存的问题。