鏈表簡介
鏈表是一種常見的數據結構，也屬於線性表，但不會按線性的順序來儲存數據。而是在每一個節點中，儲存了下一個節點的指針。可以看圖理解。(有C語言基礎的可能比較好理解)。
使用鏈表結構可以克服數組需要預先知道數據大小的缺點(C語言的數組需要預先定義長度)，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。
接下來就是介紹兩種常見的鏈表: 單向鏈表，雙向鏈表在JavaScript中的實現。
單向鏈表
鏈表中最簡單的形式就是單向鏈表，鏈表中的節點都包含兩個部分，第一部分儲存著自身信息，第二部分則儲存有指向下一節點的指針。最後一個節點則指向NULL:
JavaScipt中單向鏈表的實現
首先，創建一個構造函數。
/**
* 單向鏈表構造函數
*/
function LinkedList() {
/**
* 單向鏈表中節點的構造函數
* @param {Any} element 要傳入鏈表的節點
*/
var Node = function(element) {
this.element = element;
//下個節點的地址
this.next = null;
}
//單向鏈表的長度
var length = 0;
//單向鏈表的頭結點，初始化為NULL
var head = null;
}
不難看出，單向鏈表構造函數比棧與隊列要復雜許多。
單向鏈表需要有如下的方法:
append方法:
append方法:
說明: 添加元素到雙向鏈表尾部
實現:
/**
* 向鏈表尾部添加元素
* @param {Any} element 要加入鏈表的節點
* @return {Any} 加入鏈表的節點
*/
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var previous;
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};
insert方法:
說明: 向雙向鏈表中某個位置插入元素。
實現:
/**
* 向鏈表中插入某個元素
* @param {Number} position 要插入的位置
* @return {Boolean} 插入成功返回true，失敗返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var index = 0;
var previous;
var current = head;
if (position === 0) {
if (head === null) {
head = node;
tail = node;
} else {
current.prev = node;
node.next = current;
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;
}
previous.next = node;
node.prev = previous;
current.prev = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
removeAt方法:
說明:移除雙向鏈表中某個位置的元素。
實現:
/**
* 移除鏈表中某一個元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素，不成功則返回false
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var index = 0;
var previous;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current.prev;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return false;
}
};
showHead、showLength、showTail方法
實現:
/**
* 獲取鏈表的頭部
* @return {Any} 鏈表的頭部
*/
this.showHead = function() {
return head;
};
/**
* 獲取鏈表長度
* @return {Number} 鏈表長度
*/
this.showLength = function() {
return length;
};
/**
* 獲取鏈表尾部
* @return {Any} 鏈表尾部
*/
this.showTail = function() {
return tail;
};
感想
鏈表這一節，基本全部都是先按需求寫代碼，寫完後再和書上對比。發現簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂。看來還是太年輕了。