链表是由一组节点组成的集合，每个节点使用一个对象的引用指向它的后继，指向另一个节点的引用就是链。在 JavaScript 中，数组也可以存储元素，但是数组说到底也是一个对象，与其他语言相比效率比较低，因此出现了链表，它可以更方便地代替数组来实现同样的数据存储与移动效果。
定义链表
为了更形象地表示链表，我从网上找了一张表示图，如下
图片来自网络
每个链表都有一个头结点，头结点通常作为链表的接入点，它不参与链表的遍历，同样还会有一个尾元素，指向一个 null 结点。在 JavaScript 中，实现一个基于对象的链表，使用两个类，一个类用来表示所有的结点，另一个类用来表示一些链表的基本方法。
Node 类
function Node(element) {
this.element = element; // 保存节点上的数据
this,next = null; // 保存指向下一个节点的链接
}
LinkedList 类
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.remove = remove;
this.display = display;
}
实现插入节点
插入一个节点，首先要明确是在某个节点的前面或后面插入，假设在一个已知节点后面插入元素，则需要先找到该节点“后面”的节点，然后将新节点的 next 属性设置为“后面”节点的 next 属性对应的值，然后设置“后面” 的节点的 next 属性指向新节点。
// 定义一个 find 来找到 “后面” 的节点
function find(item) {
var currNode = this.head;
while(currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement,item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
现在插入新节点的方法已经完成，我们紧接着定义一个方法用于展示链表中的元素
function display() {
var currNode = this.head;
while(!(currNode.next == null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
删除节点
删除链表中的一个元素，我们首先要找到该元素所在的节点，然后找到它前面的节点，使其的 next 属性指向待删除节点的下一个节点，这样就可以把节点 remove 掉。
// 定义 findPrevious 方法寻找前面节点
function findPrevious(item){
var currNode = this,head;
while(!(currNode.next == null) && (currNode.next.element != item)){
currNode = currNode.next;
}
return currNode;
}
function remove(item) {
var prevNode = this.findPrevious(item);
if(!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
这里的prevNode.next = prevNode.next.next;就是使前面的节点直接指向待删除节点后面的节点。
完整代码
最后放上完整的代码，包含 Node 类、LList 类和测试代码；
function Node(element) {
this.element = element;
this,next = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.remove = remove;
this.display = display;
}
function remove(item) {
var prevNode = this.findPrevious(item);
if(!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
function findPrevious(item){
var currNode = this.head;
while(!(currNode.next == null) && (currNode.next.element != item)){
currNode = currNode.next;
}
return currNode;
}
function display() {
var currNode = this.head;
while(!(currNode.next == null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function find(item) {
var currNode = this.head;
while(currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement,item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
var city = new LList();
city.insert("Guangzhou","head");
city.insert("Shenzhen","Guangzhou");
city.insert("Shantou","Shenzhen");
city.insert("Zhuhai","Shantou");
city.display();
city.remove("Shenzhen");
city.display();
参考资料：Data Structure and Algorithms Using JavaScript, Michael McMillan 著
