考虑数据结构，让我们仔细研究链接列表。
链接列表是最受欢迎，最有效的数据结构之一。基本上，链接列表是“节点”的集合，每个节点都包含 data ， next 和上一个，基本上是 next 涉及下一个节点，上一个是指以前的节点。
我们可以说，数组和链接列表相似。但是在数组中，元素存储在特定位置或索引中。
另一方面，在链接列表中，所有内容都可以用作单独的对象。每个元素（节点）包含一些内容，数据，链接到下一个节点，链接到上一个节点。
链接列表的类型：
链接列表有三种类型，
1。单链接列表：每个节点都包含数据和指向下一个节点的指针。基本上是单向。
分析上述图像，它以 head 开始，因此 head 是入口点。如果链接列表为空，则 head 将为null。因此， head 引用第一个节点， last 节点指向null。
const linkedList = {
head: {
value: 5
next: {
value: 7
next: {
value: 2
next: {
value: 15
next: null
}
}
}
}
}
};
基本示例，
// class of node
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
/* LindedList class. remember, if the head node is not passed then head will be null */
class LinkedList {
constructor(head = null) {
this.head = head
}
}
/* lets create some nodes */
let node1 = new ListNode(5) // data will be 5
let node2 = new ListNode(7) // data will be 7
let node3 = new ListNode(2) // data will be 2
let node4 = new ListNode(15) // data will be 15
node1.next = node2 // points to the node2
node2.next = node3 // points to the node2
node3.next = node4
let list = new LinkedList(node1) // Linked List completed
的优势和单独链接列表的用途
- 动态数据结构：内存动态分配给链接列表。我们可以很容易地添加或删除元素。我们不需要考虑初始尺寸。
- 实现：在这里可以轻松实现其他数据结构，例如队列和堆栈。
- 多功能性：衬里列表可用于实现广泛的数据结构，例如堆栈，队列，图形，图形，真实和具有表。
单独链接列表的缺点
- 纪念用法：我们需要存储下一个数据的地址，因此需要更多的内存。
- 访问元素：无法直接访问任何元素。如果我们需要找到n个值，那么我们需要穿越直到找到nth元素。
- 反向遍历：单独链接的列表不可能。因为我们没有上一个指针的内存地址。
- 更复杂的实现：与数组相似，其实现非常复杂。我们需要了解动态内存位置和指针操作。
- 缺乏缓存局部性：它可能无法利用现代处理器中的缓存机制。其性能较慢。
2。双重链接列表：每个节点包含两个指针一个用于下一个节点，一个用于以前的节点。
在上图中，我们了解，
- prev：指的是先前的节点
- 数据：数据项
- 下一个：下一个节点的地址
下图显示了我们的表示链接列表的表示形式，此处每个节点都包含 next _和_prev to point 下一个节点和 prev node
基本示例
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}
class DoublyLinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
previous: null
};
this.length = 0;
this.tail = this.head;
}
// Insert node at end of the list
add(newNode) {
this.tail.next = newNode;
newNode.previous = this.tail;
this.tail = newNode;
this.length++;
}
printList() {
let current = this.head;
let result = [];
while (current !== null) {
result.push(current.value);
current = current.next;
}
console.log(result.join(' '));
return this;
}
}
let numList = new DoublyLinkedList();
numList.add(new ListNode (12));
numList.add(new ListNode (13));
numList.add(new ListNode (14));
numList.add(new ListNode (15));
numList.add(new ListNode (16));
numList.add(new ListNode (17));
numList.printList();
console.log(numList)
console.log(numList.head)
双重链接列表的优势：
- 反向：反向双重链接列表非常容易。
- traversal：此双重链接列表的遍历是双向的，在单链接列表中是不可能的。
- 删除：与单链接列表相比，节点的删除很容易。
双重链接列表的缺点：
- 与数组和单链接列表相比，它使用额外的内存。
- 遍历双重链接列表的范围比遍历单个链接列表
- 实现和维护双链接列表可能比单链接列表更复杂。
使用双重链接列表的使用：
- 导航系统：它用于需要前后导航的导航系统中。
- 撤消和重做：它也被各种应用程序使用来实现撤消和重做功能。
-mru/lru：双链接列表也用于构建MRU/LRU（最/最不最近使用的）缓存。
- 线程调度程序：在许多操作系统中，线程调度程序（选择在此时需要运行的过程）保持当时运行的所有过程的双关联列表。<
- 浏览器：下一页和上一页。
- 图像查看器：接下来和上一个图像
- 实施**图**算法
3。循环链接列表：它与其他链接列表不同，其最后一个节点指向第一个或任何其他节点。
它有两种类型，
- 圆形单链接列表
- 圆形双链接列表
我们将在下一个中学习循环链接列表。就是这样。见Yaaa。