Une introduction douce aux structures de données: comment fonctionnent les listes liées

Avez-vous déjà construit une machine Rube Goldberg? Sinon, peut-être avez-vous construit une ligne élaborée de dominos?

D'accord, peut-être que vous n'étiez pas aussi ringard que moi. Ainsi soit-il. Pour ceux d'entre vous qui ont eu le plaisir de faire l'une des choses ci-dessus, vous avez déjà saisi l'essence de la structure de données d'aujourd'hui: les listes chaînées!

Fonctionnement des listes liées

La forme la plus simple de listes liées - une liste liée individuellement - est une série de nœuds où chaque nœud individuel contient à la fois une valeur et un pointeur vers le nœud suivant dans la liste.

Les ajouts ( Ajouter ) agrandissent la liste en ajoutant des éléments à la fin de la liste.

Les suppressions ( Supprimer) seront toujours supprimées d'une position donnée dans la liste.

Search ( Contains ) recherchera dans la liste une valeur.

Exemples de cas d'utilisation:

  • Stocker des valeurs dans une table de hachage pour éviter les collisions (plus d'informations à ce sujet dans quelques articles)
  • Refaire la course incroyable!

Gardons cet article agréable et léger en travaillant sur un outil que le réseau CBS peut utiliser pour planifier sa prochaine émission télévisée de course incroyable.

Au fur et à mesure que vous passez par là, je veux que vous continuiez à vous demander: «En quoi les listes chaînées sont-elles différentes des tableaux? En quoi sont-ils similaires? »

Commençons.

Tout d'abord, vous devez créer la représentation de notre liste chaînée:

class LinkedList{ constructor(){ this._head = null; this._tail = null; this._length = 0; }
 size(){ return this._length; }}

Pour suivre le point de départ et le point d'arrivée de la course, vous créez les propriétés de tête et de queue.

Ensuite, pour vous assurer de ne pas rendre la course trop longue ou trop courte pour la saison, vous créez une propriété de longueur et une méthode de taille. De cette façon, vous pouvez toujours suivre exactement la durée de la course.

Maintenant que vous avez un moyen de stocker la liste des courses, vous devez créer un moyen d'ajouter à cette liste. La question est, qu'est-ce que vous ajoutez spécifiquement?

N'oubliez pas qu'une liste liée est une série de nœuds où chaque nœud a une valeur et un pointeur vers le nœud suivant dans la liste. Sachant cela, vous réalisez qu'un nœud n'est qu'un objet avec une valeur et une propriété suivante.

Puisque vous allez créer un nouveau nœud à chaque fois que vous ajoutez à la liste, vous décidez de créer un constructeur qui facilite la création d'un nouveau nœud pour chaque valeur ajoutée à votre liste.

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

La disponibilité de ce constructeur vous permet de créer votre méthode d'ajout.

class Node { constructor(value) { this.value = value; this.next = null; }}
class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); //we create our node if(!this._head && !this._tail){ //If it's the first node this._head = node; //1st node is head & tail this._tail = node; }else{ this._tail.next = node; //add node to the back this._tail = this._tail.next; //reset tail to last node } this._length++; } size() { return this._length; }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

Maintenant que vous avez ajouté cette méthode, vous pourrez ajouter un tas d'emplacements à votre liste Amazing Race. Voilà à quoi cela ressemblera. Notez que j'ai ajouté un espace blanc supplémentaire pour le rendre plus facile à comprendre.

{ _head: { value: 'Colombo, Sri Lanka', next: { value: 'Lagos, Nigeria', next: { value: 'Surat, India', next: { value: 'Suzhou, China', next: null } } } }, _tail: { value: 'Suzhou, China', next: null }, _length: 4 }

Bon, maintenant que vous avez créé cette liste et un moyen d'ajouter, vous vous rendez compte que vous voulez de l'aide pour ajouter des emplacements à cette liste parce que vous avez la décidophobie (oui, c'est une chose).

Vous décidez de le partager avec votre collègue, Kent, en lui demandant d'ajouter quelques adresses supplémentaires. Le seul problème est que lorsque vous le lui donnez, vous ne lui dites pas quels endroits vous avez déjà ajoutés. Malheureusement, vous avez aussi oublié après avoir souffert d'amnésie provoquée par l'anxiété de décision.

Bien sûr, il pourrait simplement exécuter console.log (AmazingRace) et lire ce que la console affiche. Mais Kent est un programmeur paresseux et a besoin d'un moyen de vérifier si quelque chose existe afin d'éviter les doublons. Dans cet esprit, vous créez une méthode contient pour vérifier les valeurs existantes.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

Génial, maintenant Kent a un moyen de vérifier les valeurs avant de les ajouter, pour éviter les doublons.

En passant, vous vous demandez peut-être pourquoi vous n'avez pas simplement utilisé la méthode contains dans la méthode add pour éviter les ajouts en double? Lorsque vous implémentez une liste liée - ou toute structure de données, d'ailleurs - vous pouvez théoriquement ajouter les fonctionnalités supplémentaires que vous souhaitez.

Vous pouvez même entrer et changer les méthodes natives sur les structures existantes. Essayez ce qui suit dans une REPL:

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

La raison pour laquelle nous ne faisons aucune de ces choses est à cause des normes convenues. Essentiellement, les développeurs s'attendent à savoir comment certaines méthodes devraient fonctionner.

Étant donné que notre classe de liste chaînée n'est pas native de JavaScript, nous avons plus de liberté pour l'implémenter, mais il existe toujours des attentes de base quant au fonctionnement des structures de données comme celles-ci. Les listes liées ne stockent pas intrinsèquement des valeurs uniques. Mais ils ont des méthodes comme contient qui nous permettent de pré-vérifier et de maintenir l'unicité de notre liste.

Kent vous répond avec sa liste de destinations, mais certaines d'entre elles sont discutables. Par exemple, le pôle Nord n'est peut-être pas la meilleure destination pour Amazing Race.

Vous décidez donc de créer une méthode pour pouvoir supprimer un nœud. Il est important de se rappeler qu'une fois que vous supprimez le nœud, vous dissociez la liste et devrez relier ce qui était avant et après le nœud supprimé.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ // see if our value exists let current = this._head; // begin at start of list let previous = this._head; while(current){ // check each node if(current.value === value){ if(this._head === current){ // if it's the head this._head = this._head.next; // reset the head this._length--; // update the length return; // break out of the loop } if(this._tail === current){ // if it's the tail node this._tail = previous; // make sure to reset it } previous.next = current.next; // unlink (see img below) this._length--; // update the length return; // break out of } previous = current; // look at the next node current = current.next; // ^^ } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

Il y a beaucoup de code dans cette fonction de suppression là-haut. Essentiellement, cela se résume à ce qui suit:

  1. si la valeur existe dans la liste…
  2. itérer sur la liste liée, en gardant une trace du nœud précédent et actuel
  3. alors, s'il y a un match →

4A. si c'est la tête

  • réinitialiser la tête au nœud suivant de la liste
  • mettre à jour la longueur
  • sortir de la boucle

4B. si c'est la queue

  • réinitialiser la queue au nœud précédent de la liste
  • dissociez le nœud en réinitialisant les pointeurs comme indiqué ci-dessous

4C. Si ce n'est pas un match → continuez à itérer

  • rendre le nœud suivant courant
  • rendre le nœud actuel précédent

One last thing to note: you may have realized that you didn’t actually delete the node. You just removed the references to it. Well, that’s OK because once all references to an object are removed, the garbage collector helps us remove it from memory. You can read up on the garbage collection here.

With the remove method now implemented, you can run this little piece of code below to make sure contestants don’t freeze to death, or accidentally bother Santa as he’s prepping for this year’s festivities.

AmazingRace.remove('North Pole');

You’ve done it! You’ve created a simple implementation of a linked list. And you can grow the list by adding items, and shrink it by removing items — all based on the item’s value.

See if you can add you can expand the linked list to allow you to insert values at the beginning, end, or any point in between.

You have all you need to implement those methods. The names and arguments for these methods should look a little like this:

addHead(value) {
}
insertAfter(target, value){
}

Feel free to share your implementations in the comments below ?

A time complexity analysis on the queue methods

Here’s the code again:

class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ let current = this._head; let previous = this._head; while(current){ if(current.value === value){ if(this._head === current){ this._head = this._head.next; this._length--; return; } if(this._tail === current){ this._tail = previous; } previous.next = current.next; this._length--; return; } previous = current; current = current.next; } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Add is O(1): Since you always know the last item in the list thanks to tail property, you don’t have to iterate over the list.

Remove is O(n): In the worst case scenario you’re going to have to iterate over the entire list to find the value to be removed. Great part though is the actual removal of the node is O(1) because you’re just resetting pointers.

Contains is O(n): You have to iterate over the entire list to check if the value exists in your list.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

Finally, Ian Elliot wrote a walk-through that helps you implementing all of the methods. But see if you can implement addHead() and insertAfter() for your linked list before peeking at this ?