单链表
单链表中的每个结点不仅包含值，还包含链接到下一个结点的 引用字段。通过这种方式，单链表将所有结点按顺序组织起来。
蓝色箭头显示单个链接列表中的结点是如何组合在一起的。
结构定义
以下是单链表中结点的典型定义：
function ListNode(val) {this.val = val;this.next = null;}
在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
基本操作
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的 next 字段到达第 2 个结点（结点 6）; 然后使用结点 6 的 next 字段，我们能够访问第 3 个结点。
你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中，我们将介绍插入和删除操作，你将了解到链表的好处。
之后，我们将为你提供练习设计自己的单链表。
添加操作
如果我们想在给定的结点 prev 之后添加新值，我们应该：
- 使用给定值初始化新结点
cur
- 将
cur的next字段链接到prev的下一个结点next
- 将
prev中的next字段链接到cur
与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。
示例
让我们在第二个结点 6 之后插入一个新的值 9。
我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15。最后，将结点 6 链接到结点 9。
插入之后，我们的链表将如下所示：
在开头添加结点
众所周知，我们使用头结点来代表整个列表。
因此，在列表开头添加新节点时更新头结点 head 至关重要。
- 初始化一个新结点
cur； - 将新结点链接到我们的原始头结点
head。 - 将
cur指定为head。
例如，让我们在列表的开头添加一个新结点 9。
- 我们初始化一个新结点 9 并将其链接到当前头结点 23。
- 指定结点 9 为新的头结点。
如何在列表的末尾添加新的结点？我们还能使用类似的策略吗？
删除操作
如果我们想从单链表中删除现有结点 cur，可以分两步完成：
- 找到
cur的上一个结点prev及其下一个结点next；
- 接下来链接
prev到cur的下一个节点next。
在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。
示例
让我们尝试把结点 6 从上面的单链表中删除。
从头遍历链表，直到我们找到前一个结点
prev，即结点 23将
prev（结点 23）与 next（结点 15）链接
结点 6 现在不在我们的单链表中。
删除第一个结点
如果我们想删除第一个结点，策略会有所不同。
正如之前所提到的，我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。
如果想要删除第一个结点，我们可以简单地 将下一个结点分配给 head。也就是说，删除之后我们的头将会是结点 6。
链表从头结点开始，因此结点 23 不再在我们的链表中。