假設理解 Big O 表示法。 JavaScript 中有範例。資料參考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》
鍊錶是一種表示節點序列的資料結構。 在單鍊錶中，每個節點都指向下一個節點。
在記憶體中，這些節點不需要連續排序（彼此相鄰），因為我們不依賴索引。當我們迭代鍊錶時，我們會遍歷節點的每個引用，直到遇到null指標。
在單鍊錶中，每個節點通常包含兩個欄位：
head 是對列表中第一個節點的 引用。它很重要，因為它允許存取鍊錶的開頭。它有時充當哨兵節點（放置在實際頭節點之前），以便更輕鬆地進行操作，例如在頭部插入。尾部是對清單中最後一個節點的引用。它的下一個指標為空，表示列表的結尾。
與陣列相比，鍊錶在插入/刪除方面具有更高的記憶體效率，因為這些操作不需要「移動」元素。從鍊錶中的任意位置新增或刪除元素的操作需要 O(1) O(1)n)O(n🎜>
最壞情況下遍歷鍊錶然後新增/刪除元素的時間（不適用於新增/刪除第一個元素）。
n)
O(n🎜> O(n) 刪除：O(n🎜> O(n)
class ListNode {
constructor(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}
}
class LinkedList {
constructor() {
// sentinel node for easy operations on head
this.head = new ListNode(-1);
this.tail = this.head;
}
// get the value at the specified index.
get(index) {
let curr = this.head.next;
let i = 0;
while (curr !== null) {
if (i === index) return curr.val;
curr = curr.next;
i++;
}
return -1;
}
// insert a new value at the head of the list.
insertHead(val) {
const newNode = new ListNode(val);
newNode.next = this.head.next;
this.head.next = newNode;
if (newNode.next === null) {
this.tail = newNode;
}
}
// insert a new value at the tail of the list.
insertTail(val) {
const newNode = new ListNode(val);
this.tail.next = newNode;
this.tail = newNode;
}
// remove the node at the specified index.
remove(index) {
let curr = this.head;
let i = 0;
while (i < index && curr.next !== null) {
i++;
curr = curr.next;
}
if (curr !== null && curr.next !== null) {
if (curr.next === this.tail) this.tail = curr;
curr.next = curr.next.next;
return true;
}
return false;
}
// get all values in the list as an array.
getValues() {
const values = [];
let curr = this.head.next;
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
}
// get the length of the list.
length() {
let length = 0;
let curr = this.head.next;
while (curr !== null) {
length++;
curr = curr.next;
}
return length;
}
}
function ListNode(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}
function LinkedList() {
this.head = new ListNode(-1); // Sentinel node
this.tail = this.head;
}
// get the value at the specified index
LinkedList.prototype.get = function(index) {
let curr = this.head.next;
let i = 0;
while (curr !== null) {
if (i === index) return curr.val;
curr = curr.next;
i++;
}
return -1;
};
// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
const newNode = new ListNode(val);
newNode.next = this.head.next;
this.head.next = newNode;
if (newNode.next === null) {
this.tail = newNode;
}
};
// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
const newNode = new ListNode(val);
this.tail.next = newNode;
this.tail = newNode;
};
// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
let curr = this.head;
let i = 0;
while (i < index && curr.next !== null) {
i++;
curr = curr.next;
}
if (curr !== null && curr.next !== null) {
if (curr.next === this.tail) this.tail = curr;
curr.next = curr.next.next;
return true;
}
return false;
};
// get all values in the list as an array
LinkedList.prototype.getValues = function() {
const values = [];
let curr = this.head.next;
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
};
// get the length of the list
LinkedList.prototype.length = function() {
let length = 0;
let curr = this.head.next;
while (curr !== null) {
length++;
curr = curr.next;
}
return length;
};
以上是實現單鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！
