Implémentation de listes liées en JavaScript

Une liste chaînée est une structure de données très similaire à un tableau, à l'exception du fait que les données ne sont pas stockées dans un seul emplacement de mémoire. En JavaScript, chaque élément (nœud) d'une liste chaînée est un objet qui pointe vers l'élément suivant (nœud) qui pointe également vers l'élément suivant de la liste chaînée, jusqu'à ce que le dernier élément ne pointe vers rien (fin de la liste chaînée) .

Le point d'entrée d'une liste chaînée est appelé la tête. L'en-tête est une référence au premier nœud de la liste chaînée. Le dernier nœud de la liste pointe vers null. Si une liste est vide, la tête est une référence nulle.

En images, sa meilleure visualisation des listes liées comme suit ;

Cela peut également être considéré comme;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Lecteur de musique — Les chansons du lecteur de musique sont liées aux chansons précédentes et suivantes. Ainsi, vous pouvez jouer des chansons à partir du début ou de la fin de la liste.
2. Visionneuse d'images — Les images précédentes et suivantes sont liées et sont accessibles par les boutons suivant et précédent.
3. Page précédente et suivante dans un navigateur Web - Nous pouvons accéder à l'URL précédente et suivante recherchée dans un navigateur Web en appuyant sur les boutons Précédent et Suivant car ils sont liés en tant que liste liée.

Il existe trois principaux types de listes liées, à savoir la liste liée simple, la liste doublement liée et la liste liée circulaire. Aux fins de cet apprentissage, nous mettrons en œuvre la liste liée singulièrement.

Comme indiqué précédemment, une liste chaînée est simplement une combinaison d'éléments (nœuds) qui pointent les uns vers les autres. L'unité de base d'une liste chaînée est un nœud. Un nœud abrite les données et le pointeur vers le nœud suivant, implémenté comme suit ;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

La suppression d'un nœud d'une liste chaînée est implémentée en supprimant son pointeur. Cela signifie que le nœud précédent pointant vers le nœud (à supprimer) serait amené à ignorer le nœud (à supprimer), pointant ainsi vers le nœud suivant.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

J'espère que cela vous a aidé à comprendre la liste liée et sa mise en œuvre.

Juste au cas où vous voudriez plus d'explications, vous pouvez me contacter sur LinkedIn :https://www.linkedin.com/in/joshua-ajagbe/ou écrivez-moi à [email protected].

Bon Apprentissage