Cet article vous apporte une introduction détaillée aux listes chaînées en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.
Listes et tableaux chaînés
Tout le monde a utilisé des tableaux en js. Les tableaux sont en fait une structure de stockage séquentielle de tables linéaires. Sa caractéristique est qu'il utilise un ensemble d'adresses. . Les cellules mémoire consécutives stockent les éléments de données les uns après les autres. Ses inconvénients sont également dus à ses caractéristiques. Par exemple, lors de la suppression ou de l'insertion d'un tableau, un grand nombre d'éléments peuvent devoir être déplacés.
Voici une simulation approximative de l'opération d'insertion du tableau :
insert(arr, index, data){
for(let i = index + 1; i <p>À partir du code ci-dessus, nous pouvons voir que l'insertion et la suppression du tableau peuvent être un O(n ) opération. Cela conduit à la structure de données de la liste chaînée. La liste chaînée ne nécessite pas que les éléments logiquement adjacents soient adjacents dans des emplacements physiques, elle n'a donc pas les inconvénients de la structure de stockage séquentielle. Bien sûr, elle perd également le caractère aléatoire de la liste chaînée. tableau dans un espace continu. Avantages de l'accès. </p><h3>Liste chaînée unidirectionnelle</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="Introduction détaillée aux listes chaînées en JavaScript"></span></p><h4>Caractéristiques de la liste chaînée unidirectionnelle : </h4>Copier après la connexion
Utilisez-en un Organisez n'importe quel espace mémoire pour stocker des éléments de données (l'espace mémoire ici peut être continu ou discontinu)
Chaque nœud (nœud) se compose des données elles-mêmes et d'un pointeur vers les suivants les nœuds sont composés de
L'accès à l'intégralité de la liste chaînée doit commencer à partir du pointeur de tête, qui pointe vers le premier nœud
le dernier nœud Le pointeur pointe vers null (NULL)
Plusieurs opérations principales dans la liste chaînée
Initialiser le nœud
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}Copier après la connexion
Initialiser la liste chaînée unidirectionnelle
Chaque liste chaînée a un pointeur de tête, pointant vers le premier nœud, s'il n'y a pas de nœud, il pointe vers NULL
class List {
constructor() {
this.head = null;
}
}Copier après la connexion
Créer un nœud
static createNode(key) {
return new createNode(key);
}Copier après la connexion
Laissez-moi vous expliquer ici, j'ai exposé une méthode statique pour créer le nœud, au lieu de l'encapsuler directement dans l'opération d'insertion, parce que j'ai l'impression que cette logique serait plus correcte. Créez une liste chaînée à partir de -> Créer un nœud -> Insérez le nœud dans la liste chaînée. Vous pouvez rencontrer des articles qui présentent un moyen d'utiliser directement un élément de données comme paramètre pour appeler l'opération d'insertion et de créer un nœud à l'intérieur de l'insertion.
Insérer un nœud (après insertion dans le nœud principal)
L'opération d'insertion nécessite uniquement d'ajuster le pointeur du nœud :
- <.>head n'existe pas Pointe vers un nœud, indiquant que le nœud actuellement inséré est le premier
- head pointe vers le nœud
- la tête pointe vers le nouveau nœud
Le pointeur du nouveau nœud pointe vers le nœud pointé par la tête d'origine
- Rechercher le nœud
- Lancer la recherche depuis la tête
Lorsque la clé dans le nœud est trouvée pour être égal à la clé que vous souhaitez trouver, renvoyer le nœud
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}Copier après la connexion
Supprimer le nœudIl y a trois situations ici :
Le nœud à supprimer se trouve être le premier, qui est le nœud pointé par head
find(key) {
let node = this.head;
while(node !== null && node.key !== key){
node = node.next;
}
return node;
}Copier après la connexion
Pointez head vers le nœud suivant (node.next) du nœud à supprimer
- Le nœud à supprimer est le dernier nœud
- Rechercher le nœud précédent ( prevNode) du nœud à supprimer
Pointez le pointeur dans prevNode sur NULL Supprimez un nœud au milieu du list- Trouver le nœud précédent (prevNode) du nœud à supprimer
Changer le pointeur dans prevNode Points vers le suivant nœud du nœud actuellement à supprimer
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;
}
}Copier après la connexion
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--;
}
}Copier après la connexion
À partir de l'image ci-dessus, vous pouvez clairement voir la différence entre une liste doublement chaînée et une liste simplement chaînée . La liste doublement chaînée comporte un pointeur supplémentaire pointant vers le nœud précédent.
Initialiser le nœud
Pointeur vers le nœud précédent指向后一个节点的指针
节点数据
class ListNode {
this.prev = null;
this.next = null;
this.key = key;
}Copier après la connexion
初始化双向链表
class List {
constructor(){
this.head = null;
}
}Copier après la connexion
创建节点
static createNode(key){
return new ListNode(key);
}Copier après la connexion
插入节点（（插入到头节点之后）
看上图中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;
}Copier après la connexion
搜索节点
这里和单向节点一样，就直接贴代码了
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}Copier après la connexion
删除节点
和之前单向链表一样，分三种情况去看：
删除的是第一个节点
删除的是中间的某个节点
删除的是最后一个节点
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;
}
}Copier après la connexion
双向链表整体代码
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;
}
}
}Copier après la connexion
总结
这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
