Implementierung einer einfach verknüpften Liste

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Einfach verknüpfte Listen verstehen

Eine verknüpfte Liste ist eine Datenstruktur, die eine Folge von Knoten darstellt. In einer einfach verknüpften Liste zeigt jeder Knoten auf den nächsten Knoten.

Im Speicher müssen diese Knoten nicht zusammenhängend (nebeneinander) sortiert werden, da wir nicht auf die Indizierung angewiesen sind. Wenn wir eine verknüpfte Liste durchlaufen, durchlaufen wir jede Referenz eines Knotens, bis wir auf einen Null-Zeiger treffen.

Struktur eines Knotens

In einer einfach verknüpften Liste enthält jeder Knoten normalerweise zwei Felder:

• Daten: der im Knoten enthaltene Wert oder die Information
• next: der Verweis (Zeiger) auf den nächsten Knoten in der Liste

Kopf- und Schwanzzeiger

Der Kopf ist eine Referenz auf den ersten Knoten in der Liste. Dies ist wichtig, da es den Zugriff auf den Anfang der verknüpften Liste ermöglicht. Er fungiert manchmal als Sentinel-Knoten (vor dem eigentlichen Kopfknoten platziert) für einfachere Vorgänge wie das Einfügen am Kopf. Der Schwanz ist ein Verweis auf den letzten Knoten in der Liste. Der nächste Zeiger ist null und zeigt das Ende der Liste an.

Speichereffizienz von Einfügungen/Löschungen

Im Vergleich zu Arrays sind verknüpfte Listen hinsichtlich des Einfügens/Löschens speichereffizienter, da diese Vorgänge kein „Verschieben“ von Elementen erfordern. Das Hinzufügen oder Entfernen eines Elements an einer beliebigen Stelle in einer verknüpften Liste dauert $O(1)$O(1) Zeit. Allerdings dauert es $O(n)$O(n) Im schlimmsten Fall dauert es, die verknüpfte Liste zu durchlaufen, um dann ein Element hinzuzufügen/zu entfernen (gilt nicht für das Hinzufügen/Entfernen des ersten Elements).

Es ist erwähnenswert, dass verknüpfte Listen aufgrund der Speicherung von Zeigern zusammen mit den Daten in jedem Knoten zusätzlichen Speicheraufwand verursachen.

Zeitkomplexitätsanalyse

Einfügung:

• am Anfang oder Ende (mit Kopf-/Schwanzzeigern) → $O(1)$O(1)
• an einer bestimmten Position (aufgrund der Durchquerung) → $O(n)$O(n)

Löschung:

• am Anfang → $O(1)$O(1)
• am Ende → $O(n)$O(n)
• an einer bestimmten Position → $O(n)$O(n)

Durchquerung/Suche: $O(n)$O(n)

JavaScript-Implementierung

Klassisches OOP

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;
    }
}

Funktionelles OOP

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;
};

Das obige ist der detaillierte Inhalt vonImplementierung einer einfach verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!