数据结构和算法(4)

链表、双向队列

链表

链表像数组一样，也用来表示一系列的元素。但是链表的实现和数组不同，在不同的场景他们会有不同的性能表现。
我们知道，数组在计算机内存中是连续的(如果不懂的话请自行AI)，而链表是可以分布在内存的各个地方，这种不连续的内存空间，我们称之为结点(很重要，后面都会涉及到这个概念)。

• 关键：每个结点除了保存着数据，他还保存着链表里下一结点的内存地址。而这份用来指示下一结点的内存地址的额外数据，被称为链。

读取、插入与删除

读取

链表不同于数组，数组在任何情况下的查找效率为O(1)。而链表是由一个个结点组成的，因此在查找某个数据的时候需要一个一个遍历结点，因此在最坏的情况下，链表的查找效率为O(N)，比数组的效率低得多。

插入

在某些情况下，链表的插入跟数组相比有着明显的优势。数组中想在0索引处插入数据，则需要将所有数据右移一格。而链表中像这样做，只需要新建一个结点再链接到下一结点即可。而链表若是想在末尾插入数据，却比数组慢得多：链表需要遍历到最后一个结点再新建结点并链接；而数组只需要直接在末尾插入就好。因此我们会发现，链表和数组的最坏情况和最好情况刚好是反着来的。

删除

我们可以类比以上的过程。链表的想删除表头的数据其实很容易，想要删除末尾的数据却很麻烦，因为他需要查找到最后一个数据。而数组删除第一个数据很麻烦，删除最后一个数据却很简单。

为了方便理解，我这里有一个可让数据结构可视化的网站,大家可以去尝试一下以便更好的理解。

除了在读取方面数组有着明显优势，其他方面大差不差，我们为什么还要用链表呢。存在即合理。

应用场景

1、需要频繁插入/删除（如实现队列、撤销操作）

2、数据规模不确定（如动态内存管理）
例如我们需要整理电子邮箱地址，需要删除列表中无效的电子邮箱。如果使用数组，我们每次删除邮箱地址需要格外花其他步骤来左移之后的数据，而用链表只需要删除数据后改变节点，便可继续检查接下来的数据了。

双向链表

这是链表结构中非常实用的一种变体。

特性

1、每个节点包含两个指针：
next：指向后一个节点（和单向链表相同）
prev：指向前一个节点（新增的指针）

类比：类似于地铁的双向轨道，既可以从A站到B站，也可以从B站返回A站。

优势：

1、双向遍历：可以从头到尾或从尾到头访问数据。
2、删除操作更高效：已知某个节点时，可直接通过prev指针找到前驱节点，无需从头遍历（单向链表删除节点需要O(n)时间找前驱）。

代价：

1、每个节点多一个指针，占用更多内存。
2、插入/删除时需要维护两个指针，代码稍复杂。

应用场景

1、浏览器历史记录：
前进和后退功能需要双向遍历。
2、音乐播放列表：
支持上一曲/下一曲切换。
3、实现双向队列（Deque）：
高效地从头部或尾部插入/删除数据。

说起双向队列，我想更进一步了解,以下由AI生成

双端队列

定义：允许在头部和尾部进行高效插入和删除操作的线性数据结构。
特点：

• 可以从两端插入（push_front/push_back）
• 可以从两端删除（pop_front/pop_back）
• 先进先出（FIFO）或后进先出（LIFO）取决于使用方式

类比：想象一个地铁站的双向闸机，乘客可以从两端进出（如下图所示）：

1

[队尾] ←→ [元素1] ↔ [元素2] ↔ ... ↔ [元素N] ←→ [队头]

为什么用双向链表实现双端队列？

1. 时间复杂度优势：
   • 所有插入/删除操作均为 O(1)（单向链表尾部操作需要O(n)遍历）
2. 操作对称性：
   • 双向链表的prev和next指针天然支持双向操作

与循环数组实现的对比