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

Une liste chaînée est une structure de données qui représente une séquence de nœuds. Dans une liste 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 chaque référence d'un nœud jusqu'à ce que nous atteignions un pointeur null.

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

La tête est une référence au 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 un nœ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!