数据结构浅析：链表
你有修建过戈德堡机械吗？如果没有，也许应该修建过精心构建的多米诺骨牌线？
好的，也许你的童年应该不像我一样书呆子。就这样吧，对于玩过上述两者中任意一样的人，你已经掌握了今天数据结构的本质：链表！
链表是怎么工作的
链表的最简单实现形式—单链表--是一系列的节点，每一个单独的节点都包含一个值和一个指向链表中下一个节点的指针。
添加（Add）通过在表的尾部添加一个项目增加列表的大小。
移除（Remove）通常移除链表中指定位置的元素。
搜索（Contains）将在列表中搜索一个指定的值。
使用例子：
哈希表中为了防止出现冲突，将 values 存储在一个列表中
-
重拍极速前进（The Amazing Race）
为了让这篇文章保持轻松友好一些，我们一起来创建一个 CBS 可用于计划其下一季“极速前进”真人秀拍摄的工具。
在阅读本文时，我希望你能够一直问自己：“链表和数组有什么区别？它们有什么相似之处？”
我们开始吧。
首先，你需要创建一个链表：
class LinkedList{
constructor(){
this._head = null;
this._tail = null;
this._length = 0;
}
size(){
return this._length;
}
}
为了跟踪比赛的起点和终点，需要创建 head 和 tail 属性。
然后，为了保证赛程不要太长或者太短，需要创建 length 属性和 size 方法。这样你就总是可以精确的掌握赛程的长度。
现在你有了一种存储数据的方法，你应该创建一个往列表添加数据的方法。问题是，你要添加什么数据呢？
记住，链表是一系列的节点，每一个节点都有一个值和指向列表中下一个节点的指针。了解了这一点，你会意识到节点就是一个存储有 value 和 next 两个属性的对象。
由于每一次往列表添加数据都需要创建一个新的节点，你决定创建一个构造函数，这样每次往列表添加数据时创建节点会更简单一些。
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}
有了构造函数，就可以创建 add 方法。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value); //we create our node
if(!this._head && !this._tail){ //If it's the first node
this._head = node; //1st node is head & tail
this._tail = node;
}else{
this._tail.next = node; //add node to the back
this._tail = this._tail.next; //reset tail to last node
}
this._length++;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
现在你已经添加了这个方法，你可以往 “AmazingRace” 列表中添加一堆比赛地点。看起来像这样。注意为了更容易理解我添加了一些额外的空格。
{ _head:
{ value: 'Colombo, Sri Lanka',
next: { value: 'Lagos, Nigeria',
next: { value: 'Surat, India',
next: { value: 'Suzhou, China',
next: null
}
}
}
},
_tail: { value: 'Suzhou, China', next: null },
_length: 4
}
好啦，现在已经创建了列表以及添加内容的方法，你意识到往列表中添加地点还需要一些方法。
你决定将这个链表共享给合作者，Kent，要求他往里面添加更多的比赛地点。唯一的问题是，当你将列表给他时，没有告诉他你已经添加了哪些地点。不幸的是你也忘记了。
当然他可以通过运行 console.log(AmazingRace) 然后逐一检查其输出。但是 Kent 是一个懒人，他需要一种方式来确认某些值是否已经存在列表中，从而避免重复添加。考虑到这一点，你创建了 contains 方法来检查是否包含某些值。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //true
AmazingRace.contains('Hanoi, Vietnam'); //false
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.contains('Seattle, Washington'); //false
AmazingRace.add('Seattle, Washington');
AmazingRace.contains('North Pole'); // false
AmazingRace.add('North Pole');
很棒，现在 Kent 为了避免重复，他可以在添加之前检查一下是否已经存在。
另一方面，你可能会想为什么不在添加之前进行检查从而避免重复呢？当你在实现一个链表—或者任意的数据结构时— 理论上你可以添加任何额外你想要的功能。
你甚至可以改变已有数据结构中原来的方法。在 REPL 中试一下以下代码：
Array.prototype.push = () => {
return 'cat';
}
let arr = [];
arr.push('eggs'); // returns 'cat';
我们没有做这些事情的原因是因为约定的标准。基本上，开发者对特定的方法应该如何工作是有预期的。
尽管我们的链表不是 JavaScript 的原生库，我们在实现它时拥有更多的自由，但是这些数据结构如何运作我们仍有基本的期望。链表本身并不保证存储的值唯一。但是它们确实可以提供 contains 这样的方法允许我们进行预检，从而维护我们列表中的值不重复。
Kent 将他修改后的列表再发给你，但是其中一些可能有问题。比如北极可能不是“极速前进”最好的终点。
所以你决定创建一个可以移除某些节点的方法。一定要记住的是，一旦你删除了某一个节点，你就打断了列表，你需要将被删除节点的前后两个节点重新连接起来。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){ // see if our value exists
let current = this._head; // begin at start of list
let previous = this._head;
while(current){ // check each node
if(current.value === value){
if(this._head === current){ // if it's the head
this._head = this._head.next; // reset the head
this._length--; // update the length
return; // break out of the loop
}
if(this._tail === current){ // if it's the tail node
this._tail = previous; // make sure to reset it
}
previous.next = current.next; // unlink (see img below)
this._length--; // update the length
return; // break out of
}
previous = current; // look at the next node
current = current.next; // ^^
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.add('Seattle, Washington');
AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');
remove 方法的代码比较长。本质上它按照如下步骤运行：
1、检查待删除的值是否存在。。。
2、遍历列表，并且需要跟踪当前节点和上一个节点
3、然后，如果当前节点就是要删除的点—>
4A、当前节点是链表的头
- 将链表的头重置为列表中的下一个节点
- 更新链表长度
- 跳出循环
4B、当前节点是链表的尾 - 将链表的尾设置为链表中的上一个节点
- 按照下图的方式重新连接节点
-
4C、如果不是要删除的节点—>继续迭代
- 将下一个节点设置为当前节点
- 将当前节点设置为上一个节点
最后要说说明的一件事：你可能已经注意到你并没有真正的删除那个节点。你只是移除了对它的引用。对，这样就可以了，因为一旦对一个对象的所有引用都被移除以后，垃圾回收器会帮助我们将它从内存中移除的。更多关于垃圾回收的信息参考这里
有了你刚才实现的 remove 方法，你只需下面这一行就可以保证参赛者不会冻死、或者打扰在正在准备新年庆典的圣诞老人。
AmazingRace.remove('North Pole');
好了，你已经完成了一个单链表的简单实现。你可通过添加元素来扩充列表，也可以通过移除元素来压缩列表。
如果你想在链表的首部、尾部或者任意节点后插入元素。你需要自己实现这些方法。这些方法的名称和参数应该类似这样：
addHead(value) {
}
insertAfter(target, value){
}
时间复杂度分析
再来看一下完整的代码
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){
let current = this._head;
let previous = this._head;
while(current){
if(current.value === value){
if(this._head === current){
this._head = this._head.next;
this._length--;
return;
}
if(this._tail === current){
this._tail = previous;
}
previous.next = current.next;
this._length--;
return;
}
previous = current;
current = current.next;
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}
Add 的复杂度是O(1)：因为有 tail 属性跟踪队列的尾部，所以你不必遍历整个列表。
Remove 的复杂度是 O(n)： 最坏的情况下，你需要遍历完整个列表才能找到你需要移除的节点。尽管真正的移除节点的操作是 O(1)（因为你只需要重置一下指针就可以）。
Contains 的复杂度是 O(n)：为了确认列表中是否包含指定的值，你必须遍历整个列表。
addHead 的复杂度是 O(1)：和我们的 add 方法相似，我们总是知道列表的头部，所以不需要遍历。
insertAfter 的复杂度是 O(n)：和上面讨论的 Remove 方法一样，你需要遍历整个列表找到你需要插入的位置。同样的，实际的插入操作复杂度为 O(1) 。
链表 VS 数组
为什么要使用链表而不是数组？技术上数组可以运行所有链表操作，如 添加、插入、删除。此外， JavaScript 中数组已经具备这些方法。
最大的差别来自插入和删除。因为数组是基于索引，当你在数组的中间插入或者删除元素时，你需要将其后面所有的元素重置到新的索引位置。
想象一下，在一个有 100,000 个元素的头部或者中间插入一个元素！像这样的插入和删除操作是非常耗费资源的。因为这一点，链表通常用于常常被移动的大型数据集。
另一方面，数组在查找方面非常出色，因为它是基于索引的。如果你知道元素的位置，你可以通过 array[position] 在 O(1) 时间内查找到该元素。
链表通常需要顺序遍历列表。基于这一原因，数组常常用于小一些的数据集或者不常移动的数据集。
小节
链表：
- 1、有 tail 和 head 属性用于跟踪链表的两端
- 2、有 add， addHead，insertAfter 和 remove 方法用于管理列表内容
- 3、有 length 属性用过跟踪列表长度
本文译自 ：A Gentle Introduction to Data Structures: How Linked Lists Work
