链表：存储有序的元素集合，但不同于数组，链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
好处：可以添加或移除任意项，它会按需扩容，且不需要移动其他元素。
与数组的区别：
数组：可以直接访问任何位置的任何元素；
链表：想要访问链表中的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
现实案例：康佳舞队、寻宝游戏
单向链表：一个节点只有链向下一个节点的链接；
双向链表：链接是双向的，一个链向下一个元素，另一个链向前一个元素
优点：双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。
-------------------------------------------------------------------------------------------------------------
链表方法声明：
1. 定义Node辅助类；
2. 内部属性 length；
2. 存储第一个节点（head）的引用
|
序号
|
方法
|
说明
|
|
1
|
append(element) | 向列表尾部添加一个新的项 |
|
2
|
insert(position, element) | 向列表的特定位置插入一个新的项 |
|
3
|
remove(element)
|
从列表中移除一项 |
|
4
|
indexOf (element )
|
返回元素在列表中的索引。如果列表中没有该元素则返回-1 |
|
5
|
removeAt(position) |
从列表的特定位置移除一项
|
|
6
|
isEmpty()
|
如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false
|
|
7
|
size ( )
|
返回链表包含元素个数。与数组的 length 属性类似 |
|
8
|
toString ( )
|
由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值 |
链表实现：
function LinkedList() {
// 定义辅助类Node
var Node = function(element) {
this.element = element; // element属性，即要添加到列表的元素
this.next = null; // next属性，即指向列表中下一个节点项的指针
}
var length = 0; // 内部属性/私有变量
var head = null; // 第一个节点的引用
// 向列表的尾部添加一个新的项
this.append = function(element) {
var node = new Node(element), // 把element作为值传入，创建Node项
current;
if (head === null) { // 列表中第一个节点，如果head元素为null，则意味着向列表添加第一个元素
head = node; // head指向node元素，下一个node将会自动生成null
} else {
current = head;
// 循环列表，直到找到最后一项
while(current.next) {
current = current.next;
}
// 找到最后一项，将其next赋为node，建立连接
current.next = node; // 列表中最后一个节点的下一个元素始终是null
}
length++; // 更新链表长度，这样就能控制它，轻松地得到列表的长度
};
// 向列表的特定位置插入一个新的项
this.insert = function(position, element) {
// 检查越界值
if (position >= 0 && position <= length) {
var 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;
}
};
// 从列表的特定位置移除一项
this.removeAt = function(position) {
// 检查越界值
if (position > -1 && position < length) {
var current = head, // current变量总是为对所循环列表的当前元素的引用
previous, // previous变量为对当前元素的前一个元素的引用
index = 0;
// 移除第一项
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;
}
};
// 从列表中移除一项
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
// 返回元素在列表中的索引。如果列表中没有该元素则返回-1
this.indexOf = function(element) {
var current = head,
index = -1;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false
this.isEmpty = function() {
return length === 0;
};
// 返回链表包含元素个数。与数组的 length 属性类似
this.size = function() {
return length;
};
// 由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值
this.toString = function() {
var current = head,
string = '';
while (current) {
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function () {
return head;
};
}
LinkedList.js
双向链表实现:
function DoublyLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0;
var head = null;
var tail = null; // 新增的
// 特定位置插入元素
this.insert = function(position, element) {
// 检查越界值
if (position >= 0 && position <= length) {
var 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-1) { // 最后一项 //新增的
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
previous.next = node;
}
node.next = current;
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++;
return true;
} else {
return false;
}
};
// 特定位置删除元素
this.removeAt = function(position) {
// 检查越界值
if (position > -1 && position < length) {
var current = head,
previous,
index = 0;
// 移除第一项
if (position === 0) {
head = current.next;
// 如果只有一项，更新tail //新增的
if (length === 1) {
tail = null;
} else {
head.prev = null;
}
} else if (position === length-1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
// 将prvious与current的下一项链接起来——跳过current
previous.next = current.next;
current.next.prev = previous; // 新增的
}
length--;
return current.element;
} else {
return null;
}
};
}
DoublyLinkedList.js
参考书籍：《学习JavaScript数据结构与算法》