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>Copy after login
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)
Several main operations in the linked list
Creating nodes
Insert node
Search/Traverse node
Delete node
-
Merge
Initialize node
Pointer points to null
Storage data
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}Copy after login
Initialize one-way linked list
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;
}
}Copy after login
Create Node
static createNode(key) {
return new createNode(key);
}Copy after login
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.
Insert node (after inserting into the head node)
The insertion operation only needs to adjust the pointer of the node. There are two situations:
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}Copy after login
Search for the node
find(key) {
let node = this.head;
while(node !== null && node.key !== key){
node = node.next;
}
return node;
}Copy after login
Delete the 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
The node to be deleted is the last node
Delete a certain node in the middle of the list Nodes
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;
}
}Copy after login
The overall code of the one-way linked list
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--;
}
}Copy after login
Doubly linked list
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.
Initialize node
class ListNode {
this.prev = null;
this.next = null;
this.key = key;
}Copy after login
初始化双向链表
class List {
constructor(){
this.head = null;
}
}Copy after login
创建节点
static createNode(key){
return new ListNode(key);
}Copy after login
插入节点（（插入到头节点之后）
看上图中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;
}Copy after login
搜索节点
这里和单向节点一样，就直接贴代码了
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}Copy after login
删除节点
和之前单向链表一样，分三种情况去看：
删除的是第一个节点
删除的是中间的某个节点
删除的是最后一个节点
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;
}
}Copy after login
双向链表整体代码
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;
}
}
}Copy after login
总结
这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个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)
