介绍

与数组相似，链表也是一种 线性数据结构。

常见的链表有两种类型：单链表和双链表。

单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。如下图：

链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

节点结构

type Node struct {
    Val int
    Next *Node
}

在大多数情况下，使用头结点(第一个结点)来表示整个列表。

操作

与数组不同，无法在常量时间内访问单链表中的随机元素。如果我们想要获得第 i 个元素，必须从头结点逐个遍历。按索引来访问元素平均要花费时间，其中 N 是链表的长度。

插入节点时间复杂度为。

https://leetcode-cn.com/explore/learn/card/linked-list/193/singly-linked-list/739/

删除节点的时间复杂度将是 。

https://leetcode-cn.com/explore/learn/card/linked-list/193/singly-linked-list/740/

双链表

双链表与单链表相似，但还有一个引用字段，称为 prev 字段。有了这个额外的字段，就能够知道当前结点的前一个结点。

结构如下：

节点结构

type Node struct {
    Val int
    Prev *Node
    Next *Node
}

与单链接列表类似，使用 头结点 来表示整个列表。

操作

访问元素:

不能在常量级的时间内访问随机位置。
必须从头部遍历才能得到我们想要的第一个结点。
在最坏的情况下，时间复杂度将是，其中 N 是链表的长度。

对于添加和删除，会稍微复杂一些，因为还需要处理 prev 字段。

添加操作的时间和空间复杂度都是 。

https://leetcode-cn.com/explore/learn/card/linked-list/196/doubly-linked-list/757/

对于删除操作因为不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是。

https://leetcode-cn.com/explore/learn/card/linked-list/196/doubly-linked-list/758/

时间复杂度比较

这里提供链表和其他数据结构（包括数组，队列和栈）之间时间复杂度的比较：

结论：

如果你需要经常添加或删除结点，链表可能是一个不错的选择。
如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

常见问题解决方案
双指针（快慢指针）

从一个经典问题开始：

给定一个链表，判断链表中是否有环。

使用双指针技巧 有一个更有效的解决方案。

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况：

如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。

所以剩下的问题是：

这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

链表 VS 数组性能大比拼

数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
_
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。

除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。