[gelöst] Eintrag einer Liste mithilfe einer Referenz löschen.



  • Hallo,

    ich tüftle schon seit geraumer Zeit an meinem Programm rum, aber komm leider nicht weiter, vielleicht kann jemand mir helfen. Ich habe eine Referenz auf ein Element innerhalb einer Liste und möchte dieses entfernen. Ist das in konstanter Zeit möglich oder muss ich erst die komplette Liste nach dem entsprechenden Eintrag absuchen bzw. list::remove würde ja auch lineare Zeit benötigen.
    Ich weiß, dass man keine Referenz einfach löschen kann. Aber die Referenz wäre in einem Objekt gespeichert, was ich auch direkt löschen würde. Bzw. würde ich auch die Referenz durch einen Pointer ersetzen, wenn sich dadurch das direkte Löschen eines Elements ermöglichen ließe.
    Ich freue mich über jeden Hilfeversuch! Danke 🙂



  • Wie wäre es mit einem Iterator?



  • Ja aber dann müsste ich doch auch die Liste von Anfang bis zum jeweiligen Eintrag durch suchen oder gibts da ne andere Möglichkeit?



  • Ich versuche eigentlich die Adjacency List Structure zu implementieren. Dabei werden Knoten- und Kantenobjekte erstellt. Ein Knotenobjekt v soll dabei eine Referenz zu einer Liste I(v) haben, in der Referenzen zu den inzidenten Kanten von v gespeichert werden. Das Kantenobjekt für eine Kante e mit Endknoten v und w soll Referenzen zu den Positionen oder den Einträgen der zugehörigen Kanten in den Inzidenslisten haben. Nach meinem Buch soll dabei das Entfernen einer Kante in konstanter Zeit möglich sein. Da man aber wenn man von Knoten v ausgeht auch auf die Inzidenzliste von Knoten w zugreifen muss und da die entsprechende Kante löschen muss, kann man diese Zeit nur schaffen, wenn man direkten Zugriff auf diesen Eintrag hat.



  • list::erase ist O(n), wobei n die Zahl der zu löschenden Knoten angibt (und nicht die Länge der Liste). Also nimm, wie manni66 schon sagte, Iteratoren.



  • Womba schrieb:

    Ja aber dann müsste ich doch auch die Liste von Anfang bis zum jeweiligen Eintrag durch suchen oder gibts da ne andere Möglichkeit?

    Nein, mit einem Iterator und erase kannst du in O(1) löschen.
    Falls das nicht klar war: du sollst statt der Referenz auf den Inhalt einen Iterator auf das Listenelement speichern.



  • Oh man, da hatte ich wohl ein gewaltiges Brett vor dem Kopf. Vielen Dank!!!


Log in to reply