Ce jour marque la troisième journée d'exercices axés sur les structures de données de listes chaînées. Nous allons aborder trois problèmes classiques : la suppression d'éléments spécifiques, la conception d'une classe de liste chaînée et l'inversion d'une liste chaînée.

Suppression d'éléments d'une liste chaînée

Le premier problème consiste à supprimer toutes les occurrecnes d'une valeur donnée dans une liste chaînée. Une approche courante consiste à utiliser un pointeur factice (dummy node) en tête de liste pour simplifier la gestion des suppressions, y compris celle du premier élément.

/**
 * Définition d'une liste chaînée.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var supprimerElements = function(head, val) {
    // Créer un nœud factice pour simplifier la logique
    let noeudFactice = new ListNode(0, head);
    let pointeurPrecedent = noeudFactice;
    let pointeurCourant = head;

    while (pointeurCourant !== null) {
        if (pointeurCourant.val === val) {
            // Sauter le nœud courant
            pointeurPrecedent.next = pointeurCourant.next;
        } else {
            // Avancer le pointeur précédent seulement si le nœud courant n'est pas supprimé
            pointeurPrecedent = pointeurCourant;
        }
        // Avancer le pointeur courant dans tous les cas
        pointeurCourant = pointeurCourant.next;
    }

    // Retourner la tête de la liste modifiée (après le nœud factice)
    return noeudFactice.next;
};

Conception d'une classe de liste chaînée doublement chaînée

Le second problème est de concevoir une classe MaListeChainee qui supporte les opérations d'ajout, de récupération et de suppression d'éléments à des indices spécifiés, ainsi que l'ajout en tête et en queue. Nous implémenterons une liste chaînée doublement chaînée pour une efficacité optimale des opérations à la queue.

// Classe pour représenter un nœud de la liste chaînée
class NoeudListe {
    constructor(valeur, suivant = null, precedent = null) {
        this.valeur = valeur;
        this.suivant = suivant;
        this.precedent = precedent;
    }
}

// Classe principale pour la liste chaînée doublement chaînée
var MaListeChainee = function() {
    this.tete = null;
    this.queue = null;
    this.taille = 0;
};

/**
 * Obtient le nœud à un index donné.
 * @param {number} index L'index du nœud à récupérer.
 * @returns {NoeudListe | null} Le nœud à l'index spécifié ou null si l'index est invalide.
 */
MaListeChainee.prototype.obtenirNoeud = function(index) {
    if (index < 0 || index >= this.taille) {
        return null;
    }
    let noeud;
    // Optimisation : parcourir depuis la tête ou la queue selon l'index
    if (index < this.taille / 2) {
        noeud = this.tete;
        for (let i = 0; i < index; i++) {
            noeud = noeud.suivant;
        }
    } else {
        noeud = this.queue;
        for (let i = this.taille - 1; i > index; i--) {
            noeud = noeud.precedent;
        }
    }
    return noeud;
};

/**
 * Récupère la valeur du nœud à l'index spécifié.
 * @param {number} index L'index du nœud.
 * @return {number} La valeur du nœud, ou -1 si l'index est invalide.
 */
MaListeChainee.prototype.get = function(index) {
    const noeud = this.obtenirNoeud(index);
    return noeud ? noeud.valeur : -1;
};

/**
 * Ajoute un nœud avec la valeur donnée en tête de la liste.
 * @param {number} val La valeur à ajouter.
 * @return {void}
 */
MaListeChainee.prototype.addAtHead = function(val) {
    const nouveauNoeud = new NoeudListe(val, this.tete, null);
    if (this.tete !== null) {
        this.tete.precedent = nouveauNoeud;
    } else {
        // Si la liste était vide, le nouveau nœud est aussi la queue
        this.queue = nouveauNoeud;
    }
    this.tete = nouveauNoeud;
    this.taille++;
};

/**
 * Ajoute un nœud avec la valeur donnée en queue de la liste.
 * @param {number} val La valeur à ajouter.
 * @return {void}
 */
MaListeChainee.prototype.addAtTail = function(val) {
    const nouveauNoeud = new NoeudListe(val, null, this.queue);
    if (this.queue !== null) {
        this.queue.suivant = nouveauNoeud;
    } else {
        // Si la liste était vide, le nouveau nœud est aussi la tête
        this.tete = nouveauNoeud;
    }
    this.queue = nouveauNoeud;
    this.taille++;
};

/**
 * Ajoute un nœud avec la valeur donnée à un index spécifié.
 * @param {number} index L'index où ajouter le nœud.
 * @param {number} val La valeur du nœud à ajouter.
 * @return {void}
 */
MaListeChainee.prototype.addAtIndex = function(index, val) {
    if (index < 0 || index > this.taille) {
        return; // Index invalide
    }
    if (index === 0) {
        this.addAtHead(val);
    } else if (index === this.taille) {
        this.addAtTail(val);
    } else {
        // Obtenir le nœud précédent l'index d'insertion
        const noeudPrecedent = this.obtenirNoeud(index - 1);
        const nouveauNoeud = new NoeudListe(val, noeudPrecedent.suivant, noeudPrecedent);
        noeudPrecedent.suivant.precedent = nouveauNoeud;
        noeudPrecedent.suivant = nouveauNoeud;
        this.taille++;
    }
};

/**
 * Supprime le nœud à l'index spécifié.
 * @param {number} index L'index du nœud à supprimer.
 * @return {void}
 */
MaListeChainee.prototype.deleteAtIndex = function(index) {
    if (index < 0 || index >= this.taille) {
        return; // Index invalide
    }

    if (index === 0) {
        // Suppression de la tête
        this.tete = this.tete.suivant;
        if (this.tete !== null) {
            this.tete.precedent = null;
        } else {
            // La liste est devenue vide
            this.queue = null;
        }
    } else if (index === this.taille - 1) {
        // Suppression de la queue
        this.queue = this.queue.precedent;
        this.queue.suivant = null;
    } else {
        // Suppression d'un élément intermédiaire
        const noeudASupprimer = this.obtenirNoeud(index);
        noeudASupprimer.precedent.suivant = noeudASupprimer.suivant;
        noeudASupprimer.suivant.precedent = noeudASupprimer.precedent;
    }
    this.taille--;
};

Inversion d'une liste chaînée simple

Enfin, nous inversons une liste chaînée simple. L'algorithme itératif est efficace, nécessitant trois pointeurs : un pour le nœud précédent, un pour le nœud courant, et un temporaire pour stocker le nœud suivant avant de modifier le poitneur courant.

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var inverserListe = function(head) {
    let pointeurPrecedent = null;
    let pointeurCourant = head;
    let noeudTemporaire = null;

    while (pointeurCourant !== null) {
        // Sauvegarder le prochain nœud avant de le modifier
        noeudTemporaire = pointeurCourant.next;
        // Inverser le pointeur 'next' du nœud courant
        pointeurCourant.next = pointeurPrecedent;
        // Avancer les pointeurs pour la prochaine itération
        pointeurPrecedent = pointeurCourant;
        pointeurCourant = noeudTemporaire;
    }

    // Le pointeur 'precedent' pointe maintenant vers la nouvelle tête de la liste inversée
    return pointeurPrecedent;
};

Ces exercices fournissent une base solide pour la compréhension et la manipulation des listes chaînées, des structures de données fondamentales en informatique.