This article brings you a detailed introduction to linked lists in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.
Linked list and array
Everyone has used arrays in js. Arrays are actually a sequential storage structure of linear tables. Its characteristic is that it uses a set of addresses. Consecutive memory cells store data elements one after another. Its shortcomings are also caused by its characteristics. For example, when deleting or inserting an array, a large number of elements may need to be moved.
Here is a rough simulation of the insertion operation of the array:
insert(arr, index, data){
for(let i = index + 1; i <p>It can be seen from the above code that the insertion and deletion of the array may be an O(n) operation. This leads to the data structure of the linked list. The linked list does not require logically adjacent elements to be adjacent in physical locations, so it does not have the shortcomings of the sequential storage structure. Of course, it also loses the randomness of the array in a continuous space. Advantages of access. </p><h3>One-way linked list</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="Detailed introduction to linked lists in JavaScript"></span></p><h4>Characteristics of one-way linked list:</h4>Use one Arrange any memory space to store data elements (the memory space here can be continuous or discontinuous)
Each node (node) consists of the data itself and a Pointers to subsequent nodes are composed of
. Access to the entire linked list must start from the head pointer, which points to the first node
The last node The pointer points to null (NULL)
Creating nodes
Insert node
Search/Traverse node
Delete node
Merge
Pointer points to null
Storage data
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}Each linked list has a head pointer, pointing to the first node, if there is no node, it points to NULL
class List {
constructor() {
this.head = null;
}
} static createNode(key) {
return new createNode(key);
}Let me explain here, I exposed a static method to create the node, rather than directly encapsulating it into the insertion operation, because I feel that such logic will be more Be more correct. Create a linked list from -> Create a node -> Insert the node into the linked list. You may encounter some articles that introduce a way to directly use a piece of data as a parameter to call the insert operation, and create a node inside the insert.
The insertion operation only needs to adjust the pointer of the node. There are two situations:
Head does not exist Points to any node, indicating that the currently inserted node is the first one
head points to the new node
The pointer of the new node points to NULL
head points to the node
head points to the new node
The pointer of the new node points to the node pointed by the original head
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}Search from head
When the key in the node is found to be equal to the key you want to find, return the node
find(key) {
let node = this.head;
while(node !== null && node.key !== key){
node = node.next;
}
return node;
}There are three parts here This situation:
The node to be deleted happens to be the first one, which is the node pointed by head
Point head to the node you want to delete Delete the next node of the node (node.next)
The node to be deleted is the last node
Find Go to the previous node (prevNode) of the node to be deleted
Point the pointer in prevNode to NULL
Delete a certain node in the middle of the list Nodes
Find the previous node (prevNode) of the node to be deleted
Point the pointer in prevNode to the current node to be deleted The next node of this node
delete(node) {
// 第一种情况
if(node === this.head){
this.head = node.next;
return;
}
// 查找所要删除节点的上一个节点
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
// 第二种情况
if(node.next === null) {
prevNode.next = null;
}
// 第三种情况
if(node.next) {
prevNode.next = node.next;
}
}class ListNode {
constructor(key) {
this.next = null;
this.key = key;
}
}
class List {
constructor() {
this.head = null;
this.length = 0;
}
static createNode(key) {
return new ListNode(key);
}
// 往头部插入数据
insert(node) {
// 如果head后面有指向的节点
if (this.head) {
node.next = this.head;
} else {
node.next = null;
}
this.head = node;
this.length++;
}
find(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
if (this.length === 0) {
throw 'node is undefined';
}
if (node === this.head) {
this.head = node.next;
this.length--;
return;
}
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
if (node.next === null) {
prevNode.next = null;
}
if (node.next) {
prevNode.next = node.next;
}
this.length--;
}
}If you put the above introduction We have already understood the one-way list, so the two-way list introduced here is actually similar.
You can clearly see the difference between a doubly linked list and a singly linked list from the above figure. The doubly linked list has an additional pointer pointing to the previous node.
Pointer to the previous node
指向后一个节点的指针
节点数据
class ListNode {
this.prev = null;
this.next = null;
this.key = key;
}头指针指向NULL
class List {
constructor(){
this.head = null;
}
} static createNode(key){
return new ListNode(key);
}看上图中head后面的第一个节点可以知道，该节点的prev指向NULL
节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点
如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)
最后将head指向新的节点
insert(node) {
node.prev = null;
node.next = this.head;
if(this.head){
this.head.prev = node;
}
this.head = node;
}这里和单向节点一样，就直接贴代码了
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}和之前单向链表一样，分三种情况去看：
删除的是第一个节点
head指向所要删除节点的下一个节点
下一个节点的prev指针指向所要删除节点的上一个节点
删除的是中间的某个节点
所要删除的前一个节点的next指向所要删除的下一个节点
所要删除的下一个节点的prev指向所要删除的前一个节点
删除的是最后一个节点
要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）
delete(node) {
const {prev,next} = node;
delete node.prev;
delete node.next;
if(node === this.head){
this.head = next;
}
if(next){
next.prev = prev;
}
if(prev){
prev.next = next;
}
} class ListNode {
constructor(key) {
// 指向前一个节点
this.prev = null;
// 指向后一个节点
this.next = null;
// 节点的数据(或者用于查找的键)
this.key = key;
}
}
/**
* 双向链表
*/
class List {
constructor() {
this.head = null;
}
static createNode(key) {
return new ListNode(key);
}
insert(node) {
node.prev = null;
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
}
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
const { prev, next } = node;
delete node.prev;
delete node.next;
if (node === this.head) {
this.head = next;
}
if (prev) {
prev.next = next;
}
if (next) {
next.prev = prev;
}
}
}这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。
The above is the detailed content of Detailed introduction to linked lists in JavaScript. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
