Structures de données JavaScript: listes liées

Les listes liées sont l'une des structures de données les plus importantes que vous puissiez apprendre.

Dans une liste liée, chaque élément contient une référence à l'élément qui le suit.

On peut partir du début de la liste, lehead, et parcourez tous les éléments de la liste, jusqu'à ce que nous atteignions la fin (letail).

Par rapport à un tableau, les éléments ne sont pas placés les uns à côté des autres dans la mémoire réelle (dans les langages de programmation de bas niveau) ou n'ont pas d'index que nous pouvons utiliser pour accéder de manière aléatoire à un élément du tableau.

Nous ne pouvons pas référencer un élément au milieu de la liste, sans partir du début, car nous ne savons pas comment le référencer.

JavaScript n'a pas d'implémentation de listes liées, nous allons donc en créer une maintenant.

Nous créons d'abord leItemclasse qui sera la contenue pour chaque élément de la liste:

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

Nous avons un pointeur vers l'élément suivant dans la liste et la valeur.

Ensuite, nous avons défini unLinkedListclasse qui hébergera 2 valeurs privées:headettail.

Nous définissons unappend()méthode pour ajouter un élément à la liste. S'il s'agit du premier élément que nous ajoutons, l'élément est à la fois la tête et la fin de la liste. Sinon, nous créons l'article et nous l'attribuons aunextpropriété de l'article de queue:

class LinkedList {
  #head = null
  #tail = null
  append = (value) => {
    const item = new Item(value)
    if (!this.#head) {
      this.#head = item
      this.#tail = item
      return
    }
    this.#tail.next = item
    this.#tail = item
  }
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}

Voici comment nous pouvons l'utiliser:

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)

Nous pouvons ajouter unsize()méthode pour renvoyer la taille de la liste:

class LinkedList {
  //...
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}
const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

Comment trouver un élément dans la liste, par valeur? Implémentons une méthode pour ce faire:

class LinkedList {
  //...
  find = (value) => {
    let count = 1
    let item = this.#head
    if (!item) return null
    while ((item = item.next)) {
      if (item.value === value) {
        return item
      }
    }
    return null
  }
}

const list = new LinkedList() list.append(1) list.append(2) list.append(3) const item = list.find(2) //item.value === 2

Que faire si nous voulons insérer un élément dans la liste liée? Nous avons déjàappend()pour insérer l'élément à la fin de la liste. Implémentons un moyen d'insérer l'élément à une position spécifique:

class LinkedList {
  //...
  insert = (index, value) => {
    //check for out-of-bounds values
    if (index < 0 || index > this.size()) return
<span style="color:#66d9ef">const</span> <span style="color:#a6e22e">node</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#a6e22e">Item</span>(<span style="color:#a6e22e">value</span>)
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">current</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">this</span>.<span style="color:#960050;background-color:#1e0010">#</span><span style="color:#a6e22e">head</span>
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">previous</span>

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">index</span> <span style="color:#f92672">===</span> <span style="color:#ae81ff">0</span>) {
  <span style="color:#75715e">//first position

node.next = current this.#head = node } else { let i = 0 while (i++ < index) { previous = current current = current.next } node.next = current previous.next = node } } }

const list = new LinkedList() list.append(1) list.append(2) list.append(3) list.insert(2, ‘a’) list.size() //4

Un autre type de liste liée est la double liste liée, où chaque élément contient également un lien vers l'élément précédent.

Téléchargez mon gratuitManuel du débutant JavaScript


Plus de tutoriels js: