Verkettete Liste: Indirektionsstufe sinnvoll?

[Redfrettchen]

Hi,
in der Literatur und auch in vielen Implementation von verketteten Listen wird der Weg über eine Indirektionsstufe gegangen: Es werden, so wie man sich es auch vorstellt, explizit Knoten verwendet, d.h. es wird eine interne Knotenstruktur benutzt, die von außen nicht sichtbar ist.
Auch in der Java SE wird soweit ich weiß intern eine node Klasse für die Verwaltung in der LinkedList benutzt.

Rein von der Spezifikation einer verketteten Liste ist das aber nicht notwendig, mein bisheriger Gegenvorschlag war bisher immer, die Struktur wirklich rekursiv aufzubauen: Die Liste selbst enthält das erste Element (falls vorhanden) und verweist auf eine Liste selben Typs als Nachfolger.

Vorteile:
- keine doppelte Implementation der Wörterbuchoperationen, für Liste und Knoten
- keine zweite Klasse im Allgemeinen
- leichtes Abschneiden von ersten Elementen: Rückgabe eine des Listen-Knotens nach den abzuschneidenen Knoten
- Einfügen von Listen in Listen einfach möglich

Nachteile:
- möglicherweise mehr Aufwand zur Verwaltung von Eigenschaften, die die gesamte Liste betreffen (Größe)

Fällt euch noch etwas grundlegendes ein, oder gibt es ein allgemeinere Begründung für die Ablehnung meiner Variante?

 

[SlaterB]

generell alles, was die Liste als ganzes sieht, wird schwieriger,

Iterator, Indexe, Sortieren usw.,
deine Liste machte ja nicht viel mehr als die Knoten in Java,

die Liste in Java ist eine zusätzliche Abstraktion, für deren Funktionalität (Größe & Co.) du eine Hilfsklasse bräuchtest

oder diese Funktionalität in die Knoten selber legst, evtl. auch nicht ganz schlimm,
aber wenn du dann das List-Interface implementieren willst
(z.B. für Collections.sort) dann hört langsam der Spass auf

 

[Redfrettchen]

Joa, ich hab mal versucht das List-Interface auf meine Weise zu implementieren und bin dann schließlich bei isEmpty() gescheitert >.< Das Problem ist, wie vorhergesagt, dass size() nicht effizient (also mit O(1)) implementiert werden kann.
Aber generell sieht man an der Standard-Implementation von LinkedList, dass eine doppelte Implementation der Wörterbuchoperationen überflüssig ist (das haben wir im Unterricht immer gemacht, deswegen mein Gegenvorschlag). Aber mit so einer Hilfsklasse, wie sie in LinkedList vorhanden ist (anders, als ich oben noch vermutet habe), kann ich mich sehr gut abfinden, sie besteht ja wirklich nur aus einigen wenigen Zeilen.

Danke für die Antwort!