Reverse Iterator



  • @kolwe96 sagte in Reverse Iterator:

    Dann wird gefragt: Was muss geändert werden um die Reihenfolge des Iterators zu drehen.

    Da kommt es auf den genauen Wortlauf der Aufgabe an. Darfst du den normalen Iterator entsorgen und dafür nur den ReverseIterator anbieten? In dem Fall würde man quasi die Liste von vornherein verkehrt herum aufbauen. Das ist zwar irgendwie Betrug, aber wenn die Aufgabe das als Möglichkeit nicht ausschließt, sollte das zulässig sein.


  • |  Mod

    Oder die richtige Antwort ist "eine doppelt verkettete Liste daraus machen". Kommt wirklich auf die genaue Aufgabenstellung an.



  • Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).



  • @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Hängt wie gesagt von der Aufgabenstellung ab, wie weit du schummeln darfst.



  • @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, speichere alle Iteratoren vorwärts laufend in dem vector (n schritte) und iteriere rückwärts durch den vector (nochmal n Schritte). Gut, du hast dann auch O(n) Speicherverbrauch...



  • @wob sagte in Reverse Iterator:

    @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, speichere alle Iteratoren vorwärts laufend in dem vector (n schritte) und iteriere rückwärts durch den vector (nochmal n Schritte). Gut, du hast dann auch O(n) Speicherverbrauch...

    Das ist die Art von "Betrug", die mir auch vorschwebte... Wenn die Aufgabenstellung dem nicht widerspricht, kann er das so tun.



  • Okay,Danke



  • ich würde ne double linked list daraus machen. Das wäre nämlich der einzig vernünftige Weg diese Aufgabe zu lösen.



  • @wob sagte in Reverse Iterator:

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, ...

    Oder man borgt sich den Speicher einfach von Stack. z.B. indem man die Iterationsfunktion rekursiv aufruft. Die Reihenfolge ergibt sich dann daraus ob man das aktuelle Element vor dem Rekursiven auswerter (vorwärts), oder danach (rückwärts).
    Bei der vorwärts Iteration bekommt man dann ne Tail-Rekursion. Die man trivial wegoptimieren kann, was dann eine klassische Iterations-Schleife ergibt.



  • @spiri sagte in Reverse Iterator:

    ich würde ne double linked list daraus machen. Das wäre nämlich der einzig vernünftige Weg diese Aufgabe zu lösen.

    +1
    Ich kann mir auch nicht vorstellen, dass irgendwas anderes im Sinne der Aufgabe gemeint sein könnte.


Anmelden zum Antworten