[Java] geordnetes Einfügen in Liste

[polti]

Hallo,

zuerst möchte ich darauf hinweisen, dass ich noch ein totaler Anfänger bin, was das Programmieren betrifft. :wink:

so und nun zu meinem Problem:
ich möchte ein Objekt vom Typ T in eine bestehende Liste sortiert einfügen.
Zur Verfügung stehen mir die Klassen LinkedList<T> und Node<T>, welche ich selbst geschrieben habe.

für das Einfügen schreibe ich nun eine Methode insert(T obj)
hier mal ein kleines Grundgerüst, bitte nicht lachen:

public boolean insert(T obj){

Node<T> tempNode = list.head;
T tempObj = (T) tempNode;
while(tempNode.getNext() != null){

if (tempObj.compareTo(obj)== 0) {
list.addLast(obj);
return false;
}
tempNode = tempNode.getNext();
tempObj = (T) tempNode;
}

return true;
}


also so wie es da geschrieben steht, ist es natürlich Mist, vom Inhalt mal ganz abgesehen.
ich bekomme nämlich eine ClassCastException (in markierter Zeile)

so, und nun zu meinem Problem:
ich habe keine Idee, wie ich über die bestehende Liste "LinkedList<T> list" navigieren kann, um die richtige Einfügeposition zu finden
mein bisheriger Plan, das über die Klasse Node zu bewältigen, wird ja mit besagter Exception quittiert.
mit dem Iterator aus java.util.* kann ich zwar navigieren, aber leider nicht Einfügen,
weshalb ich mit meinem Latain am Ende bin.

deshalb suche ich hier nach Hilfe!!!

gruß
polti09

[Monger]

Dämliche Frage, aber warum verwendest du denn nicht die LinkedList aus dem Java JDK?

http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html


Aber deine fettgedruckte Zeile ist natürlich Quark. Ein Knoten HAT ein Objekt, er IST es aber nicht! Ein Node ist nur ein Hilfskonstrukt. Sinngemäß müsste es bei dir heißen:


T tempObject = node.getObject();

Dann gehst du die Liste von vorne bis hinten durch, und vergleichst das Element jedes Knotens mit dem Element was du einfügen willst. Sobald dein Objekt größer ist, erzeugst du an der Stelle einen neuen Knoten, und bettest dein Objekt dort ein.
Von der Idee her bist du also schon richtig.

[polti]

Ah,
vielen Dank!
ich habe natürlich ganz vergessen, dass die Nodes nur auf die Objekte "zeigen". (wie peinlich :rolleyes: )

gruß

[mithrandir]

Dere!

Ich halte es generell für fragwürdig eine einfach verkette Liste dafür zu nehmen, da man ja an einem bestimmten Index einfügen muss. Gibt's da nicht performantere Listen-Implementierungen (ArrayList)?

bye, Peter

[Monger]

Dere!

Ich halte es generell für fragwürdig eine einfach verkette Liste dafür zu nehmen, da man ja an einem bestimmten Index einfügen muss. Gibt's da nicht performantere Listen-Implementierungen (ArrayList)?

bye, Peter

Gerade ArrayList ist afaik für Einfügeoperationen extrem inperformant. Genau dafür ist ja eine LinkedList da: damit man die Kette an jeder beliebigen Stelle aufbrechen und durch zusätzliche Elemente ergänzen kann.

Aber du hast natürlich Recht, dass man die Suche nach dem richtigen Einfügepunkt sicherlich effektiver gestalten kann.

[HellHorse]

Gerade ArrayList ist afaik für Einfügeoperationen extrem inperformant.
Solange man nur am Ende einfüg (habe bisher nie was anderes gemacht) ist meiner Erfahrung nach ArrayList viel performanter.

Aber du hast natürlich Recht, dass man die Suche nach dem richtigen Einfügepunkt sicherlich effektiver gestalten kann.
-> SkipList

[Monger]

Solange man nur am Ende einfüg (habe bisher nie was anderes gemacht) ist meiner Erfahrung nach ArrayList viel performanter.

Ich meinte natürlich einfügen an beliebiger Stelle. Wenn Arraylist beim einfachen anhängen schon schlecht wäre, wäre es ganz bitter! ;)

[polti]

das meine Vorgehensweise nicht die beste ist, ist mir schon bewusst.
aber es macht jetzt das, was es auch tatsächlich soll.
und damit gebe ich mich auch zufrieden!

die verwendung einer doppelt-verketteten Liste ist natürlich schon sinnvoller,
das das Einfügen der Knoten einfacher von statten geht.

aber ich habe es auch mit der einfach-verketteten hinbekommen.

gruß

[mithrandir]

Wie sind eigentlich FastList und FastTable (Javolution (http://www.javolution.org/)) implementiert, um angeblich so schnell zu sein?

[PatkIllA]

das meine Vorgehensweise nicht die beste ist, ist mir schon bewusst.
aber es macht jetzt das, was es auch tatsächlich soll.
und damit gebe ich mich auch zufrieden!

die verwendung einer doppelt-verketteten Liste ist natürlich schon sinnvoller,
das das Einfügen der Knoten einfacher von statten geht.

aber ich habe es auch mit der einfach-verketteten hinbekommen.
Warum ist es in einer doppelt verketten Liste das Einfügen einfacher? Du musst noch noch einen Zeiger mehr einfügen und zum sortierten Einfügen hilft es auch nicht, da das Finden der Position in lineare Zeit benötigt O(n). Da wäre eher eine Skipliste angebracht, da das Suchen in log n geht.

[polti]

ich stimme mit dir über ein, dass das finden der einfügeposition bei einer doppelt-verketteten liste nicht schneller erfolg, aber das einfügen an sich geht einfacher von statten, da man hier direkt auf den vorgänger zugreifen kann.

bei einer einfach-verketteten list ist das navigieren zum vorgänger hinsichtlich der einfügeposition etwas umständlicher.

zur skipliste kann ich leider nichts sagen, da ich sie net kenne.

gruß
polti

[HellHorse]

ich stimme mit dir über ein, dass das finden der einfügeposition bei einer doppelt-verketteten liste nicht schneller erfolg,
Doch sicher, alle Items die "hinter der Mitte" liegen findest du schneller

aber das einfügen an sich geht einfacher von statten, da man hier direkt auf den vorgänger zugreifen kann.
Ein oder zwei Referenzen umhängen, das ist ja fast das gleiche. Es ist ja nicht so, dass bei einer doppelt verketteten List noch irgendwelche Rotationen gemacht werden müssen.

[PatkIllA]

Doch sicher, alle Items die "hinter der Mitte" liegen findest du schnellerAber auch nur wenn du weißt, das sie in der letzten Hälfte liegen.