1、鏈表
鏈表存儲有序的元素集合阐滩，但不同于數(shù)組二打，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本事的節(jié)點和一個指向下一個元素的引用組成叶眉。相對于傳統(tǒng)的數(shù)組址儒，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素衅疙。然而，鏈表需要使用指針鸳慈，因此實現(xiàn)鏈表時需要額外注意饱溢。
數(shù)組和鏈表的一個不同在于數(shù)組可以直接訪問任何位置的元素，而想要訪問鏈表中的一個元素走芋，需要從起點開始迭代列表绩郎。
1.1、單向鏈表
下面是單向鏈表的具體實現(xiàn)代碼：
function LinkedList() {
var Node = function(element){
this.element = element;
this.next = null;
};
var length = 0;//鏈表長度
var head = null;//第一個節(jié)點
this.append = function(element){
var node = new Node(element),
current;
if (head === null){ //列表為空
head = node;
} else { //列表不為空
current = head; //現(xiàn)在只知道第一項head
while(current.next){ //找到列表的最后一項
current = current.next;
}
//建立鏈接
current.next = node;
}
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; //先連上添加的節(jié)點
previous.next = node; //再斷開之前的連接
}
length++;
return true;
} else {
return false;
}
};
this.removeAt = function(position){
if (position > -1 && position < length){
var current = head,
previous,
index = 0; //用來迭代列表翁逞，直到到達目標(biāo)位置
if (position === 0){ //移除第一項
head = current.next;
} else { //移除中間或者尾部最后一項
while (index++ < position){
previous = current;
current = current.next;
}
//連接前一項和后一項肋杖，跳過當(dāng)前的項，相當(dāng)于移除了當(dāng)前項
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
var index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
var current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++; //記錄位置
current = current.next;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){
var current = head,
string = '';
while (current) {
string += current.element;//拼接
current = current.next;
}
return string;
};
this.print = function(){
console.log(this.toString());
};
}
1.2挖函、雙向鏈表
雙向鏈表和單向鏈表的區(qū)別在于状植，在單向鏈表中，一個節(jié)點只有鏈向下一個節(jié)點的鏈接。而在雙向鏈表中津畸，鏈接是雙向的：一個鏈向下一個元素振定，另一個鏈向前一個元素。示例代碼如下：
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.append = function(element){
var node = new Node(element),
current;
if (head === null){ //列表為空
head = node;
tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
length++;
};
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) { //最后一項
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node; //把node節(jié)點連接進去前一個節(jié)點和后一個節(jié)點
current.prev = node; //斷掉之前previous和current的連接
node.prev = previous; //prev同樣需要連接
}
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;
if (length === 1){ // 列表只有一項
tail = null;
} else {
head.prev = null;
}
} else if (position === length-1){ 移除最后一項
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next; // 鏈接前一項和后一項肉拓，跳過當(dāng)前項
current.next.prev = previous; //修復(fù)prev
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
var index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
var current = head,
index = -1;
//檢查第一項
if (element == current.element){
return 0;
}
index++;
//檢查中間項
while(current.next){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
//檢查最后一項
if (element == current.element){
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this. size = function() {
return length;
};
this.toString = function(){
var current = head,
s = current ? current.element : '';
while(current && current.next){
current = current.next;
s += ', ' + current.element;
}
return s;
};
this.inverseToString = function() {
var current = tail,
s = current ? current.element : '';
while(current && current.prev){
current = current.prev;
s += ', ' + current.element;
}
return s;
};
this.print = function(){
console.log(this.toString());
};
this.printInverse = function(){
console.log(this.inverseToString());
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
}
}
1.3后频、循環(huán)鏈表
循環(huán)鏈表可以像單向鏈表那樣只有單向引用，也可以像雙向鏈表那樣有雙向引用暖途。循環(huán)鏈表和其他鏈表的區(qū)別在于最后一個元素指向下一個元素的引用不是null卑惜，而是指向第一個元素（head）。示例代碼如下：
function CircularLinkedList() {
var Node = function(element){
this.element = element;
this.next = null;
};
var length = 0;
var head = null;
this.append = function(element){
var node = new Node(element),
current;
if (head === null){ //列表為空
head = node;
} else {
current = head;
while(current.next !== head){ //最后一個元素將是head驻售，而不是null
current = current.next;
}
current.next = node; //建立連接
}
node.next = head; //首尾相連起來變成一個環(huán)列表
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;
while(current.next !== head){
current = current.next;
}
head = node;
current.next = head;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
if (node.next === null){ //在最后一個元素更新
node.next = head;
}
}
length++;
return true;
} else {
return false;
}
};
this.removeAt = function(position){
if (position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0){
while(current.next !== head){
current = current.next;
}
head = head.next;
current.next = head; //更新最后一項
} else {
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
var index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
var current = head,
index = -1;
if (element == current.element){ //檢查第一項
return 0;
}
index++;
while(current.next !== head){ //檢查列表中間
if (element == current.element){
return index;
}
current = current.next;
index++;
}
if (element == current.element){ //檢查最后一項
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){
var current = head,
s = current.element;
while(current.next !== head){
current = current.next;
s += ', ' + current.element;
}
return s.toString();
};
this.print = function(){
console.log(this.toString());
};
}
