Compréhension approfondie de la structure des données dans JS (Linked-list)

Recommandations associées : "Tutoriel vidéo javascript"

Pour les débutants en JS, comprendre les listes chaînées peut être une tâche difficile car JS n'a pas d'intégration une liste chaînée est fournie. Dans un langage de haut niveau comme JS, nous devons implémenter cette structure de données à partir de zéro, et si vous n'êtes pas familier avec le fonctionnement de cette structure de données, la partie implémentation devient plus difficile ?.

Dans cet article, nous verrons comment stocker des listes chaînées dans une base de données, mettre en œuvre des opérations telles que l'ajout et la suppression de listes chaînées, la recherche et l'inversion de listes chaînées. Avant d'implémenter une liste chaînée, vous devez connaître quels sont les avantages d'une liste chaînée par rapport aux tableaux et aux objets.

Nous savons que les éléments du tableau sont stockés dans la base de données par numéro d'index et dans l'ordre :

Lors de l'utilisation d'un tableau , dans Des opérations telles que l'ajout/suppression d'un élément depuis le début ou à un index spécifique peuvent être une tâche moins performante car nous devons déplacer l'index de tous les autres éléments. La raison en est la nature de l'indexation numérotée des tableaux.

L'utilisation d'objets peut résoudre les problèmes ci-dessus. Puisque l'emplacement de stockage de l'élément est aléatoire dans un objet, il n'est pas nécessaire de déplacer l'index de l'élément lors de l'exécution d'opérations comme l'ajout/suppression d'un élément au début ou à un index spécifique :

Bien que l'ajout et la suppression d'éléments dans des objets soient rapides, comme vous pouvez le voir sur la figure ci-dessus, les objets ne sont pas le meilleur choix lors des opérations itératives. les objets sont stockés dans des emplacements aléatoires. Les opérations itératives peuvent donc prendre beaucoup de temps. C'est la raison pour laquelle la liste chaînée est introduite.

Alors, qu'est-ce qu'une liste chaînée ?

Comme vous pouvez le constater d'après le nom lui-même, il s'agit en quelque sorte d'une liste chaînée. Alors, comment est-il lié et que contient la liste ?

Une liste chaînée est composée de nœuds avec deux attributs : data et pointeur . Le pointeur à l'intérieur du nœud

pointe vers le nœud suivant dans la liste. Le premier nœud de la liste chaînée s'appelle head. Pour une meilleure compréhension, jetons un œil au schéma décrivant la liste chaînée :

Comme vous pouvez le voir sur la figure ci-dessus, chaque nœud a deux Attributs, data et pointer. Le pointeur pointe vers le nœud suivant de la liste et le pointeur du dernier nœud pointe vers null L'image ci-dessus est une liste à chaînage unique ?.

Il y a une grande différence entre les listes chaînées et les objets. Dans une liste chaînée, chaque nœud est connecté au nœud suivant via un pointeur . Ainsi, nous avons une connexion entre chaque nœud de la liste chaînée, alors que dans un objet, les paires clé-valeur sont stockées de manière aléatoire sans connexion entre elles.

Ensuite, nous implémentons une liste chaînée pour stocker des entiers. Étant donné que JS ne fournit pas de support intégré pour les listes chaînées, nous utiliserons des objets et des classes pour implémenter des listes chaînées ?

class Node {
  constructor (value) {
    this.value = value
    this.next = null
  }
}

class LinkedList {
  constructor () {
    this.head = null
    this.tail = this.head
    this.length = 0
  }
  append (value) {
  }

  prepend (value) {

  }

  insert (value, index) {

  }

  lookup (index) {

  }

  remove (index) {

  }

  reverse () {
    
  }
}

Dans le code ci-dessus, nous avons créé deux classes, une pour

liste chaînée lui-même, l'un est le nœud lui-même. Comme nous en avons discuté, chaque nœud aura deux propriétés, un et un 值 (correspondant au champ 指针). La classe next

LinkedList contient trois attributs, (la valeur initiale est head), null (qui pointe également vers tail) qui est utilisé pour stocker le dernier nœud de la liste chaînée. Et l'attribut null utilisé pour enregistrer la longueur de la liste chaînée. Ensuite, implémentons la méthode à l’intérieur ?. length

append (ajouter les valeurs dans l'ordre)

Cette fonction ajoute un nœud à la fin de la liste chaînée. Afin de mettre en œuvre cette fonction, nous devons comprendre certaines des opérations qu'elle doit effectuer :

À partir de la figure ci-dessus, nous pouvons y parvenir de la manière suivante

Fonction : append

  append (value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
  }

Expliquez brièvement la méthode

? : append

const linkedList1 = new LinkedList()
linkedList1.append(2)

vérifie si

pointe vers head À ce moment, null. pointe vers head, nous créons donc un nouvel objet et attribuons le nouvel objet à null et head :tail

let node = new Node(2)
this.head = newNode
this.tail = newNode

Maintenant,

et head pointent vers le même objet, ce qui est important de se rappeler. tail

Ensuite, nous ajoutons deux valeurs supplémentaires à la liste chaînée :

linkedList1.append(3)
linkedList1.append(4)

Maintenant,

ne pointe pas vers head, nous entrons donc dans la branche null du append fonction : else

this.tail.next = node

由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是JS 中对象的工作方式。在JavaScript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于

this.head.next = node;

下一行：

this.tail = node

现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。

执行三次append之后，linkedList1 的结构应该是这样的：

head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3

从上面的代码中我们可以看到，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。

我们来看下一个函数 ?

prepend (将值添加到链表的开头)

为了实现此函数，我们使用Node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。 接下来，我们将新节点分配给链表的head：

与append函数一样，这个函数的复杂度也是O(1)。

  prepend (value) {
  const node = new Node(value)

  node.next = this.head
  this.head = node
  this.length++
}

就像append函数一样，此函数的复杂度也为O(1)。

insert (在特定索引处添加值)

在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。 insert 函数接受两个参数，值和索引:

let linkedList2 = new LinkedList()
linkedList2.append(23)
linkedList2.append(89)
linkedList2.append(12)
linkedList2.append(3)

linkedList2.insert(45,2)

第1步：

遍历链表，直到到达index-1位置:

第2步：

将索引为1的节点的指针（在本例中为89）分配给新节点（在本例中为45）：

第3步：

将新节点(45)的 next 指向给下一个节点(12)

这就是执行插入操作的方式。 通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。 在代码中实现：

insert (value, index) {
  if (index >= this.length) {
  this.append(value)
}

  const node = new Node(value)

  const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
  prevNode.next = node
  node.next = nextNode

  this.length++
}

简单分析一下上面的函数：

如果index的值大于或等于length属性，则将操作移交给append函数。 对于 else 分支，我们使用 Node 类创建一个新节点，接下来观察一个新函数getPrevNextNodes() ，通过该函数我们可以接收prevNode和nextNode的值。 getPrevNextNodes函数的实现如下：

 getPrevNextNodes(index){
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while(count < index - 1){
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

通过遍历链表返回在index-1位置和index位置的节点，并将prevNode的next属性指向新节点，并将新节点的next属性指向nextNode。

链表的插入操作的复杂度为 O(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。 尽管复杂度为O(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。

remove (删除特定索引处的元素)

实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getPrevNextNodes函数获取prevNode和nextNode值时，我们必须在remove中执行以下操作：

remove(index){
  let {previousNode,currentNode} = this.getNodes(index)
  previousNode.next = currentNode.next
  this.length--
}

删除操作的复杂度也为 O(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。

reverse (反转链表)

虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。

为了反转链表，我们需要跟踪三个节点，previousNode，currentNode和nextNode。

考虑下面的链表:

let linkedList2 = new LinkedList()
linkedList2.append(67)
linkedList2.append(32)
linkedList2.append(44)

第一步：

开始，previousNode的值为null，而currentNode的值为head：

第二步：

接下来，我们将nextNode分配给currentNode.next：

第三步：

接下来，我们将currentNode.next属性指向previousNode：

第三步：

现在，我们将previousNode移至currentNode，将currentNode移至nextNode：

这个过程从步骤2重复操作，一直到currentNode 等于 null。

reverse (){
  let previousNode = null
  let currentNode = this.head

  while(currentNode !== null) {
    let nextNode = currentNode.next
    currentNode.next = previousNode
    previousNode = currentNode
    currentNode = nextNode
  }

  this.head = previousNode
}

就像我们看到的一样，直到currentNode === null，我们一直在遍历和移动这些值。 最后，我们将previousNode值分配给head。

反向运算的复杂度为O(n)。

查找 (查找特定索引的值)

这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是O(n)。

lookup(index){
    let counter = 0;
    let currentNode = this.head;
    while(counter < index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }

好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。

总结

链表为我们提供了快速的append（末尾添加元素）和prepend（开头添加元素）操作。 尽管链表中的插入操作的复杂度为O(n)，但比数组的插入操作要快得多。 使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。

在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。

原文地址：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/

作者：Vivek Bisht 

译文地址：https://segmentfault.com/a/1190000024565634

更多编程相关知识，请访问：编程教学！！

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!