共计 3314 个字符，预计需要花费 9 分钟才能阅读完成。

本篇主要有三部分

什么是链表
链表的实现
链表的变种

源码地址：https://github.com/yhtx1997/S…
另外，今天 2019 年 2 月 18 日上午发现 2048-vue 版，代码版本不对，且最新版本遗失，无奈只得重新修复了下 2048-vue 地址：https://github.com/yhtx1997/S…
什么是链表
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。如下图：注：其中 00 06 10 12 18 为假定在内存中的地址
我将已经做好的链表存入数据，然后在控制台打印出来是这样的：
它看起来就像是这样的，一层套一层

其实应该是下面这样，类似于栓狗的铁链

链表的实现
链表功能

添加元素
获取指定位置元素
在指定位置插入元素
移除指定位置的元素
返回指定元素的位置
移除指定元素
是否为空
长度
获取表头
清空链表
转换为字符串输出

// 链表元素
class Node {
constructor(element) {
this.element = element; // 元素
this.next = undefined; // 指向下一个元素
}
}
class LinkedList {
// 构造函数声明一些全局变量
constructor(){
this.count = 0; // 长度
this.head = undefined; // 第一个元素
}
// 添加元素
push(element) {

}
// 获取指定位置元素
getElementAt(index) {

}
// 在指定位置插入元素
insert(element, index) {

}
// 移除指定位置的元素
removeAt(index) {

}
// 返回指定元素的位置
indexOf(element) {

}
// 移除指定元素
remove(element) {

}
// 是否为空
isEmpty() {

}
// 长度
size() {

}
// 获取表头
getHead() {

}
// 清空链表
clear() {

}
// 转换为字符串输出
toString() {

}
}
代码实现
class LinkedList {
// 构造函数声明一些全局变量
constructor(){
this.count = 0; // 长度
this.head = undefined; // 第一个元素
}
// 添加元素
push(element) {
const node = new Node(element);
if (this.head === undefined) {
this.head = node;
} else {
let current = this.head;
while (current.next !== undefined) {
current = current.next;
}
current.next = node;
}
this.count++;
}
// 获取指定位置元素
getElementAt(index) {
// 判断不是空链表
if (this.isEmpty() || index > this.count || index < 0) {
// 非空才能继续处理
// 判断不大于最大长度，不小于最小长度（0）
return undefined;
}
// 循环找到元素
let current = this.head;
for (let i = 0; i < index; i++){
current = current.next;
}
return current;// 返回找到的元素
}
// 在指定位置插入元素
insert(element, index) {
// 创建一个元素
let current = new Node(element);
// 首先确定是不是在首位置插入
if (index === 0){
current.next = this.head;
this.head = current;
} else {
// 找到指定位置前一个元素
let previous = this.getElementAt(index – 1);
// 将前一个元素的 next 赋值给插入元素的 next
current.next = previous.next;
// 将插入元素的 node 赋值给前一个元素的 next
previous.next = current;
}
this.count++;
}
// 移除指定位置的元素
removeAt(index) {
let current = this.head;
if (index === 0){
this.head = current.next;
} else {
// 找到这个元素和这个元素之前的元素
let previous = this.getElementAt(index – 1);
current = previous.next;
// 将这个元素的 next 赋值给这个元素之前元素的 next
previous.next = current.next;
}
this.count–;
// 返回要移除的元素
return current.element;
}
// 返回指定元素的位置
indexOf(element) {
// 从头开始找
let current = this.head;
// 不超过最大长度
for (let i = 0; i < this.size() && current != null; i++){
if (current.element === element){// 找到相等的就返回下标
return i;
}
current = current.next;
}
return -1;
}
// 移除指定元素
remove(element) {
// 获取指定元素位置
let index = this.indexOf(element);
// 移除指定位置元素
return this.removeAt(index);
}
// 是否为空
isEmpty() {
return this.size() === 0;
}
// 长度
size() {
return this.count;
}
// 获取表头
getHead() {
return this.head;
}
// 清空链表
clear() {
this.head = undefined;
this.count = 0;
}
// 转换为字符串输出
toString() {
if (this.head == null) {
return ”;
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current != null; i++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
let a = new LinkedList();
a.push(‘a’);
a.push(‘b’);
a.push(‘c’);
a.push(‘d’);
a.push(‘e’);
a.push(‘f’);
a.push(‘h’);
a.push(‘i’);
a.push(‘j’);
a.push(‘k’);
a.push(‘l’);
a.push(‘m’);
a.push(‘n’);
a.push(‘o’);
a.push(‘p’);
a.push(‘q’);
a.remove(‘a’);
a.insert(‘a’,1);
console.log(a);
插入元素图解：
现在有狗链两节，我要在中间加一节

先把两节分开，

然后把前边的尾部与要加的头部相连，然后把要加的尾部与后边的头部相连
0 连 xx , xx 连 1

链表的变种
双向链表
我们已经知道链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成，双向链表除了这个基本特性，每个元素还包含一个指向前一个元素的引用，如图所示：

循环链表
循环链表就是链表的最后一个指向下一个元素的引用指向了第一个元素，使其成为循环链表
双向循环链表
双向循环链表就是双向链表的第一个元素指向前一个的引用指向了最后一个元素，而最后一个元素指向下一个元素的引用指向了第一个元素，如图所示：

共计 2122 个字符，预计需要花费 6 分钟才能阅读完成。

1. 链表数据结构
链表存储有序的元素集合，但不同于数组，链表中的元素咋内存中并不是连续放置的每个元素有一个存储元素本身的节点和一个指向下一个元素的引用组成。下图展示了一个链表的结构：链表的优点：链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
缺点：因为含有大量的指针域，占用空间较大；查找元素需要遍历链表来查找，非常耗时。
适用场景：数据量较小，需要频繁增加，删除操作的场景
2. 创建链表
function LinkedList() {
// 创建一个 node 类，表示将要加入的项 element 表示要添加的值，next 指向列表中下一个节点项的指针
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
let head = null;
// 下面声明链表的方法
// 1. 向列表尾部添加一个新的项
this.append = function(element) {
let node = new Node(element);
current;
// 列表为空, 添加的是第一个元素
if(head === null) {
head = node;
// 列表不为空，向其追加
} else {

current = head;
// 循环列表，直到找到最后一项
while(current.next) {
current = current.next;
}
// 找到最后一项，将其 next 赋为 node，建立链接
current.next = node;
}
// 更新列表长度
length++;
}
// 2. 从列表中移除元素
this.removeAt = function(position) {
// 检查 position 是否超出链表范围
if(position > -1 && position < length) {
let current = head,
previous,
index = 0;
// 移除第一个元素
if(position === 0) {
head = current.next;
} else {
// 循环到指定位置，找到该位置的 previous 和 current
while(index++ < position) {
previous = current;
current = current.next;
}
// 将 previous 与 current 的下一项链接起来：跳过 current
previous.next = current.next;
}
// 链表长度减一
length–;
// 返回被删除项
return current.element;
} else {
// 不是有效位置，返回 null
return null
}
}
// 3. 在任意位置插入元素
this.insert = function(element, position) {
// 判断是否超过链表范围
if (position >= 0 && position<= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
// 在首位插入元素
if (position === 0) {
node.next = current;
head = node;
} else{
// x 循环到 position 应该添加的位置，取出 previous 和 current
while(index++ < position) {
previous = current;
current = current.next;
}
// 在 previous 和 current 间插入
node.next = current;
previous.next = node;
};
// 更新链表长度
length++;
return true;
} else{
return false;
};
}
//4. 把 LinkedList 对象转化成字符串
this.toString = function() {
let current = head,
string = ”;
while(current) {
string += current.element + (current.next ? ‘n’ : ”);
current = current.next;
}
return string;
}
//5. 链表中是否存在某个值
this.indexOf = function(element) {
let current = head,
index = 0;
while(current) {
if(element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
//6. 通过 element 实现 remove 元素
this.remove = function(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
//7.isEmpty size getHead 方法
this.isEmpty = function() {
return length === 0;
}
this.size = function() {
return length;
}
this.getHead = function() {
return head;
}
}