读【数据结构与算法】之链表
链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向他的下一个节点，指向另一个节点的引用就叫链。这样也就形成了链表。
实现链表需要两个类，一个是节点类Node，还有链表LinkedList类。
基本链表
最基本链表，也就是从头节点开始，一个链接着一个节点，直至最后一个，遍历的话只能从头开始到尾。
基本实现：
/**
* Class Node
* 节点类
*/
function Node(element) {
this.element = element;
this.next = null;
}
/**
* Class LinkedList
* 链表 LinkedList
*/
function LinkedList() {
this.head = new Node('head');
}
LinkedList.prototype = {
constructor: LinkedList,
/**
* 查找链表项
* @param {Any} item 某项
* @return {Node|Null} 节点或者null
*/
find: function find(item) {
var currNode = this.head;
while (currNode && currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
},
/**
* 查找链表中哪个节点的下一个节点中的元素是查找项
* @param {Any} item 查找项
* @return {Node|Null} 节点或者null
*/
findPrevious: function findPrevious(item) {
var currNode = this.head;
while (currNode.next != null && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
},
/**
* 在某项后插入新项
* @param {Any} newElement 插入新项
* @param {Any} item 某项
* @return {Undefined} undefined
*/
insert: function insert(newElement, item) {
var current = this.find(item);
if (!current) return;
var newNode = new Node(newElement);
newNode.next = current.next;
current.next = newNode;
},
/**
* 得到所有项
* @return {Array} 所有项
*/
display: function display() {
var ret = [];
var currNode = this.head;
while (currNode.next != null) {
ret.push(currNode.next.element);
currNode = currNode.next;
}
return ret;
},
/**
* 移除链表中某项
* @param {Any} item 某项
* @return {Undefined} undefined
*/
remove: function remove(item) {
var preNode = this.findPrevious(item);
if (preNode && preNode.next != null) {
preNode.next = preNode.next.next;
}
}
};
双向链表
对于基本链表，如果想要从尾往头去遍历的话，就很困难了。那么咱们可以给Node增加一个属性，通过该属性执行前一个节点的引用，这样，也就形成了双向链表。对于双向链表，每一个节点都能找到他的前一个和后一个节点。
基本实现：
/**
* Class BidNode
* 双向节点类
*/
function BidNode(element) {
this.element = element;
this.next = null;
this.previous = null;
}
/**
* Class BidLinkedList
* 双向链表 BidLinkedList
*/
function BidLinkedList() {
this.head = new BidNode('head');
}
BidLinkedList.prototype = {
constructor: BidLinkedList,
/**
* 查找链表项
* @param {Any} item 某项
* @return {BidNode|Null} 节点或者null
*/
find: function find(item) {
var currNode = this.head;
while (currNode && currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
},
/**
* 查找链表中最后的节点
* @return {BidNode|Null} 节点或者null
*/
findLast: function findLast() {
var currNode = this.head;
while (currNode.next != null) {
currNode = currNode.next;
}
return currNode;
},
/**
* 在某项后插入新项
* @param {Any} newElement 插入新项
* @param {Any} item 某项
* @return {Undefined} undefined
*/
insert: function insert(newElement, item) {
var current = this.find(item);
if (!current) return;
var newNode = new BidNode(newElement);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
},
/**
* 得到所有项
* @return {Array} 所有项
*/
display: function display() {
var ret = [];
var currNode = this.head;
while (currNode.next != null) {
ret.push(currNode.next.element);
currNode = currNode.next;
}
return ret;
},
/**
* 反向得到所有项
* @return {Array} 所有项
*/
disReverse: function disReverse() {
var ret = [];
var currNode = this.findLast();
while (currNode.previous != null) {
ret.push(currNode.element);
currNode = currNode.previous;
}
return ret;
},
/**
* 移除链表中某项
* @param {Any} item 某项
* @return {Undefined} undefined
*/
remove: function remove(item) {
var currNode = this.find(item);
if (currNode && currNode.next != null) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
};
具体运行例子请看demojs实现链表