数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 中的链表类型
在本文中，我们将讨论 JavaScript 中各种类型的链表。链表是一种顺序数据结构，可以动态存储数据。由于这种数据结构没有索引，因此可以根据需要添加和删除数据。这将减少内存存储的浪费。
有各种类型的链表。它们如下所示：
- 简单链表 - 项目导航仅向前。
- 双向链表 - 项目可以向前和向后导航。
- 循环链表 - 最后一个项目包含下一个第一个元素的链接，而第一个元素具有上一个最后一个元素的链接。
简单链表
示例 1
以下示例显示了如何创建简单链表。我们创建一个 Node 类，其中包含两个局部变量：data 和 next。每当调用此类时，构造函数都会将 data 值分配给 data 变量，并将其链接到列表中已存在的先前节点。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Linked List Data Structure</title>
</head>
<body>
<script type="text/javascript">
class Node {
constructor(data) {
this.element = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
add(element) {
let node = new Node(element);
let temp;
if (this.head == null) this.head = node;
else {
temp = this.head;
while (temp.next) {
temp = temp.next;
}
temp.next = node;
}
this.size++;
}
insertAt(element, index) {
if (index < 0 || index > this.size)
return document.write("Enter a valid index.");
else {
let node = new Node(element);
let curr, prev;
curr = this.head;
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
let it = 0;
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
node.next = curr;
prev.next = node;
}
this.size++;
}
}
removeFrom(index) {
if (index < 0 || index >= this.size)
return document.write("Enter a valid index");
else {
let curr,
prev,
it = 0;
curr = this.head;
prev = curr;
if (index === 0) {
this.head = curr.next;
} else {
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
}
this.size--;
return curr.element;
}
}
removeElement(element) {
let curr = this.head;
let prev = null;
while (curr != null) {
if (curr.element === element) {
if (prev == null) {
this.head = curr.next;
} else {
prev.next = curr.next;
}
this.size--;
return curr.element;
}
prev = curr;
curr = curr.next;
}
return -1;
}
indexOf(element) {
let count = 0;
let temp = this.head;
while (temp != null) {
if (temp.element === element) {
document.write("</br>The Element is found at the index : ");
return count;
}
count++;
temp = temp.next;
}
return -1;
}
isEmpty() {
return this.size == 0;
}
size_of_list() {
document.write("</br>The size of the Linked List is : " + this.size);
}
displayList() {
let curr = this.head;
let str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
document.write("The Elements in the Linked List are: " + str);
}
}
let ll = new LinkedList();
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
ll.displayList();
ll.size_of_list();
document.write(ll.indexOf(40));
</script>
</body>
</html>
双向链表
双向链表是一种链表类型，它以两种方式链接其中的节点。简单来说，双向链表中的节点与其上一个节点和下一个节点相连。因此，项目可以向前和向后导航。
示例 2
以下示例显示了如何创建双向链表并使用 JavaScript 执行其操作。我们首先创建一个包含三个部分的 Node 类：previous、value 和 next。每次调用此类时，都会在列表中建立一个新节点。然后，我们执行各种链表操作，如插入、删除、检查状态和显示。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Doubly Linked List Data Structure</title>
</head>
<body>
<script type="text/javascript">
function createNode(value) {
return {
value: value,
next: null,
previous: null,
};
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
insert(value) {
this.size++;
let newNode = createNode(value);
if (this.tail) {
this.tail.next = newNode;
newNode.previous = this.tail;
this.tail = newNode;
return newNode;
}
this.head = this.tail = newNode;
return newNode;
}
remove() {
if (this.tail) {
this.size--;
let removedTail = this.tail;
let beforeTail = this.tail.previous;
this.tail = beforeTail;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
return removedTail;
}
return undefined;
}
print() {
document.write("The Elements in the Doubly Linked List are :</br> ");
let current = this.head;
while (current) {
document.write(
`${current.previous?.value} ${current.value} ${current.next?.value}`
);
current = current.next;
}
}
insertHead(value) {
this.size++;
let newNode = createNode(value);
if (this.head) {
this.head.previous = newNode;
newNode.next = this.head;
this.head = newNode;
return newNode;
}
this.head = this.tail = newNode;
return newNode;
}
insertIndex(value, index) {
if (index >= this.size) {
throw new Error("Insert index out of bounds");
}
if (index === 0) {
return this.insertHead(value);
}
this.size++;
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
let previousNode = currentNode.previous;
let newNode = createNode(value);
newNode.next = currentNode;
newNode.previous = previousNode;
previousNode.next = newNode;
currentNode.previous = newNode;
return newNode;
}
}
let dLinkedList = new DoublyLinkedList();
dLinkedList.insert(7);
dLinkedList.insert(8);
dLinkedList.insert(9);
dLinkedList.print();
</script>
</body>
</html>
循环链表
循环链表可以创建为单向（简单）链表或双向链表。
如果是简单链表，则第一个元素的地址将存储在最后一个节点的 next 部分中，但如果是双向链表，则最后一个项目包含一个指向第一个元素的 next 链接，而第一个元素包含一个指向最后一个元素的 prev 链接。
更新于：2022-12-16
1K+ 次查看
广告