資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學JavaScript 中的連結串列實現
連結串列是一種資料結構，它由一系列元素組成，每個元素都包含對序列中下一個元素的引用（或“連結”）。第一個元素稱為表頭，最後一個元素稱為表尾。
連結串列比其他資料結構有很多優點。現在我們將看看如何使用 JavaScript 實現連結串列。
定義節點類和連結串列類
這是在 JavaScript 中實現連結串列的基本前提。在此步驟中，需要建立兩個類，一個用於節點，另一個用於連結串列。
Node 類表示連結串列中的單個節點。它有兩個屬性：data 和 next。data 屬性用於儲存節點的實際資料，而 next 屬性是對列表中下一個節點的引用。Node 類包含一個建構函式，在建立新節點時初始化 data 和 next 屬性。
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
LinkedList 類表示連結串列本身。它有一個 head 屬性，引用列表中的第一個節點。LinkedList 類還包含一個建構函式，在建立新 LinkedList 時初始化 head 屬性。
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
LinkedList 類還包含一個方法，允許您插入、刪除和搜尋列表中的節點，同時允許其他操作，如列印列表、計數元素、反轉列表等等。
列印連結串列
您可以透過遍歷列表並列印每個節點的資料來列印連結串列的元素。
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
向連結串列新增節點
根據需要插入新節點的位置，有多種方法可以向連結串列新增資料，如下所示：
向連結串列的開頭新增節點
要向連結串列的開頭新增節點/元素，一旦建立了包含資料的節點，只需將其 next 屬性設定為列表的當前表頭。然後，您可以將列表的表頭更新為新節點。這也被稱為在連結串列的表頭插入，是最基本的資料新增型別。只需呼叫下面定義的 add 函式即可完成。
add(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
向連結串列的末尾新增節點
要向連結串列的末尾新增節點/元素，我們需要遍歷列表並找到最後一個節點。之後，建立一個包含資料的新節點，並將最後一個節點的 next 屬性設定為新節點。這也被稱為在連結串列的尾部插入，是第二種最基本的資料新增型別。只需呼叫下面定義的 addToTail 函式即可完成。
addToTail(data) {
let newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
在特定位置新增節點
要向連結串列的特定位置新增節點/元素，您可以遍歷列表以查詢插入點之前的節點，建立一個包含資料的新節點，將新節點的 next 屬性設定為當前位置的節點，並將前一個節點的 next 屬性設定為新節點。
addAtPosition(data, position) {
let newNode = new Node(data);
if (position === 1) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
let i = 1;
while (i < position - 1 && current) {
current = current.next;
i++;
}
if (current) {
newNode.next = current.next;
current.next = newNode;
}
}
示例（向連結串列新增節點）
在下面的示例中，我們實現了在開頭、結尾和特定位置新增節點。
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// function to add data to linked list
add(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
//function to add data to tail
addToTail(data) {
let newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
// function to insert data to linked list at a particular index
addAtPosition(data, position) {
let newNode = new Node(data);
if (position === 1) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
let i = 1;
while (i < position - 1 && current) {
current = current.next;
i++;
}
if (current) {
newNode.next = current.next;
current.next = newNode;
}
}
// this function is used to iterate over the entire linkedlist and print
it
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("
List after adding nodex at position 2");
list.addAtPosition("nodex",2);
list.printAll();
console.log("
List after adding nodey to tail");
list.addToTail("nodey");
list.printAll();
輸出
Initial List: node1 node2 node3 node4 List after adding nodex at position 2 node1 nodex node2 node3 node4 List after adding nodey to tail node1 nodex node2 node3 node4 nodey
刪除節點
資料的刪除也可以透過多種方法完成，具體取決於需求。
刪除特定節點
要從連結串列中刪除特定節點，我們需要遍歷列表並找到要刪除節點之前的節點，更新其 next 屬性以跳過要刪除的節點，並更新對下一個節點的引用。這根據值刪除節點。
remove(data) {
if (!this.head) {
return null;
}
if (this.head.data === data) {
this.head = this.head.next;
this.length--;
return this;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
this.length--;
return this;
}
current = current.next;
}
return null;
}
刪除特定位置的節點
要從連結串列中刪除特定位置的節點，我們需要遍歷列表並找到要刪除節點之前的節點，更新其 next 屬性以跳過要刪除的節點，並更新對下一個節點的引用。這基本上是根據節點的索引值刪除節點。
removeAt(index) {
if (index < 0 || index >= this.length) return null;
if (index === 0) return this.remove();
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
this.length--;
return this;
}
示例（從連結串列中刪除節點）
在下面的示例中，我們實現了刪除特定節點和特定位置節點。
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// function to add data to linked list
add(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
}
else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
// function to remove data from linked list
remove(data) {
if (!this.head) {
return null;
}
if (this.head.data === data) {
this.head = this.head.next;
this.length--;
return this;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
this.length--;
return this;
}
current = current.next;
}
return null;
}
// function to remove from a particular index
removeAt(index) {
if (index < 0 || index >= this.length) return null;
if (index === 0) return this.remove();
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
this.length--;
return this;
}
// this function is used to iterate over the entire linkedlist and print it
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("
List after removing node2");
list.remove("node2");
list.printAll();
console.log("
List after removing node at index 2");
list.removeAt(2);
list.printAll();
輸出
Initial List: node1 node2 node3 node4 List after removing node2 node1 node3 node4 List after removing node at index 2 node1 node3
結論
在 JavaScript 中實現連結串列涉及建立 Node 類來表示列表中的每個節點以及 LinkedList 類來表示列表本身，並向 LinkedList 類新增方法以執行新增和刪除資料以及列印列表等操作。務必考慮邊緣情況並在實現中相應地處理它們。根據用例，有多種方法可以向 LinkedList 新增或刪除資料。
更新於：2023年3月10日
7K+ 瀏覽量
廣告