数据结构
网络
关系数据库管理系统 (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+ 浏览量
广告