LinkedList Fragen

[ChaosE]

Hallo,

beim Programmieren bin ich auf zwei Fragen zur LinkedList Klasse gestossen, auf die weder SUN Doku noch google keine Antwort parat hatten. Aber immerhin bin ich so auf diese Forum aufmerksam geworden Zu meinem Hintergrund: Ich bin von Haus aus eher C++ Programmierer (gewesen, zur Zeit mache ich mehr mit Java) mit mathematisch/informatischem Background (Studium abgeschlossen).

Frage #1:
LinkedList benutzt als Modell eine doppelt verkettele Liste. Wenn ich die Größe einer Liste mit mylist.size() abfrage - hat das O(n) oder O(1), sprich zählt die Liste die ganze Zeit mit oder nicht? Beide Implementationen sind üblich, je nachdem ob man entweder split() oder size() in konstanter Zeit haben möchte. Die STL Implementation von C++ wählt die erste Variante, sprich size() Aufrufe sind teuer. Wo finde ich solche Infos für die Java Collections, gibt es da technisch tiefergehende Bücher oder Onlinedoku?

Frage #2:
Gibt es eine zyklische LinkedList Variante?

Frage #3:
Die ist etwas komplizierter und hat mit den Failsafe ListIteratoren und dem leidigen "verändern während des Iterierens" Thema zu tun, was hier schon das eine oder andere mal diskutiert wurde (ja, ich weiss wie man sucht ). Mein Problem ist das folgende: Ich re-implementiere gerade eine 3D C++ Datenstruktur in Java. Diese besteht - grob vereinfach - aus einer doppelt verketten Liste. Die Elemente der Liste sind etwas komplexere Objekte, die sich sowohl zum Teil gegenseitig referenzieren, als auch - jetzt kommts - die eigene Position (Iterator) in der Liste kennen sollen. Hintergrund ist, dass das Löschen eines Objektes in O(1) gehen soll, ohne das Objekt in der Liste suchen zu müssen. Vorteil einer doppelt verketten Liste ist ja (normalerweise) auch, dass zum Löschen eines Listenelements in konstanter Zeit zwei Zeilen Code ausreichen (previous.next = this.next; next.previous = this.previous.

Soweit so gut - aber selbst wenn ich es hinbekommen sollte den ListIterator für jedes Objekt im Objekt selber abzuspeichern (leider scheint es keinen LinkedList Methode zu geben, welche mir einen Iterator auf das letzte Element liefert), werden die ja alle ungültig sobald ich auch nur eines davon lösche. Eine andere Datenstruktur (Hashtable) kommt aus Effizienzgründen nicht in Frage, die Objekte sind gross und es sind sehr viele, so dass ich selbst bei 2GB Hauptspeicher schnell an Grenzen komme wenn ich nicht sauber progammiere.

Meine bisherige Überlegung geht daher in die Richtung meine eigene MyLinkedList Klasse zu entwerfen, die alle genannten Bedingungen erfüllt (zyklisch, konstanter Zugriff auf die size() und non-Failsafe Iteratoren). Gibt es eine bessere Lösung?

So, ich hoffe ich habe die Fragen präzise genug formuliert.

MfG;
ChaosE

 

[Wildcard]

-Die Liste zählt die size mit
-Du kannst auch einfach die remove Methode des Iterators benutzen :wink:
-Wenn du einen ListIterator nimmst, kannst du die Position angeben an der dieser beginnen soll

 

[ChaosE]

-Die Liste zählt die size mit

Ah, gut !

-Du kannst auch einfach die remove Methode des Iterators benutzen :wink:

Okay, aber was ist dann mit den anderen Iteratoren? Nehmen wir an, ich möchte alle geometrischen Nachbarn eines Objekts löschen (obj.delNeighbours()), die sich alle auch selbst aus der "globalen" Liste austragen. Sind nach dem ersten Löschen nicht alle anderen Iteratoren ungültig? Wie gesagt, jedes Objekt soll einen Iterator auf sich selbst in der Liste mitschleifen, der nur zum Löschen des Objektes selbst verwendet wird.

-Wenn du einen ListIterator nimmst, kannst du die Position angeben an der dieser beginnen soll

Jo, hab ich gesehen. Aber ist das dann nicht wirklich O(n)? Die Methode fängt doch bestimmt von vorne an und hört bei der Position auf, würde ich vermuten.

Vielen Dank soweit;
ChaosE

 

[Wildcard]

Okay, aber was ist dann mit den anderen Iteratoren? Nehmen wir an, ich möchte alle geometrischen Nachbarn eines Objekts löschen (obj.delNeighbours()), die sich alle auch selbst aus der "globalen" Liste austragen. Sind nach dem ersten Löschen nicht alle anderen Iteratoren ungültig? Wie gesagt, jedes Objekt soll einen Iterator auf sich selbst in der Liste mitschleifen, der nur zum Löschen des Objektes selbst verwendet wird.

Das ist korrekt. Aber mit Iteratoren mitschleifen ist so eine Sache, da diese normal on-demand erzeugt werden.
Wenn du sie in Reserve haben willst, dann müsstest du sie ja bei jeder Listenoperation neu erzeugen :shock:

Jo, hab ich gesehen. Aber ist das dann nicht wirklich O(n)? Die Methode fängt doch bestimmt von vorne an und hört bei der Position auf, würde ich vermuten.

Ohne mir die Implementierung angesehen zu haben würde ich das auch vermuten.

 

[ChaosE]

Das ist korrekt. Aber mit Iteratoren mitschleifen ist so eine Sache, da diese normal on-demand erzeugt werden.
Wenn du sie in Reserve haben willst, dann müsstest du sie ja bei jeder Listenoperation neu erzeugen :shock:

Jain. Ich vermute, das das bei der LinkedList Implementation für Java so ist wie Du es beschreibst. Bei einer "echten" verketten Liste muss das nicht unbedingt so sein.

Okay, etwas weiter ausholen: Eine doppelt Verkettete Listenimplementation hat ja normalerweise eine Unterklasse LinkedListElement, letztere besteht in der Regel aus drei Referenzen (in anderen Programmiersprachen auch Zeigern, ich weiss in Java ein böses Wort). Eine auf das vorherige, eine auf das nachfolgende Listenelement und einen auf das Element das in der Liste verwaltet wird selbst:

Class ListElement {
  public ListElement prev;
  public ListElement next;
  public Object obj;
}

Die eigentliche Liste selbst enthält dann meist einen Zeiger auf das erste, eventuell auf das letzte ListElement und zählt (je nach Anwendungsfall) noch die Anzahl der ListElemente mit.

Wenn ich jetzt eine Liste von meinen komplexen Elementen anlege, kann jedes Objekt eine Referenz auf das ListElement enthalten, in der es in der globalen Objektliste abgelegt ist.

Class MyObject {
  public Vector3d[] huge_data;
  public ListElement my_place;
}

Soll das Objekt dann später gerlöscht werden, kann es sich selbst in konstanter Zeit aus dieser Liste austragen, ohne sich selbst suchen zu müssen (Laufzeit = teuer) oder das eine der anderen Referenzen ungültig wird, d.h. die Iteratoren müssen nicht neu erzeugt werden sondern bleiben weiterhin gültig. Man muss ein bisserl aufpassen was man tut, dafür ist es extrem effizient bei veränderungsintensiven Datenstrukturen wo oft gelöscht und eingefügt werden muss. Wie heisst es so schön: "Der Iterator wird Dir die dunkle Seite der Macht zeigen!" Oder so ähnlich

Ich vermute aber inzwischen ganz stark, dass letzteres mit der LinkedList Implementation von Java nicht funktioniert, so dass ich wohl oder übel meine eigene Listenklasse schreiben muss. Würde mich aber gerne vom Gegenteil überzeugen lassen da ich eigentlich schon ganz gerne Standard-Klassen benutze.

MfG;
ChaosE

 

[Wildcard]

Nein, du musst LinkedList in jedem Fall erweitern, anders geht's nicht.
Überhaupt, wenn du dir nicht wirklich sicher bist das du jedes KB Speicher brauchst, dann bist du mit dem HashSet IMO besser aufgehoben.
Spätestens bei Threads wirst du mit dieser Datenstrucktur nämlcih richtig Spaß haben, ausserdem erfordert es, dass die verwalteten Objekte in etwas eingreifen was nur die Liste etwas angeht und ist schon aus diesem Gesichtspunkt IMO unsauber.

 

[ChaosE]

Leider brauche ich jedes KByte ... alleine die Rohdaten die ich zur Laufzeit im Speicher halten muss sind schon gerne mal 800-1000MB gross - und auf denen fangen die Algorithmen dann erst zu arbeiten an und erzeugen natürlich neuen Overhead. Den klein halten ist eine der Herausforderungen, wo ich mir am Anfang nicht sicher war ob man das in Java hinbekommt. Scheint aber zu klappen, obwohl man manchmal etwas Mühe hat.

Das Hautprogramm enthält in der Tat mehrere Threads, allerdings sehe ich da - saubere Programmierung vorausgesetzt - keine Probleme.

MfG;
ChaosE

 

[Wildcard]

Na dann, viel Glück.
Kannst das Ergebnis ja posten wenn du magst :wink: