大家一定听说过数据结构与算法，算法就暂且先不讨论了，因为我知之甚少。但是数据结构这块我略懂一些，从这篇文章起我会陆续讲解一下JavaScirpt中的数据结构，比如：数组、队列、栈、集合、字典和散列表等等。
本次我要和大家唠叨的是 链表 ------------------------●'◡'●
1、链表数据结构
首先想和大家说的是，像链表呀、字典呀等词，不能一看见它就害怕，感觉它有多么高深，这些词只是一个概念而已，当你了解了背后的原理或者定义，你会觉得，呵呵，just so so。
先来点理论吧，必要的概念还是得看看的。
1-1、什么是链表
链表存储有序的元素集合，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。链表不同于数组，链表中的元素在内存中并不是连续放置的。
一图胜千言，还是上图吧
举个栗子：火车就很像链表。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢，改变它的位置，添加或移除它，每节车厢都是列表的元素，车厢间的连接就是指针
1-2、链表优缺点
优点：添加或移除元素的时候不需要移动其他元素。
缺点：访问链表的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素
如果不理解的话，那就等读完本文再回过头来看看就懂了。
2、创建链表
理解了链表是什么之后，现在开始实现一个链表数据结构。我定义一个类用来描述链表，这个类的名称是LinkedList,以下代码是这个类的骨架。
ps：什么是骨架，就是这个类应该有的属性或者方法，先不关注方法的具体实现，只关注有什么。
function LinkedList() {
let Node = function(element){ // {1}
this.element = element;
this.next = null;
};
let length = 0; // {2}
let head = null; // {3}
this.append = function(element){};
this.insert = function(position, element){};
this.removeAt = function(position){};
this.remove = function(element){};
this.indexOf = function(element){};
this.isEmpty = function() {};
this.size = function() {};
this.getHead = function(){};
this.toString = function(){};
this.print = function(){};
}
因为每一个节点需要保存自身的值和一个指向列表中下一个节点的指针，所以我们定义了一个构造函数Node（行{1}）
LinkedList 类也有存储列表项的数量的 length 属性（内部/私有变量）（行{2}）。
另外，我们还需要存储第一个节点的引用，把这个引用存储在head变量中（行{3}）。（如果你不想叫它head,可以改成其他的，你随意）
接下来，我们定义了LinkedList类的实例方法，你看看，还挺多的，其实都不难。
我们在实现这些方法前，先看看他们的职责：
| 方法名 | 职责 |
|---|---|
| append(element) | 向列表尾部添加一个新的项 |
| insert(position, element) | 向列表的特定位置插入一个新的项 |
| remove(element) | 从列表中移除一项 |
| indexOf(element) | 返回元素在列表中的索引。如果列表中没有该元素则返回-1 |
| removeAt(position) | 从列表的特定位置移除一项 |
| isEmpty() | 如果链表中不包含任何元素，返回 true，如果链表长度大于0则返回 false |
| size() | 返回链表包含的元素个数 |
| toString() | 由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值 |
2-1、向链表尾部追加元素
向 LinkedList 对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元素，或者列表不为空，向其追加元素。
下面是我们实现的 append 方法：
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //列表中第一个节点
head = node;
} else {
current = head; //{4}
//循环列表，直到找到最后一项
while(current.next){
current = current.next;
}
//找到最后一项，将其 next 赋为 node，建立链接
current.next = node; //{5}
}
length++; //更新列表的长度 //{6}
};
解释一下上述代码：
根据传入的值，用Node构造函数创建一个节点
如果head元素为null,意味着链表为空，我们只需要将head指向该元素
如果head元素不为null，我们需要找到最后一个节点，但是我们只有第一个元素的引用，也就是head，所以，我们来个while循环找到最后一个节点，你可能注意到了current这个变量。我详细的说明以下这个东西是干吗的吧。current变量就像一个指针，随着循环的进行，它指向的元素一直在变，循环结束时，它指向了链表中的最后一个元素，这样我们就拿到了链表中最后一个元素，也就是current。
你看，我这样说，你理解了这个current变量了吗？
你必须理解，因为这是编程中最常用的一种方法。
拿到了链表种的最后一项，我们就很容易的将元素插入到链表尾部了，只需要将current(别忘了，此时的current元素代表的是链表最后一个元素)的next属性置为待插入的元素(也就是node)
以上步骤，我们来张图说明一下吧。
最后，别忘了，更新一下链表的长度。
2-2、从链表中移除元素
有添加就有删除，此处删除节点有两个方法，分别为remove removeAt，我们先来看看removeAt移除元素的代码，remove方法非常简单我放到了后面讲解。
this.removeAt = function(position){
//检查越界值
if (position > -1 && position < length){
let current = head, //current代表当前项，它是随着循环的进行而不断变化的
previous, // current代表当前项，那么previous代表前一项
index = 0; // 用index来控制当前循环
//移除第一项
if (position === 0){ // 删除头部元素
head = current.next; //日常玩指针
} else {
while (index++ < position){ // index小于给定的查找位置的话，就继续循环
previous = current; // 改变前一项的引用
current = current.next; // 改变当前项的引用
}
//将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
previous.next = current.next;
}
length--; // 更改链表的长度
return current.element; //返回移除元素的值
} else {
return null; // {11}
}
};
首先我们先说说怎么就叫添加元素了，怎么就叫删除元素了。其实，就是一个玩指针的过程。
链表的大部分操作都是在玩指针，让这个元素的指针指向谁，让那个元素的指针指向谁。啥叫指针？就是next属性，obj.next=a; obj.next=b;你看，我一直在改变obj的指针，是不是so easy。
我先说一下删除元素的总体思路，带着这个思路去看上面的代码。
移除元素:
比如将元素A从链表中移除，A元素在链表中的位置为5.
A元素的上一个元素为B，A元素的下一个元素为C。
我们只需要干一件事就完成了移除元素A，那就是：将元素B的指针指向元素C。
如果我说的让你的思路乱了，那就想想火车吧，我要移除一节车厢，只需要将这节车厢的前一个车厢链接到这节车厢的后一个车厢就可以了。
来吧，叨叨半天了，看看图吧，可能一看图，就懂了。
可能会有人问，那A元素步还在吗，的确，它还在，不过，如果对它的引用计数为0，那么垃圾回收机制会将它收回。
2-3、在任意位置插入元素
我们一开始学习了，如何在链表尾部添加一个元素，现在该实现一下在任意位置插入元素的方法了insert
看代码之前，我建议你先思考一下，如何做，就叫插入元素，没思路的话就想想火车。火车要加一节车厢，该怎么做。
。。。。。。。。。
。。。。。。。。。
。。。。。。。。。
。。。。。。。。。
。。。。。。。。。
上代码喽：
this.insert = function(position, element){
//检查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //在第一个位置添加
node.next = current;
head = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
这段代码我希望你能读懂，我几乎没有加注释。
读不懂就想想火车，想想怎么改变指针。
读不懂就看看下面的图
2-4、实现其他方法
在这一节中，我们将会实现 toString、indexOf、isEmpty 和 size 等其他方法。这些方法没有多大难度。
toString方法
toString 方法会把 LinkedList 对象转换成一个字符串.
this.toString = function(){
let current = head,
string = '';
while (current) {
string +=current.element +(current.next ? 'n' : '');
current = current.next;
}
return string;
};
indexOf 方法
indexOf 方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。
this.indexOf = function(element){
let current = head,
index = -1;
 
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
实现了这个方法，我们就可以实现 remove 等其他的方法：
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
isEmpty、size 和 getHead 方法
this.isEmpty = function() {
return length === 0;
};
如果列表中没有元素，isEmpty 方法就返回 true，否则返回 false。
this.size = function() {
return length;
};
这个size()方法，我就不多说了。
this.getHead = function(){
return head;
};
到这里，一个简单的链表就算是完成了。怎么样，没有想象的那么可怕吧。 我们接下来介绍以下链表的其他类型。
3、双向链表
链表有多种不同的类型，双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
来张图看看吧
从图中，我们发现几点不一样的地方：
- 每个节点有两个指针，一个指向当前节点的前一个节点，另一个指向当前节点的后一个节点
LinkedList类增加了一个tail变量，用来指向链表尾部元素
知道了这些区别，让我们愉快的写一下双向链表这个类吧，我叫它DoublyLinkedList,你随意。
function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的
};
let length = 0;
let head = null;
let tail = null; //新增的
//这里是方法
}
双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。
3-1、在任意位置插入新元素
向双向链表中插入一个新项跟（单向）链表非常类似。区别在于，链表只要控制一个 next 指针，而双向链表则要同时控制 next 和 prev（previous，前一个）这两个指针。
我先把代码端出来：
this.insert = function(position, element){
//检查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //在第一个位置添加
if (!head){ //新增的
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //新增的
head = node;
}
} else if (position === length) { //最后一项 //新增的
current = tail; // {3}
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
在链表插入一个新元素的步骤：
- 迭代列表，直到到达要找的位置。我们将在
current和previous元素之间插入新元素。 - 首先，
node.next将指向current，而previous.next将指向node，这样就不会丢失节点之间的链接。 - 然后需要处理所有的链接：
current.prev将指向node，而node.prev将指向 previous。
用图来描述一下这个过程：
3-2、在任意位置移除元素
从双向链表中移除元素跟链表非常类似。唯一的区别就是还需要设置前一个位置的指针
从列表中间移除一个元素的步骤：
- 首先需要迭代列表，直到到达要找的位置。
current变量所引用的就是要移除的元素。 - 要移除它，我们可以通过更新
previous.next和current.next.prev的引用，在列表中跳过它。 previous.next将指向current.next，而current.next.prev将指向previous
还是用图来描述一下这个过程：
接下来就是代码实现了，我再三思考，决定，这部分代码由看客老爷实现吧，真好也能检测以下自己有没有掌握。
4、循环链表
前面介绍的两种链表的最后一个元素的next指针是指向null的，这样一来，只要我们遍历链表，当到达尾部节点时，循环就结束了。
循环链表，顾名思义，链表没有终止。可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。
单向循环列表，最后一个元素指向下一个元素的指针（tail.next）不是引用 null，而是指向第一个元素（head）。
来张图
双向循环链表有指向 head 元素的 tail.next，和指向 tail 元素的 head.prev。
再来张图
5、总结
总结一下吧
- 链表的优点是在不移动其他元素的情况下，就可以添加和移除元素
- 链表的缺点是每次操作都必须从链表第一个节点开始迭代，不想数组那样，通过下标就可以获取到值。
- 链表操作的是指针，无论添加还是删除节点。火车就是最好的例子。
好了，今天就到这里了。
文章中如果有错误或者有不懂的地方，欢迎给我留言。
