Zeit, die Komplexität von Single-Link-Liste Einfügen und löschen

Ich bin ein bisschen verwirrt über die Zeit, die Komplexität der verketteten Listen. In diesem Artikel hier es besagt, dass einfügen und löschen in einer verknüpften Liste ist O(1). Ich wollte wissen, wie das möglich ist ? Es ist davon auszugehen, dass die forward-und next-Zeiger sind bekannt ? Wäre das nicht Doppelt verkettete Liste dann ? Ich würde es begrüßen, wenn jemand könnte dies klären . Und wie die Zeit, die Komplexität von insertion/deletion der einfach verkettete Liste O(1) ?

  • Fügen Sie die word sortiert in die Liste ein, und die Komplexität wird schnell Rampe. Ohne die Sorge um das "wo" insertion stattfindet, nur Verklemmen etwas auf ein Ende der Liste ist klar O(1). Wenn man etwas in einer bestimmten Position in der Liste ist O(1) haben Sie direkten Zugang auf den Zeiger, muss direkt neu verdrahtet, um den neuen Knoten (d.h. der Einfügepunkt).
InformationsquelleAutor Rajeshwar | 2014-03-24
  1. 4

    Ist es angenommen, dass die forward-und next-Zeiger sind bekannt ?

    In einfach verknüpfte Listen, sowohl für einfügen und löschen, müssen Sie einen Zeiger auf das element vor das einfügen/löschen Punkt. Dann alles klappt.

    Beispiel:

    # insert y after x in O(1)
def insert_after(x, y): 
    y.next = x.next
    x.next = y

# delete the element after x in O(1)
def delete_after(x):
    x.next = x.next.next

    Für viele Anwendungen ist es problemlos möglich, den Vorgänger des Elements, das Sie derzeit auf der Suche, die durch Ihren Algorithmus, um zu erlauben, für dynamisches einfügen und löschen in konstanter Zeit. Und natürlich kann man immer einfügen und löschen an der Vorderseite der Liste in O(1), das es ermöglicht, eine stack-like (LIFO) Verwendung Muster.

    Löschen ein Element, wenn Sie nur wissen, dass der Zeiger auf das Element ist in der Regel nicht möglich in O(1). EDIT: Als codebeard demonstriert, wir kann einfügen und löschen, indem Sie Sie nur zu wissen, einen Zeiger auf das einfügen/löschen Punkt. Es umfasst das kopieren der Daten aus dem Nachfolger, so dass bis zur Festsetzung der next Zeiger des Vorgängers.

    • +1 ... letzten Kommentar, , wenn Sie haben die Zeiger von Adresse (oder Referenz), was selten ist, um sicher zu sein, aber verdammt praktisch manchmal. Schön zu schreiben.
    • Ich muss sagen, die website zu sein scheint, irgendwie verwirrend zu sehen, wie das ist die zweite Frage dieser Art heute 😛 Vielleicht sollten Sie einige andere Ressourcen
    • Du meinst den Vorgänger-Zeiger? Ich dachte ich habe erwähnt, dass in den vorletzten Absatz
    • Sie meinte wohl das gleiche. Ich bezog das auf die tatsächliche Adresse, auf die Zeiger, die Punkte des Ziel-Knotens. Nicht der Wert (die offensichtlich von keinem nutzen ist). Es kann die Adresse-der head-Zeiger oder die Adresse einiger Knoten, die next Zeiger. Es spielt keine Rolle, welche. Seine das Ding, das als Verweis auf den Zielknoten. Wenn das, was Sie gemeint (und ich wünschte, ich könnte den Aufwärtstrend dieses wieder nur für die Nutzung des "vorletzten"), dann sind wir Total auf der gleichen Seite.
    • Ich sehe, was du jetzt meinst.. ich glaube nicht, dass es gibt Ihnen mehr macht, als die Vorgänger-Zeiger, wenn (ein Zeiger auf die "paar Knoten", die Punkte auf unsere Knoten), weil etwas konnte wurden eingefügt zwischen "einige Knoten und den Knoten in der Zwischenzeit. Nun Frage ich mich, ob es überhaupt möglich ist, dieses Weg zu ziehen, durch das einsetzen nicht durch die Schaffung neuer Knoten für das eingefügte element, aber durch das kopieren Ihrer Vorgänger und wiederverwenden von seiner Lage 😛 Aber vielleicht bekommen wir Probleme mit löschen.. Alles sehr komisch, aber einfach verknüpfte Listen sind echt cool in jedem Fall
    • Ich bin damit einverstanden, dass einige Sachen auf der genannten website ist wirklich warf mich aus. Zum Beispiel heißt es, dass für eine BST-worst-case-Szenario, der auf der Suche ist O(n). Ich nicht einverstanden mit diesem. Ich werde auch mal in andere Ressourcen
    • Beachten Sie den Unterschied zwischen binärer Suchbaum (die können entarten zu einer einzigen Kette von Knoten, wie in einer Liste) und balanced binary search tree (der eine logarithmisch begrenzt Höhe). Wikipedia ist eigentlich ganz nützlich, wenn es um algorithmen
    • Sie brauchen nicht immer zu wissen, das element, bevor Sie die Einfügemarke. Siehe meine Antwort.
    • Jetzt sehe ich, was Sie dort Tat, guter Punkt. Dies erfordert das kopieren von Daten um, obwohl
    • kopieren von Zeigern/Referenzen O(1).
    • Sicher, aber wenn du bist gut mit Umweg und zusätzliche Zeiger, Sie könnte genauso gut verwenden Sie eine doppelt verkettete Liste. Einzeln Listen sind in der Regel verwendet, wenn Sie Platz sparen wollen und/oder Persistenz, beides ist nicht möglich, wenn Sie es tun auf diese Weise. Ich denke, das ist, warum es nicht so Häufig verwendet, aber ich weiß nicht,
    • Die OP ' s Frage bezieht sich auf die Zeit-Komplexität ist also egal, welcher Mechanismus verwendet wird (kopieren oder Zeiger), es ist immer noch O(1).
    • Sicher, sicher, du hast absolut Recht, ich habe nur gefragt, warum diese nicht Häufig verwendet, da es scheint, ziemlich nützlich. Ich bearbeitet meine Antwort um diese Tatsache zu verdeutlichen (hoffe du verzeihst mir)

    InformationsquelleAutor Niklas B.
  2. 3

    Ja, es ist vorausgesetzt, dass Sie bereits wissen, den Ort, an dem Sie einfügen möchten die Daten.

    Angenommen, Sie haben einige Artikel p in der Liste, und Sie möchten fügen Sie ein neues element new nach p in der Liste:

    new->next = p->next;
p->next = new;

    Alternativ nehme an, das Sie einfügen möchten new vor p. Dies kann noch getan werden, in O(1) Zeit:

    if (p == head) {
    new->next = head;
    head = new;
} else {
    tmp = p->data;
    p->data = new->data;
    new->data = tmp;
    new->next = p->next;
    p->next = new;
}

    Wie für das löschen von Elementen in einer herkömmlichen, einzeln verkettete Listen, es ist nicht unbedingt O(1)!

    Es ist O(1) für das löschen von allen Elementen außer dem letzten element. Wenn Sie versuchen, löschen des letzten Elements in eine einfach verkettete Liste, Sie müssen wissen, das element, bevor es (das erfordert O(N) Zeit-vorausgesetzt, Sie wusste es nicht vor).

    Löschen das Element p:

    free_if_necessary(p->data);
if (p->next) {
    /* O(1) */
    nextnext = p->next->next;
    nextdata = p->next->data;
    destroy_if_necessary(p->next);
    p->data = nextdata;
    p->next = nextnext;
} else if (p == head) {
    destroy_if_necessary(p);
    head = NULL;
} else {
    /* O(n) */
    prev = find_prev(head, p);
    destroy_if_necessary(p);
    prev->next = NULL;
}
    • Es funktioniert, weil die Daten, die Spitzen, von p ist behoben.
    • Ich erkannte, dass in der Zwischenzeit. Das ist ein guter trick
    • Danke @codebeard, dass extrem nützlich ist
    InformationsquelleAutor codebeard
  3. 0

    Vielleicht ist das Verhältnis zu den delete-und insert-operation für array.

    Und es ist eine Voraussetzung, dass Sie wissen, die Position, wo zum einfügen oder löschen.

    In der Reihe, wenn Sie möchten, einfügen oder löschen eines Elements an der Position pos, sollten Sie die anderen Elemente nach der position pos, so ist die Komplexität O(N).

    Aber in der Liste, wenn Sie führen Sie den gleichen Vorgang, brauchen Sie nicht zu berücksichtigen, die andere Elemente, so ist die Komplexität O(1).

    InformationsquelleAutor BlackMamba
Schreibe einen Kommentar