Zitat von
r2c2:
Also ich würde sagen out-of-place is bei verketteten Listen eher komplizierter, da man jeweils die einzelnen Items neu erzeugen muss(siehe unten).
Ich möchte mich jetzt hier gar nicht weiter über den Sinn und unsinn von in-place vs. nicht in-place streiten. Was ich sagen wollte (ein letztes mal auch sage) ist, dass die Idee einer zweiten Liste einfacher zu verstehen ist als ein zweiter Zeiger auf der gleichen Menge. Damit würde die Idee (je nach Definition) nicht in-place realisiert werden. Wie man es tatsächlich umsetzt ist dann eine andere Sache.
In-place wäre es wohl auch dann, wenn man eine zweite Liste nimmt, denn hier wird nur konstant viel mehr an Speicher gebraucht (jedes Element ist immer nur in einer der beiden Listen, egal ob real existent oder nicht). In einer verketteten Liste werden doch eh nur die Zeiger auf ein Element gespeichert, also brauch ich hier nie ein Element neu erzeugen, ich verschiebe nur den Speicher.
Wenn man sich nun die verkettete Liste als eine lineare Struktur, die hintereinander im Speicher liegt vorstellt (kann man machen, denn man folgt eh nur den Zeigern, was dazwischen im Speicher liegt interessiert uns für die Liste schließlich nicht), dann könnte man sich die Liste als eine Art Array dyn. Länge vorstellen (eine gewisse Vereinfachung, rein virtueller Natur!). Hier finde ich kann man sich leichter vorstellen mit zwei Listen zu arbeiten, als zwei Zeiger auf der gleichen Liste zu verwenden (ist nur meine Meinung).
Der Overhead einer zweiten Liste bestünde nun darin, dass man diese zwischen-speichern müsste. Man braucht also einen Zeiger auf das erste Element der Liste (und aus Bequemlichkeit einen auf das letzte Element, ermöglicht schnelles anhängen, ist aber nicht nötig). Das sind also zwei Zeiger, die man benötigt. Kling finde ich nach einem vertretbaren und vorallem konstanten Overhead.
Da hier eh nur mit Zeigern gearbeitet wird, kann ich Elemente einfach verschieben, ohne dass ich die je kopieren muss. Also brauche ich nur konstant viel mehr Speicher (ca. 8 Byte). Das wäre also (entgegen meiner ersten Behauptung) durchaus in-place, gebe ich dir Recht!
Jetzt finde ich es aber immer noch leichter, dass ich mir vorstelle, dass ich eine sortierte Liste und eine unsortierte habe. Am Anfang ist dann die sortierte Liste leer, die unsortierte voll. Jetzt durchsucht man alle Elemente der unsortierten Liste und nimmt das kleinste raus. Dies wird nun in die sortierte Liste getan. So macht man weiter. Die Frage ist also, wie nimmt man ein Element aus einer Liste heraus und wie fügt man es in eine Liste ein. Da hat r2c2 ja schon einiges zu gesagt. Wie man das letztlich realisiert ist jedoch auf mehr als eine Art und Weise möglich (wie vielleicht aus den letzten Beiträgen inkl. diesem hervor geht).
Falls der Threadsteller hier nicht auf eine einfach verkettete Liste eingeschränkt ist, so bietet sich eine doppelt verkettete Liste an, diese kennt dann auch ihren Vorgänger, dass macht das ausgliedern eines Elements leichter.