鏈表是一種常見的資料結構,也屬於線性表,但不會按線性的順序來儲存資料,而是在每一個節點中儲存了指向下一個節點的指標。使用鏈表結構可以克服陣列需要預先知道資料大小的缺點,能充分利用記憶體空間,實現靈活的動態記憶體管理。接下來介紹單向鏈表與雙向鏈表在 JavaScript 中的實現。
鏈表中最簡單的形式就是單向鏈表。鏈表中的每個節點都包含兩個部分:第一部分儲存自身資訊,第二部分則儲存指向下一節點的指標,最後一個節點指向 NULL。
首先建立一個構造函式:
/**
* 單向鏈表構造函式
*/
function LinkedList() {
/**
* 單向鏈表中節點的構造函式
* @param {Any} element 要傳入鏈表的節點
*/
var Node = function(element) {
this.element = element;
this.next = null; // 下個節點的地址
}
var length = 0; // 鏈表長度
var head = null; // 頭節點,初始化為 NULL
}
單向鏈表需要具備 append、insert、indexOf、remove、removeAt、getHead、isEmpty、toString、size 等方法。
雙向鏈表的每個節點除了指向下一節點外,還有一個指向前一節點的指標,因此需要同時維護 head 與 tail。它需要具備 insert、removeAt、showHead、showLength、showTail 等方法。
向鏈表尾部添加元素:
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};
向雙向鏈表中某個位置插入元素:
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;
}
};
移除雙向鏈表中某個位置的元素:
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;
}
};
this.showHead = function() {
return head;
};
this.showLength = function() {
return length;
};
this.showTail = function() {
return tail;
};
鏈表這一節,基本都是先按需求寫程式碼,寫完後再和書上對比,發現被瞬間秒成渣——自己寫的很多暗坑,邏輯也很混亂。看來還是學藝不精,需要多加練習。