后端开发教程 - Java、Spring Boot 实战 - msg200.com
谢谢，接下来：链表简介
在这篇文章中，我们将用 Ariana Grande 的歌曲《thank u, next》的语言来探讨链表数据结构。如果你还没看过这首歌的MV，请在开始之前先暂停一下。
链表是由带有数据和指针的节点组成的线性数据集合。我们将重点介绍单链表，它包含存储节点值和指向下一个节点的指针的节点。还有其他类型的链表，例如双向链表和循环链表，但我们现在只讨论单链表。
以下是一些简单的定义，以确保我们达成共识：
- 指针存储内存中某个值的地址。它们也可以指向空值。引用类似，但不能指向空值。
- 数据结构是可以用任何编程语言实现的数据集合。
我们将在本文中使用以下链接列表：
在上图中，我们看到了五个不同的节点，每个节点都有一个数据值。前四个节点按照她列出前任的顺序排列：
我以为我会和肖恩在一起
但他不是我们的对手
我写了一些关于瑞奇的歌
现在我听着听着就笑了
甚至差点结婚了
对于皮特，我非常感激 我
希望我能对马尔科姆说“谢谢”
因为他是个天使
最后一个是Ari本人：
另外，我遇到了其他人
，我们进行了更好的讨论，
我知道他们说我继续前进太快了，
但这一次会持续下去
，因为她的名字叫阿里
，我对此很满意（对此很满意）
除了数据之外，每个节点还存储指向下一个节点的指针。她总是按照相同的顺序唱关于前任的歌，最后唱的是自己。当我们遍历链表时，也会采用相同的顺序。我们将从头节点（链表中的第一个节点）开始，然后移动到下一个节点，依此类推。对于单链表，我们不会反向移动或随机地从一个节点跳转到另一个节点，而是按照相同的顺序从头到尾进行遍历。
我们可以通过以下方式创建节点和链接节点来创建一个超级简单的链表：
class Node {
constructor(data, next=null) {
this.data = data
this.next = next
}
}
let ari = new Node('Ari')
let malcolm = new Node('Malcolm', ari)
let pete = new Node('Pete', malcolm)
let ricky = new Node('Ricky', pete)
let sean = new Node('Sean', ricky)
本文的最终代码也是用 Python 编写的，请点击此处
如果我们打印出 Sean 节点的样子，我们可以看到它存储了他的名字作为数据属性，以及对下一个节点 Ricky 的引用。我们可以使用该next属性遍历所有节点！
另外，链表末尾有一个空指针。在这种情况下，由于 Ari 是女王，她自己就很好，不需要继续寻找下一个伴侣。所以，不用了，她的节点是 next。
与数组相比，链表有一些优势，数组是它们在线性数据结构领域的主要替代品。数组传统上存储在内存的连续块中，这使我们能够使用快速索引公式start_of_array_in_memory + space_allocated_for_each_array_item * index_of_item_we_want。虽然O(1)获取索引处的项目非常高效（），但在数组中插入或删除项目的效率较低 - 我们需要将所有内容移动到内存中的另一个块中。不能保证该数组之前或之后有空间来插入新项目。如果在中间插入或删除，则适用相同的逻辑 - 您必须在内存中移动项目以填补空缺或分配更多空间。
与数组不同，链表不需要存储在内存中一个连续的（或并排的😉）块中，这使得在链表开头插入和删除操作更加容易。指针可以指向内存中的任意位置，因此你无需移动所有数据来添加新节点。
话虽如此，如果你尝试搜索链表、在中间插入或从中间删除，这个过程效率会低得多。我们需要从头部遍历到我们试图访问的节点。
链表的另一个缺点是它们比数组占用更多的内存，因为它们存储数据和指向下一个节点的指针，而数组只存储数据。
让我们看一下实现这些操作的代码。我们将在链表的开头插入，并在索引处实现删除，以展示执行这些操作需要做什么：
class LinkedList {
constructor() {
// the head attribute stores a pointer to the first node in our linked list
this.head = null
this.length = 0
}
insert(data) {
// inserts to the beginning of the linked list
// what used to be the head becomes the second element
this.head = new Node(data, this.head)
this.length++
}
remove_value(value) {
// remove any data value from the linked list
// we need to store a pointer to a node and it's predecessor
// so that when we remove the value we can just change the pointer!
let prevNode = null
let currentNode = this.head
while (currentNode) {
if (currentNode.data === value) {
if (prevNode) {
// Set the previous node's next value to the node we're deleting's next attribute
// effectively removing it from our sequence
prevNode.next = currentNode.next
} else {
this.head = currentNode.next
}
currentNode = null
this.length--
return true
}
// move to the next nodes
prevNode = currentNode
currentNode = currentNode.next
}
}
}
let thankUNext = new LinkedList()
thankUNext.insert('Ari')
thankUNext.insert('Malcolm')
thankUNext.insert('Pete')
thankUNext.insert('Ricky')
thankUNext.insert('Sean')
thankUNext.remove_value('Ricky')
下面是一个可视化的例子，展示了如果 Ari 对 Ricky 不再那么感激的话，将 Ricky 从我们的链表中移除会是什么样子：
红色的所有内容都会被删除。
另外两个有用的方法是search和iterate：
iterate() {
let node = this.head
while (node) {
console.log(node.data)
node = node.next
}
}
search(data) {
let idx = 0
let node = this.head
while (node) {
if (node.data === data) return idx
node = node.next
idx += 1
}
return -1
}
所以，我们知道将 Ariana Grande 的前任存储在链表中是数据结构的绝佳用途，因为当我们跟着唱“thank u, next”时，我们总是按相同的顺序列出它们。但是，还有哪些其他数据适合用链表呢？一种用途是任务队列。例如，打印机一次只能打印一份，但我们仍然希望加载未来的任务，而不必每页都按打印！当我们创建任务列表时，我们总是将最新的项目添加到队列的末尾，然后打印出队列中第一个！后退按钮的实现也类似！或者撤销热键！我们通常会在链表之上实现一个堆栈或队列数据结构来实现这些功能。我还发现它们对很多代码挑战非常有帮助。
希望这篇文章教会你爱而不是耐心或痛苦。
