链表是一种由一系列元素组成的数据结构，每个元素都包含对该序列中下一个元素的引用（或“链接”）。第一个元素称为头，最后一个元素称为尾。
链表与其他数据结构相比有很多优点。现在我们来看看如何使用 JavaScript 实现链表。
定义 Node 类和 LinkedList 类
这基本上是在 JavaScript 中实现链表的先决条件。在这一步中，需要创建2个类，一个用于节点，另一个用于链表。
Node 类表示链表中的单个节点。它有两个属性：data 和 next。 data 属性用于存储节点的实际数据，而 next 属性是对列表中下一个节点的引用。 Node 类由一个构造函数组成，该构造函数在创建新 Node 时初始化数据和 next 属性。
立即学习“Java免费学习笔记（深入）”；
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 中添加或删除数据。
