Probleme mit Listiteratoren:

[Markus Innerebner]

Hallo ihr, ich grüble seit mehreren Stunden um mein Problem mit
LinkedListen zu lösen:

Arbeite mit zwei LinkedList: LinkedListA, LinkedListB

Hierbei geht es darum, dass ich in einem Schleifendurchlauf je je ein
Element von LinkedListA nach LinkedListB verschiebe (also gleichzeitig
von LinkedListA lösche). Das Problem ist, dass ich beim Löschen auf den
Index des Elementes zugreifen muss. Mein Element-Objekte haben ein
ID-Attribut, durch welches ich notwendigerweise auf LinkedListA
zugreifen muss. Da sich aber nach einem Löschvorgang alle Elemente in
der LinkedList, die rechts vom bereits entfernten Objekt stehen, sich
der Index um eins dekrementiert, ist die Zuweisung nicht richtig.
Versucht hab ichs, die mit einem Zähler zu machen, aber da ist das
Problem, wenn ich nun ein Objekt (o2) wieder rechts vom bereits
entfernten Objekt (o1) entferne, erhöht sich der Zähler der Nachfolger
von o2 um noch eins (2) während die die links von o2 und rechts von o1
stehen gleich bleibt (1).
Bin da beim Rumüberlegen und weiss nicht weiter.

Wäre froh wenn ihr mir da weiterhelfen könnt (Pseudocode-Form) reicht
vollkommen aus.

vielen Dank im voraus

Markus Innerebner

[Sascha Broich]

Post by Markus Innerebner
Hallo ihr, ich grüble seit mehreren Stunden um mein Problem mit
Arbeite mit zwei LinkedList: LinkedListA, LinkedListB
Hierbei geht es darum, dass ich in einem Schleifendurchlauf je je ein
Element von LinkedListA nach LinkedListB verschiebe (also gleichzeitig
von LinkedListA lösche). Das Problem ist, dass ich beim Löschen auf den
Index des Elementes zugreifen muss. Mein Element-Objekte haben ein
ID-Attribut, durch welches ich notwendigerweise auf LinkedListA
zugreifen muss.

Wenn du sowieso mit IDs arbeitest, ist eine HashMap das Richtige.
Löse dich also von den Listen und denke mit Maps.

Sascha Broich

[Markus Innerebner]

Post by Sascha Broich
Wenn du sowieso mit IDs arbeitest, ist eine HashMap das Richtige.
Löse dich also von den Listen und denke mit Maps.
Sascha Broich

Hallo Sascha,
das kann ich eben nicht, denn ich muss mir anschliessend nachdem ich
eine bestimmte Anzahl an Objekten von LinkedListA nach LinkedListB
rüberverschoben hab, wieder beide verschmelzen, dass dies so aussieht
( LinkedListA_Part1, LinkedListB, LinkedListA_Part2 )
und dabei spielt die Reihenfolge die bedeutende Rolle.

[Sascha Broich]

Post by Markus Innerebner
Hallo Sascha,
das kann ich eben nicht, denn ich muss mir anschliessend nachdem ich
eine bestimmte Anzahl an Objekten von LinkedListA nach LinkedListB
rüberverschoben hab, wieder beide verschmelzen, dass dies so aussieht
( LinkedListA_Part1, LinkedListB, LinkedListA_Part2 )
und dabei spielt die Reihenfolge die bedeutende Rolle.

Und gleich in eine neue Liste kopieren geht nicht?

Alternativ schau dir mal LinkedHashMap an, die bietet einen Iterator, der
die Einfüge-Reihenfolge berücksichtigt.

Sascha Broich

[Sven Kiesewetter]

Post by Markus Innerebner
Hallo ihr, ich grüble seit mehreren Stunden um mein Problem mit
Arbeite mit zwei LinkedList: LinkedListA, LinkedListB
Hierbei geht es darum, dass ich in einem Schleifendurchlauf je je ein
Element von LinkedListA nach LinkedListB verschiebe (also gleichzeitig
von LinkedListA lösche). Das Problem ist, dass ich beim Löschen auf den
Index des Elementes zugreifen muss. Mein Element-Objekte haben ein
ID-Attribut, durch welches ich notwendigerweise auf LinkedListA
zugreifen muss. Da sich aber nach einem Löschvorgang alle Elemente in
der LinkedList, die rechts vom bereits entfernten Objekt stehen, sich
der Index um eins dekrementiert, ist die Zuweisung nicht richtig.
Versucht hab ichs, die mit einem Zähler zu machen, aber da ist das
Problem, wenn ich nun ein Objekt (o2) wieder rechts vom bereits
entfernten Objekt (o1) entferne, erhöht sich der Zähler der Nachfolger
von o2 um noch eins (2) während die die links von o2 und rechts von o1
stehen gleich bleibt (1).
Bin da beim Rumüberlegen und weiss nicht weiter.
Wäre froh wenn ihr mir da weiterhelfen könnt (Pseudocode-Form) reicht
vollkommen aus.
vielen Dank im voraus
Markus Innerebner

Ich kann deinen Ausführungen zwar nicht 100% folgen, aber folgender Code
sollte tun, was du willst:

LinkedList linkedListA = new LinkedList();
// mit Elementen füllen
LinkedList linkedListB = new LinkedList();
Iterator iA = linkedListA.iterator();
int i = 0;
while (iA.hasNext()){ // solche Elemente in Liste A
Object curr = iA.next(); // nächtes Element holen
iA.remove(); // altes Element aus Liste A löschen
linkedListB.add(curr); // rüberschieben
i++; // zählt, bei welchem Element du gerade bist
}

Sven

[Markus Innerebner]

Post by Sven Kiesewetter
Ich kann deinen Ausführungen zwar nicht 100% folgen, aber folgender
LinkedList linkedListA = new LinkedList();
// mit Elementen füllen
LinkedList linkedListB = new LinkedList();
Iterator iA = linkedListA.iterator();
int i = 0;
while (iA.hasNext()){ // solche Elemente in Liste A
Object curr = iA.next(); // nächtes Element holen
iA.remove(); // altes Element aus Liste A löschen
linkedListB.add(curr); // rüberschieben
i++; // zählt, bei welchem Element du gerade bist
}
Sven

Hallo Sven,
erstmal Danke für die Antwort,
so würde es auch gehen, aber da ich da sehr auf die Effizient wert lege,
kann ich das nicht machen.

beispiel:
entferne Objekt (o1) mit ID=10 aus LinkedListA,
nun muss ich linear das LinkedListA durchgehen und sobald die Bedingung
erfüllt ist dass ((Element)iA.next()).getID() = o1.getID() erfüllt ist,
hab ichs.
wenn ich nun im nächsten Durchlauf Objekt mit ID=5 entferne muss ich
nochmals iA durchlaufen und das wird dann zeitaufwendiger.
Ich versuch eben die Lösung für einen direkten Zugriff zu finden, was
mir eben bis jetzt noch nicht gelungen ist.

Grüße Markus

[Sven Kiesewetter]

Post by Markus Innerebner
Hallo Sven,
erstmal Danke für die Antwort,
so würde es auch gehen, aber da ich da sehr auf die Effizient wert lege,
kann ich das nicht machen.
entferne Objekt (o1) mit ID=10 aus LinkedListA,
nun muss ich linear das LinkedListA durchgehen und sobald die Bedingung
erfüllt ist dass ((Element)iA.next()).getID() = o1.getID() erfüllt ist,
hab ichs.
wenn ich nun im nächsten Durchlauf Objekt mit ID=5 entferne muss ich
nochmals iA durchlaufen und das wird dann zeitaufwendiger.
Ich versuch eben die Lösung für einen direkten Zugriff zu finden, was
mir eben bis jetzt noch nicht gelungen ist.
Grüße Markus

Dann haben Markus und Achim recht und LinkedHashMap ist dein Freund.

Sven

[Markus Innerebner]

Post by Sven Kiesewetter

Post by Markus Innerebner
Hallo Sven,
erstmal Danke für die Antwort,
so würde es auch gehen, aber da ich da sehr auf die Effizient wert
lege, kann ich das nicht machen.
entferne Objekt (o1) mit ID=10 aus LinkedListA,
nun muss ich linear das LinkedListA durchgehen und sobald die
Bedingung erfüllt ist dass ((Element)iA.next()).getID() = o1.getID()
erfüllt ist, hab ichs.
wenn ich nun im nächsten Durchlauf Objekt mit ID=5 entferne muss ich
nochmals iA durchlaufen und das wird dann zeitaufwendiger.
Ich versuch eben die Lösung für einen direkten Zugriff zu finden, was
mir eben bis jetzt noch nicht gelungen ist.
Grüße Markus

Dann haben Markus und Achim recht und LinkedHashMap ist dein Freund.
Sven

Hallo Sven,
hab nun den gesamten Vorgang mit LinkedHashMap gemacht, hab aber da
folgendes Problem:
LinkedHashMap lHM1, lHM2;

- bestimmte Elemente werden von lHM1 nach lHM2 verschoben //klappt.
- setze MinCOPOS = Stelle (in lHM2) mit dem kleinsten Wert
// Hierbei merk ich mir die kleinste Stelle, aus welchem ich aus lHM1
den kleinsten Wert rausgenommen hab ( denn genau ab hier wird dann mein
modifiziertes iHM2 eingefügt ).
- modifiziere ein Attributsinhalt jedes Elementes in iHM2
- füge als nächstes in iHM1 an der Stelle MINCOPOS-1 das gesamte iHM2 ein
// hier hab ich meine Probleme, denn ich weiss nicht, welcher
Vorgehensweise die richtige ist:
- Vorgehensweise 1:
Iterator it1 = iHM1.values().iterator();
while( it.hasNext() ) {
if( ((Element)it.next()).getCoPos() == MINCOPOS-1 )
iHM1.putAll(iHM2);
break;
}
// jetzt muss ich noch alle nachfolgenden Elemente, die nach dem
letzten Wert von iHM2 liegen (und die ja jetzt in iHM1 wieder drinnen
sind) mit einem neuen COPOS Wert aktualiesieren.
// nun weiss ich nicht, an welcher Stelle sich der itarator nach
dem Einfügen von iHM2 befindet.
// muss ich da von vorne nochmals durchgehen, um an die Stelle in
iHM1 zu gelangen, an welche ich das letzte Element aus iHM2 eingefügt
hatte.

- Vorgehenswiese 2:
if( iHM1.containsKey(new Integer(minCOPOS-1)) )
iHM1.putAll(iHM2);
// wird jetzt iHM2 nach der letzten Stelle iHM1 eingefügt,
oder genau an der Stelle, die ich zwei Zeilen davor abgefragt hab.

Grüße und ein großes Dankeschön
Markus

[Achim Peters]

Post by Markus Innerebner
Arbeite mit zwei LinkedList: LinkedListA, LinkedListB
Hierbei geht es darum, dass ich in einem Schleifendurchlauf je je ein
Element von LinkedListA nach LinkedListB verschiebe (also gleichzeitig
von LinkedListA lösche). Das Problem ist, dass ich beim Löschen auf den
Index des Elementes zugreifen muss.

Wieso musst Du das? LinkedList hat auch remove(Object o).

Post by Markus Innerebner
Mein Element-Objekte haben ein
ID-Attribut, durch welches ich notwendigerweise auf LinkedListA
zugreifen muss. Da sich aber nach einem Löschvorgang alle Elemente in
der LinkedList, die rechts vom bereits entfernten Objekt stehen, sich
der Index um eins dekrementiert, ist die Zuweisung nicht richtig.

Welche Zuweisung?

Post by Markus Innerebner
Wäre froh wenn ihr mir da weiterhelfen könnt (Pseudocode-Form) reicht
vollkommen aus.

while (moreIdsExist())
{
Object o = getElementWithID(linkedListA, getNextID());
linkedListB.add(o);
linkedListA.remove(o);
}

Ich empfehle trotzdem wie Sascha eine Map-Datenstruktur, z. B. die
LinkedHashMap (ab Java 1.4.)

HTH

Achim

[Markus Innerebner]

Post by Achim Peters
Ich empfehle trotzdem wie Sascha eine Map-Datenstruktur, z. B. die
LinkedHashMap (ab Java 1.4.)
HTH
Achim

Hi Achim,
nun hab ich LinkedHashMap als Datenstruktur verrwendet, wobei mir da
noch einiges bzgl. Reihenfolge unklar ist.
hab zwei
LinkedHashMap lHM1, lHM2;

- bestimmte Elemente werden von lHM1 nach lHM2 verschoben //klappt.
- setze MinCOPOS = Stelle (in lHM2) mit dem kleinsten Wert // Hierbei
merk ich mir die kleinste Stelle, aus welchem ich aus lHM1 den kleinsten
Wert rausgenommen hab ( denn genau ab hier wird dann mein modifiziertes
iHM2 eingefügt ).
- modifiziere ein Attributsinhalt jedes Elementes in iHM2
- füge als nächstes in iHM1 an der Stelle MINCOPOS-1 das gesamte iHM2 ein
// hier hab ich meine Probleme, denn ich weiss nicht, welcher
Vorgehensweise die richtige ist:
- Vorgehensweise 1:
Iterator it1 = iHM1.values().iterator();
while( it.hasNext() ) {
if( ((Element)it.next()).getCoPos() == MINCOPOS-1 )
iHM1.putAll(iHM2);
break;
}
// jetzt muss ich noch alle nachfolgenden Elemente, die nach dem
letzten Wert von iHM2 liegen (und die ja jetzt in iHM1 wieder drinnen
sind) mit einem neuen COPOS Wert aktualiesieren.
// nun weiss ich nicht, an welcher Stelle sich der itarator nach
dem Einfügen von iHM2 befindet.
// muss ich da von vorne nochmals durchgehen, um an die Stelle in
iHM1 zu gelangen, an welche ich das letzte Element aus iHM2 eingefügt
hatte.
- Vorgehenswiese 2:
if( iHM1.containsKey(new Integer(minCOPOS-1)) )
iHM1.putAll(iHM2);
// wird jetzt iHM2 nach der letzten Stelle iHM1 eingefügt, oder
genau an der Stelle, die ich zwei Zeilen davor abgefragt hab.

Grüße und ein großes Dankeschön
Markus

[Albert Uerz]

Hi Markus,

hier findest Du Grundlagen über Datenstrukturen, es ist wirklich sehr
empfehlenswert:

http://www-lehre.inf.uos.de/~ainf/2003/skript/skript.html

Post by Markus Innerebner
Arbeite mit zwei LinkedList: LinkedListA, LinkedListB
Hierbei geht es darum, dass ich in einem Schleifendurchlauf je je ein
Element von LinkedListA nach LinkedListB verschiebe (also gleichzeitig
von LinkedListA lösche). Das Problem ist, dass ich beim Löschen auf den
Index des Elementes zugreifen muss.

Muß man das? Wenn Du die Objekte verschiebst, bleibt die ObjektID die
gleiche. Du könntest also so vorgehen:

// Liste 1
LinkedList l1 = new LinkedList();
Iterator itl = l1.iterator();
// Liste 2
LinkedList l2 = new LinkedList();
...

// initialisieren der Variablen
Object o = null;
int index = -1;

while (itl.hasNext()){
...
index = l.indexOf(itl.next()); //merken,wenn es das gesuchte Objekt ist
o = l.get(index); //Objekt sichern

if( Eigenschaft von o){ // ist es das gesuchte Objekt?
...
}else {index = -1;} // nein, bleibt in Liste 1

if (index > 0){
l2.add(o); //Objekt an Liste 2 anhängen
l.remove(o); //Objekt aus Liste 1 entfernen
index = -1; //reinitialisieren
}//if
...
}//while
...


Ich hoffe, ich hatte Deine Frage richtig verstanden.

Bis denne
Albert aus dem bewlkten Bad Fallingbostel

[Markus Innerebner]

Post by Albert Uerz
LinkedList l1 = new LinkedList();
Iterator itl = l1.iterator();
// Liste 2
LinkedList l2 = new LinkedList();
...
// initialisieren der Variablen
Object o = null;
int index = -1;
while (itl.hasNext()){
...
index = l.indexOf(itl.next()); //merken,wenn es das gesuchte Objekt ist
o = l.get(index); //Objekt sichern
if( Eigenschaft von o){ // ist es das gesuchte Objekt?
...
}else {index = -1;} // nein, bleibt in Liste 1
if (index > 0){
l2.add(o); //Objekt an Liste 2 anhängen
l.remove(o); //Objekt aus Liste 1 entfernen
index = -1; //reinitialisieren
}//if
...
}//while
...
Ich hoffe, ich hatte Deine Frage richtig verstanden.
Bis denne
Albert aus dem bewlkten Bad Fallingbostel

Hallo Albert.
danke für die Antwort .
Das Problem ist, dass die Laufzeit das wichtigste Kriterim ist.
Wenn ich also Objekt o1 mit id 3000 aus LinkedList1 entferne, aber beim
nächsten mal Objekt o2 mit id = 1500 brauch, muss ich wieder mit next
oder previous LinkedList1 durchgehen, bis ich es gefunden hab. Da ich
mit über 500 000 Objekten arbeite, wird die ganze Sache etwas aufwendig.

Aber, danke dennoch für deinen Vorschlag.

Markus

[Albert Uerz]

Hi Markus,

dann stellt Dir mal die Frage, was eine Liste darstellt (rethorisch
natürlich ;-> )
Antwort: Eine Liste ist ein degenerierter Baum, Beispiel:
füge mal die Elemente schon sortiert in einen Baum, dann kommt eine
Liste heraus.
Du kannst die Laufzeit also bei einem Baum auf O(log n) im Average case
beschränken.

Sieh Dir mal die Seite an, die ich Dir postete.

Übrigens, man kann auch diese Datenstrukturen "unabhänig" voneinander
gestalten:
Elemente in der einen und den Index mit einem Verweis auf die Positionen
in einer anderen Datenstruktur (B-Baum, Hashtable,Bit-Listen, ...).

Eine Liste, die nicht doppelt verkettet ist, mußt Du sowieso immer von
Anfang an durchlaufen. Wenn es unbedingt eine Liste (kein Baum) sein
soll, so macht es auch Sinn, diese immer sortiert und doppelt verkettet
zu haben, dann kannst Du auch binär in der Liste suchen (Divide and
Conquer-Verfahren,...)
Steht alles mit Beispielen in der Datenstrukturen/Algorithmen Vorlesung :-)

Bis denne Albert

Post by Markus Innerebner

Post by Albert Uerz
LinkedList l1 = new LinkedList();
Iterator itl = l1.iterator();
// Liste 2
LinkedList l2 = new LinkedList();
...
// initialisieren der Variablen
Object o = null;
int index = -1;
while (itl.hasNext()){
... index = l.indexOf(itl.next()); //merken,wenn es das gesuchte
Objekt ist
o = l.get(index); //Objekt sichern
if( Eigenschaft von o){ // ist es das gesuchte Objekt?
...
}else {index = -1;} // nein, bleibt in Liste 1
if (index > 0){
l2.add(o); //Objekt an Liste 2 anhängen
l.remove(o); //Objekt aus Liste 1 entfernen
index = -1; //reinitialisieren
}//if
...
}//while
...
Ich hoffe, ich hatte Deine Frage richtig verstanden.
Bis denne
Albert aus dem bewlkten Bad Fallingbostel

Hallo Albert.
danke für die Antwort .
Das Problem ist, dass die Laufzeit das wichtigste Kriterim ist.
Wenn ich also Objekt o1 mit id 3000 aus LinkedList1 entferne, aber beim
nächsten mal Objekt o2 mit id = 1500 brauch, muss ich wieder mit next
oder previous LinkedList1 durchgehen, bis ich es gefunden hab. Da ich
mit über 500 000 Objekten arbeite, wird die ganze Sache etwas aufwendig.
Aber, danke dennoch für deinen Vorschlag.
Markus