定义
链表是由一组节点组成。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。
设计一个基于对象的链表
- 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;
}
实现方法
我们首先实现 insert 方法， 但是实现insert方法之前可以先实现 find 方法，先找到已知节点，然后将新节点插入到已知节点后：
function find(item) {
var currentNode = this.head;
while(currentNode.element!=item) {
currentNode = currentNode.next
}
return currentNode;
}
现在就可以实现insert方法了：
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
展示所有数据的 display 方法：
function display() {
var currentNode = this.head;
while(currentNode != null) {
console.log(currentNode.element);
currentNode = currentNode.next;
}
}
测试我们写的方法：
var cities = new LList();
cities.display();
cities.insert('second', 'head');
cities.insert('third', 'second');
cities.insert('second-third', 'second');
cities.display();
结果
我们似乎还少写了一个 remove 方法，从链表中删除节点时，需要找到待删除节点前面的节点。找到这个节点后修改它的 next 属性，使其不再指向待删除的节点，而是指向待删除节点的下一个节点。我们可以先写一个findprevious方法：
function findPrevious(item) {
var currentNode = this.head;
while(currentNode.next != null && currentNode.next.element != item) {
console.log(currentNode.next);
currentNode = currentNode.next;
}
return currentNode;
}
所以，现在可以写remove 方法了：
function remove(item) {
var currentNode = this.findPrevious(item);
if (currentNode.next != null) {
currentNode.next = currentNode.next.next;
}
}
现在可以来测试下我们写的remove 方法了。
cities.remove('second');
console.log('删除second后:');
cities.display();
结果
双向链表
首先我们需要给Node类增加一个 previous 属性：
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
由于现在节点多了一个 previous 属性，所以需要改造下 insert 方法：
function insert(newElement, item) {
var currentNode = this.find(item);
var newNode = new Node(newElement);
newNode.previous = currentNode;
newNode.next = currentNode.next;
currentNode.next.previous = newNode;
currentNode.next = newNode;
}
双向链表的 remove 方法比单向链表的效率更高，因为不需要再查找前驱节点了，首先要在链表中查找待删除的节点，然后再设置该节点前驱节点的 next 属性，使其指向待删除节点的后驱节点就好了。
function remove(element) {
var currentNode = this.find(element);
if (currentNode.next != null) {
currentNode.previous.next = currentNode.next;
currentNode.next.previous = currentNode.previous;
currentNode.next = null;
currentNode.previous = null;
}
}
最后我们再实现一个反向打印链表的方法，就基本完成了链表的基本方法实现，实现这个方法之前我们需要实现一个 findLast 方法来查找链表最后一个节点：
findLast() {
var currentNode = this.head;
while(currentNode.next != null) {
currentNode = currentNode.next;
}
return currentNode;
}
这时候我们就可以很容易实现反向打印链表了：
function dispReverse() {
var lastNode = this.findLast();
while(lastNode.previous != null) {
console.log(lastNode.element);
lastNode = lastNode.previous;
}
console.log(lastNode.element);
}
