Implémentation d'une liste à lien unique

Suppose une compréhension de la notation Big O. Les exemples sont en JavaScript. Références d'informations "Cracking the Coding Interview" par Gayle Laakmann McDowell

Comprendre les listes à lien unique

Uneliste chaînéeest une structure de données qui représente une séquence denœuds.Dans uneliste chaînée unique,chaque nœud pointe vers le nœud suivant.

En mémoire, ces nœuds n'ont pas besoin d'être triés de manière contiguë (adjacents les uns aux autres) puisque nous ne nous appuyons pas sur l'indexation. Lorsque nous parcourons une liste chaînée, nous passons par chaqueréférenced'un nœud jusqu'à ce que nous atteignions un pointeurnull.

Structure d'un nœud

Dans une liste à chaînage unique, chaque nœud contient généralement deux champs :

• données: la valeur ou les informations contenues dans le nœud
• next: la référence (pointeur) vers le nœud suivant dans la liste

Pointeurs de tête et de queue

Latêteest uneréférenceau premier nœud de la liste. Il est indispensable car il permet d’accéder au début de la liste chaînée. Il agit parfois comme unnœud sentinelle(placé avant le nœud principal réel) pour des opérations plus faciles comme l'insertion en tête. La queue est une référence au dernier nœud de la liste. Son pointeur suivant est nul indiquant la fin de la liste.

Efficacité de la mémoire des insertions/suppressions

Par rapport aux tableaux, les listes chaînées sont plus efficaces en termes d'insertion/suppression puisque ces opérations ne nécessitent pas de « décalage » d'éléments. L'opération d'ajout ou de suppression d'un élément de n'importe où dans une liste chaînée prend $O(1)$O(1)temps. Cependant, il faut $O(n)$O(n)temps dans le pire des cas pour parcourir la liste chaînée pour ensuite ajouter/supprimer un élément (ne s'applique pas à l'ajout/suppression du premier élément).

Il convient de souligner que les listes chaînées ont une surcharge de mémoire supplémentaire en raison du stockage des pointeurs ainsi que des données dans chaque nœud.

Analyse de la complexité temporelle

Insertion :

• au début ou à la fin (avec pointeurs tête/queue) → $O(1)$O(1)
• à une position spécifique (en raison de la traversée) → $O(n)$O(n)

Suppression :

• au début → $O(1)$O(1)
• à la fin → $O(n)$O(n)
• à un poste spécifique → $O(n)$O(n)

Traversée/Recherche : $O(n)$O(n)

Implémentation JavaScript

POO classique

class ListNode { constructor(val, nextNode = null) { this.val = val; this.next = nextNode; } } class LinkedList { constructor() { // sentinel node for easy operations on head this.head = new ListNode(-1); this.tail = this.head; } // get the value at the specified index. get(index) { let curr = this.head.next; let i = 0; while (curr !== null) { if (i === index) return curr.val; curr = curr.next; i++; } return -1; } // insert a new value at the head of the list. insertHead(val) { const newNode = new ListNode(val); newNode.next = this.head.next; this.head.next = newNode; if (newNode.next === null) { this.tail = newNode; } } // insert a new value at the tail of the list. insertTail(val) { const newNode = new ListNode(val); this.tail.next = newNode; this.tail = newNode; } // remove the node at the specified index. remove(index) { let curr = this.head; let i = 0; while (i < index && curr.next !== null) { i++; curr = curr.next; } if (curr !== null && curr.next !== null) { if (curr.next === this.tail) this.tail = curr; curr.next = curr.next.next; return true; } return false; } // get all values in the list as an array. getValues() { const values = []; let curr = this.head.next; while (curr !== null) { values.push(curr.val); curr = curr.next; } return values; } // get the length of the list. length() { let length = 0; let curr = this.head.next; while (curr !== null) { length++; curr = curr.next; } return length; } }

POO fonctionnelle

function ListNode(val, nextNode = null) { this.val = val; this.next = nextNode; } function LinkedList() { this.head = new ListNode(-1); // Sentinel node this.tail = this.head; } // get the value at the specified index LinkedList.prototype.get = function(index) { let curr = this.head.next; let i = 0; while (curr !== null) { if (i === index) return curr.val; curr = curr.next; i++; } return -1; }; // insert a new value at the head of the list LinkedList.prototype.insertHead = function(val) { const newNode = new ListNode(val); newNode.next = this.head.next; this.head.next = newNode; if (newNode.next === null) { this.tail = newNode; } }; // insert a new value at the tail of the list LinkedList.prototype.insertTail = function(val) { const newNode = new ListNode(val); this.tail.next = newNode; this.tail = newNode; }; // remove the node at the specified index LinkedList.prototype.remove = function(index) { let curr = this.head; let i = 0; while (i < index && curr.next !== null) { i++; curr = curr.next; } if (curr !== null && curr.next !== null) { if (curr.next === this.tail) this.tail = curr; curr.next = curr.next.next; return true; } return false; }; // get all values in the list as an array LinkedList.prototype.getValues = function() { const values = []; let curr = this.head.next; while (curr !== null) { values.push(curr.val); curr = curr.next; } return values; }; // get the length of the list LinkedList.prototype.length = function() { let length = 0; let curr = this.head.next; while (curr !== null) { length++; curr = curr.next; } return length; };

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!