刷过力扣的读者肯定对单链表非常熟悉，力扣上的单链表节点定义如下：
这仅仅是一个最简单的单链表节点，方便力扣出算法题来考你。在实际的编程语言中，我们使用的链表节点会稍微复杂一点，类似这样：
主要区别有两个：
1、编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。
2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。
有了 prev 前驱指针，链表支持双向遍历，但由于要多维护一个指针，增删查改时会稍微复杂一些，后面带大家实现双链表时会具体介绍。
为什么需要链表
前面介绍了 数组（顺序存储）的底层原理，说白了就是一块连续的内存空间，有了这块内存空间的首地址，就能直接通过索引计算出任意位置的元素地址。
链表不一样，一条链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 next, prev 指针，将零散的内存块串联起来形成一个链式结构。
这样做的好处很明显，首先就是可以提高内存的利用效率，链表的节点不需要挨在一起，给点内存 new 出来一个节点就能用，操作系统会觉得这娃好养活。
另外一个好处，它的节点要用的时候就能接上，不用的时候拆掉就行了，从来不需要考虑扩缩容和数据搬移的问题，理论上讲，链表是没有容量限制的（除非把所有内存都占满，这不太可能）。
当然，不可能只有好处没有局限性。数组最大的优势是支持通过索引快速访问元素，而链表就不支持。
这个不难理解吧，因为元素并不是紧挨着的，所以如果你想要访问第 3 个链表元素，你就只能从头结点开始往顺着 next 指针往后找，直到找到第 3 个节点才行。
上面是对链表这种数据结构的基本介绍，接下来我们就结合代码实现单/双链表的几个基本操作。
单链表的基本操作
如果觉得抽象，以下网站可以帮助完成：https://visualgo.net/zh/list
我先写一个工具函数，用于创建一条单链表，方便后面的讲解：
查/改
单链表的遍历/查找/修改
比方说，我想访问单链表的每一个节点，并打印其值，可以这样写：
类似的，如果是要通过索引访问或修改链表中的某个节点，也只能用 for 循环从头结点开始往后找，直到找到索引对应的节点，然后进行访问或修改。
增
在单链表头部插入新元素
直接看代码吧，很简单：
Java
运行代码
复制代码
1
2
3
4
5
6
7
8
// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
// 在单链表头部插入一个新节点 0
ListNode newHead = new ListNode(0);
newHead.next = head;
head = newHead;
// 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
在单链表尾部插入新元素
这个操作稍微复杂一点，因为我们要先从头结点开始遍历到链表的最后一个节点，然后才能在最后一个节点后面再插入新节点：
Java
运行代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
// 在单链表尾部插入一个新节点 6
ListNode p = head;
// 先走到链表的最后一个节点
while (p.next != null) {
p = p.next;
}
// 现在 p 就是链表的最后一个节点
// 在 p 后面插入新节点
p.next = new ListNode(6);
// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6
当然，如果我们持有对链表尾节点的引用，那么在尾部插入新节点的操作就会变得非常简单，不用每次从头去遍历了。这个优化会在后面具体实现双链表时介绍
在单链表中间插入新元素
这个操作稍微有点复杂，我们还是要先找到要插入位置的前驱节点，然后操作前驱节点把新节点插入进去：
Java
运行代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
// 在第 3 个节点后面插入一个新节点 66
// 先要找到前驱节点，即第 3 个节点
ListNode p = head;
for (int i = 0; i < 2; i++) {
p = p.next;
}
// 此时 p 指向第 3 个节点
// 组装新节点的后驱指针
ListNode newNode = new ListNode(66);
newNode.next = p.next;
// 插入新节点
p.next = newNode;
// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5
