Verkettete Listen weiß jemand die Antwort?
2 Antworten
removeFirst und isEmpty kann offensichtlich in kons. Zeit ausgeführt werden.
Kann nur entweder size sein oder clear...
Wenn du die größe der verketten Liste wissen willst...also mit size...müsstest du durch die ganze Liste gehen..und das braucht O(n) zeit...
Bei clear bin ich mir da nicht mehr so sicher...^^
size & clear
size aber nur wenn kein counter verwendet wird.
clear kann in konstanter Zeit ausgeführt werden, wenn Garbage Collector aktiv ist =D
machst du eigentlich irgendeine Hausaufgabe auch selbst?!
aber das macht dann nicht dein Programm, oder? auf jeden Fall nicht beim löschen. Vielleicht beim allokieren.
beim Löschen muss man selbst nur Anfang und Ende auf null setzen und das Wars. Der Rest macht der GC.
Kann aber schon sein, dass die Arbeit nicht einfach ignoriert wird, nur weil sie ein Anderer macht^^
Ich könnte mir vorstellen, dass man eine intelligente Garbage Collection schreiben könnte, welche eine Callback anstatt einer Blockadresse beim Freigeben übernimmt.
Sobald CPU Zeit verfügbar ist, wird die übergebene Callback aufgerufen, wo man das Freigeben aller Kettenelemente durchführt.
Man übergibt also praktisch die gesamte Kette an die GC und definiert den Freigabemechanismus.
clear kann in konstanter Zeit da es schlicht ein Löschen des Pointers ist ;) bzw first auf Null setzen. Glaub nicht das die hier bedenken das jedes der Teil Elemente auch noch einzeln gelöscht werden muss..
hmmm glaub durchaus das in den meisten Fällen kein Zähler eingesetzt wird. Wer hält sonst den Zähler das erste Element wenn du bei dem bist weiß du doch noch gar nicht ob das Einfügen Erfolg hatte. Alle Elemente damit machst du das einfügen ja noch langsamer ...
Es kann leider nur eins ausgewählt werden
ich mal von clear aus?