鏈表
相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或移除元素的時候不需要移動其他元素。
5.1 創(chuàng)建一個鏈表
function LinkedList() {
var Node = function(ele) {
this.ele = ele;
this.next = null;
};
var length = 0;
var head = null;
// 5.1.1 向列表尾部添加一項
this.append = function(ele) {
var node = new Node(ele),
current;
if (head === null) {
head = node;
} else {
current = head;
// 循環(huán)列表，直到找到最后一項
while (current.next) {
current = current.next;
}
// 找到最后一項，將其next賦為node,建立鏈接
current.next = node;
}
length++; // 更新列表長度
};
// 5.1.2 根據特定位置移除一個元素
this.removeAt = function(pos) {
// 檢查越界值
if (pos > -1 && pos < length) {
var current = head,
prev,
index = 0;
// 移除第一項
if (pos === 0) {
head = current.next;
} else {
while (index++ < pos) {
prev = current;
current = current.next;
}
// 將prev與current的下一項鏈接起來：跳過current,從而移除它
prev.next = current.next;
}
length--;
return current.ele;
} else {
return null;
}
};
// 5.1.3 在任意位置插入一個元素
this.insert = function(pos, ele) {
// 檢查越界值
if (pos >= 0 && pos <= length) {
var node = new Node(ele),
current = head,
prev,
index = 0;
// 在第一個位置添加
if (pos === 0) {
node.next = current;
head = node;
} else {
while (index++ < pos) {
prev = current;
current = current.next;
}
node.next = current;
prev.next = node;
}
length++;
return true;
} else {
return false;
}
};
// 5.1.4 實現(xiàn)其他方法
// 1.toString方法
this.toString = function() {
var current = head,
str = '';
while (current) {
str += ',' + current.ele;
current = current.next;
}
return str.slice(1);
};
// 2.indexOf方法
this.indexOf = function(ele) {
var current = head,
index = 0;
while (current) {
if (ele === current.ele) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 3.remove方法
this.remove = function(ele) {
var index = this.indexOf(ele);
return this.removeAt(index);
};
// 4.isEmpty,size,和getHead方法
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function() {
return head;
};
}
5.2 雙向鏈表
雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或反過來
優(yōu)點： 在單向鏈表中，如果迭代列表時錯過了要找的元素，就需要從頭再來，雙向鏈表則不需要如此
function DoublyLinkedList() {
var Node = function(ele) {
this.ele = ele;
this.next = null;
this.prev = null; // 新增的
}
var length = 0;
var head = null;
var tail = null; // 新增的
// 5.2.1 在任意位置插入一個新元素
this.insert = function (pos, ele) {
// 檢查越界值
if (pos >= 0 && pos <= length) {
var node = new Node(ele),
current = head,
prev,
index = 0;
if (pos === 0) { // 在第一個位置添加
if (!head) {
head = node;
tail = node;
} else {
node.next = current;
current.prev = node;
head = node;
}
} else if (pos === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < pos) {
prev = current;
current = current.next;
}
node.next = current;
prev.next = node;
current.prev = node;
node.prev = prev;
}
length++;
return true;
} else {
return false;
}
}
// 5.2.2 從任意位置移除元素
this.removeAt = function(pos) {
if (pos > -1 && pos < length) {
var current = head,
prev,
index = 0;
// 移除第一項
if (pos === 0) {
head = current.next;
if (length === 1) {
tail = null;
} else {
head.prev = null;
}
} else if (pos === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < pos) {
prev = current;
current = current.next;
}
prev.next = current.next;
current.next.prev = prev;
}
length--;
return current.ele;
} else {
return null;
}
};
}
