Einfügen/Löschen irgendwo in einer verknüpften Liste in C++

Question

Ich habe C++ für eine Weile gelernt, und gerade erst begonnen, verknüpfte Listen zu suchen. Ich kann eine Template-Klasse List mit den üblichen Funktionen einfügen/entfernen von hinten/vorne erstellen. Jetzt kam ich mit einer Übung, die mich auffordert, eine Funktion zu schreiben, um Einfügungen/Löschungen irgendwo in der Liste zu handhaben.

Bitte beachten Sie, dass meine Fragen sind sehr einfach.

Das Problem, das ich habe ist, dass ich die Frage nicht eindeutig zu sehen. Welche Art von Informationen benötigt die Funktion? Zum Beispiel für das Löschen, I mit mehreren Kandidaten kommen kann: 1), um den ersten Knoten löschen, die einen bestimmten Wert (Argument hat: value) 2) Löschen alle Knoten mit einem bestimmten Wert (Argument: value) 3) löschen ein bestimmter Knoten (Argument: Zeiger auf diesen Knoten) 1) und 2) kann ich leicht codieren. 3) ist schwieriger, aber ich kann es auch tun. Ich sehe den Punkt in 3) einfach nicht. Ist es üblich, Knoten (außerhalb der Listendefinition) zu manipulieren, wenn man Listen verwendet? Wie in, ist es üblich für ein Programm, das Listen benutzt, um Zeiger auf die Knoten zu manipulieren?

Was ist die übliche Bedeutung von „löschen überall“ in dieser Einstellung?

Auch für „insert überall“ ist der Wortlaut seltsam. Was bedeutet "überall"? Soll der Platz in der verknüpften Liste von einem bestimmten Knoten vergeben werden?

Answer 1

In verknüpften Liste haben Sie konstante Zeit Zugriff auf das erste Element. Also delete/insert irgendwo bedeutet die Stelle, die zwischen dem ersten und letzten Element existiert. Grundsätzlich benötigen Sie 2 Iteratoren. Wenn Sie die Stelle finden, die Sie entfernen/einfügen möchten, sollten Sie sich auf das Objekt direkt davor beziehen. weil Sie nicht auf das vorherige Element Zugriff haben, nur auf den nächsten:
E0-> E1-> E2-> E3-> E4

Wenn Sie wollen: unsere verknüpften Liste das sieht aus wie sie an, entferne E3, du musst Iterator auf E2 setzen, damit du Zeiger für E2-> next korrigieren kannst.

gute Referenz ist das Buch Standard Library von Nicolai M. Josuttis schrieb. Das Problem, auf das Sie gestoßen sind, wird dort ausführlich beschrieben.

Answer 2

node*insert(node*head,int d){ 

    node*temp=new node; 
    temp->data=d; 
    if(head==NULL){ 
     temp->next=NULL; 
     head=temp;} 
    else 
     {node*curr=head,*pre=NULL; 
    while (curr!=NULL && curr->data<temp->data) 
    { 
     pre=curr; 
     curr=curr->next; 
    } 
    temp->next=curr; 
    if(pre==NULL) 
     head=temp; 
    pre->next=temp; 
    } 
    return head; 
}