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>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)
Créer un nœud
Insérer un nœud
Rechercher/Nœud de parcours
Supprimer un nœud
Fusionner
Le pointeur pointe vers null
Données de stockage
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}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;
}
} static createNode(key) {
return new createNode(key);
}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.
L'opération d'insertion nécessite uniquement d'ajuster le pointeur du nœud :
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}Il 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;
}Si vous comprenez la liste à sens unique présentée ci-dessus, alors la liste à double sens présentée ici est en fait presque la même.
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--;
}
}
Pointeur vers le nœud précédent 指向后一个节点的指针 节点数据 头指针指向NULL 看上图中head后面的第一个节点可以知道，该节点的prev指向NULL 节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点 如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛) 最后将head指向新的节点 这里和单向节点一样，就直接贴代码了 和之前单向链表一样，分三种情况去看： 删除的是第一个节点 head指向所要删除节点的下一个节点 下一个节点的prev指针指向所要删除节点的上一个节点 删除的是中间的某个节点 所要删除的前一个节点的next指向所要删除的下一个节点 所要删除的下一个节点的prev指向所要删除的前一个节点 删除的是最后一个节点 要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址） 这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。 class ListNode {
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(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;
}
}
}总结
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)
