Hallo Leute,
Ich muss eine Methode implementieren mit der ich einer verketteten Liste neue Elemente an einer gewünschten Stelle einfüge. Die Methode soll insertPos(Object o, int index) heißen und man muss ihm in der Methode die Parameter o (gewünschter Inhalt des Elementes) und index (gewünschte Stelle, an der o eingefügt werden soll) übergeben.
In der Theorie ist mit alles klar: Ich muss mit einer Schleife die Liste bis index durchlaufen, an der Stelle index muss ich dann eine Kopie des gewünschten Nachfolgers erstellen, dann die Referenz des vorherigen Elementes auf mein Element zeigen lassen und schließlich den Inhalt meines Elementes mit dem gewünschten Inhalt o überschreiben. (Falls meine Überlegung falsch ist, bitte ich um Verbesserung)
Ich hänge jetzt nun wie so oft am eigentlichen Implementieren der Methode, sei es nun wegen Mangel an Befehls-Kenntnisse oder Nichtüberlegung von bestimmten wichtigen Dingen.
Mein bisheriger Quellcode der Methode:
public void insertPos(Object o, int index) {
if(index>=0){
for(int i = 0; i<= index;i++){
o = new LinkedList(index, next);
o = index;
}
}
}
Ich hoffe einer von euch kann mich auf die Sprünge bringen. Danke im Voraus.
LG ElifOzt
also erstens ist die abfrage ob index >= 0 sinnfrei weil die vorschleife die selbe bedingung hat und somit
gar nicht ausgeführt werden würde.
wo ist denn genau der fehler?
eine exception?
was ist das ergebnis?
linkedlist modelliert dann auch ein element in der liste, sehe ich das richtig?
wieso versuchst du einem object ein int zuzuweisen? bzw was willst du damit erreichen?
du hast doch die theorie schon beschrieben, aber das steht nicht in deinem code,
oder sehe ich das falsch?
Das if() ist redundant - es stellt sicher dass der Index nicht negativ ist. Das macht aber auch der for-Loop der als Bedingung hat das i kleiner oder gleich dem index sein muss. Ergo: wenn i mit 0 beginnt kann index nicht kleiner 0 sein - sonst wird der for-Loop garnicht erst ausgeführt.
Als nächstes würde ich mal versuchen was passiert wenn du deine Parameter als final meldest.
Und zum Schluss: dein Code kann schon alleine wegen Type-Mismatch nicht compilen da du versuchst einem Object einen int zuzuweisen.
Auch haut deine Grundidee nicht hin.
In einer LinkedList hält das aktuelle Entry eine Referenz auf seinen Nachfolger, dieser kennt aber nicht seinen Vorgänger (das wäre dann eine DoubleLinkedList).
Du brauchst also nicht erst eine Kopie des aktuellen Elements erstellen und die aktuelle überschreiben. Du musst nur den Pointer auf den Nachfolger entsprechend anpassen.
Dabei musst du dann aber genau bestimmen ob “einfügen bei Pos 10” dann meint “this ist neu Pos 10” oder “this wird an Pos 10 angehängt” bedeutet. Beides gibt es und ist recht einfach umzusetzen. Mit dem Überschreiben des aktuellen Elements hat aber beides nichts zu tun.
[quote=ElifOzt]Mein bisheriger Quellcode der Methode:[/quote]Falls es dir noch niemand gesagt hat: Namen von Parametern und (lokalen) Variablen darf man jederzeit so umbenennen, das man selbst versteht wofür sie da sind.
Also benenne doch bitte mal den Parameter o (mit Hilfe deiner IDE!!!) um zu einzufuegendesObjekt. Und dann schau Dir noch mal die Zeilen 6 und 7 an (auf die die Umbenennung auch wirken sollte)…
Hm. Die Zuweisungen ganz innen machen nicht viel Sinn. Poste am besten mal die Klasse, wo die Methode drinsteht (und die vermutlich “LinkedList” heißt). Das kritisch(st)e ist ja, wenn das Element an index 0 eingefügt werden muss…
EDIT: Wie kann es sein, dass es schon 3 Antworten gibt, für einen Post, den ich gerade eben erst freigeschaltet habe?!
Also ich habe jetzt die if Anweisung gelöscht, hab auch dann gesehen, dass es gedoppelt war.
Und auch den Tipp mit dem einzufuegendesElement hab ich umgesetzt und merke gerade, dass es wirklich nicht sehr viel Sinn macht, dem Index mein Inhalt zuzuweisen.
Ich bin nur gerade etwas verwirrt weil wir in der Vorlesung irgendwie das mit Überschreiben hatten, allerdings war das beim aller ersten Element, wahrscheinlich kann man es nur da verwenden. Naja aber ich weiß jetzt auch irgendwie nicht weiter…
Mein Quellcode jetzt:
private Object item;
private LinkedList next;
public LinkedList() {
}
private LinkedList(Object i, LinkedList n) {
item = i;
next = n;
}
public Object insertfirst(Object elem) {
next = new LinkedList(item, next);
return item = elem;
}
public Object insertlast(Object elem) {
if (item == null) {
item = elem;
next = new LinkedList();
} else
next.insertlast(elem);
return elem;
}
public Object removefirst() {
if (item != null) {
Object res = item;
item = next.item;
next = next.next;
return res;
}
return null;
}
public Object removelast() {
return (item == null) ?
null : (next.item == null) ? removefirst() :
next.removelast();
}
public Object search(Object elem) {
return (item == null) ?
null : (item.equals(elem)) ? item :
next.search(elem);
}
public String toString() {
return (item == null) ? "" : item.toString() + " " +
next.toString();
}
public void insertPos(Object einzufuegendesElement, int index) {
for(int i = 0; i<= index;i++){
einzufuegendesElement = new LinkedList(index, next);
einzufuegendesElement = index;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertfirst(2);
list.insertlast(4);
list.insertfirst(1);
list.insertlast(5);
list.insertPos(3, 2);
System.out.println(list); // 1 2 3 4 5
}
}
*** Edit ***
Ups, da hat wohl etwas mit dem Einfügen des Codes nicht geklappt Hoffe ihr könnts trotzdem verstehen
[quote=ElifOzt]Ich bin nur gerade etwas verwirrt weil wir in der Vorlesung irgendwie das mit Überschreiben hatten, allerdings war das beim aller ersten Element, wahrscheinlich kann man es nur da verwenden.[/quote]Schau dir doch die beiden Methoden noch mal genauer an: public Object insertfirst(Object elem) { next = new LinkedList(item, next); return item = elem; } public void insertPos(Object einzufuegendesElement, int index) { for(int i = 0; i<= index;i++){ einzufuegendesElement = new LinkedList(index, next); einzufuegendesElement = index; } }was fällt Dir auf?
[quote=ElifOzt]Achso ja das mit next muss verändert werden oder?
Aber wie soll ich denn das mit dem index und dem Objekt machen?[/quote]Der index wird in der Struktur überhaupt nicht gespeichert. Der dient nur zum abzählen, was Du mit der for Schleife schon erledigt hast.
Im übrigen sollte die neue Methode der alten viel ähnlicher sein.
Achso, ja das ist mir klar, aber ich weiß nicht wie ich das speichern muss. Bei Arrays würde ich da ja die eckigen Klammern benutzen, aber bei Linked lists ist mir die Implementierung überhaupt nicht bekannt oder ich kann nicht soweit denken
[quote=ElifOzt]Wie gesagt, ich habe Probleme damit meine Gedanken zu Code zu verwandeln. Ich weiß nicht genau welche Befehle ich verwenden muss usw.[/quote]Wo her kommt dann der Code in insertPos()?
Fang noch mal bei meinem Post #7 an.
Mach Dir Zeile für Zeile klar was in der ersten Methode passiert, und wie die zweite davon abweicht.
Also eine linked-List funktioniert prinzipiell so: Du hälst den ersten Knoten in der Hand.
Jedes Knoten besteht aus einer “Nutzlast” (Variable item) und einem Zeiger auf den nächsten Knoten (Variable next).
Die beiden Extremfälle sind einfach, weill man die Kette der Knoten nicht unterbricht.
Du hast (wie Du richtig erkannt hast) 4 Teilaufgaben:
Finde den ListenKnoten, nach dem der neue Knoten eingefügt werden soll.
Erzeuge den neuen Knoten.
hänge den Rest der Liste (also das worauf next des gefundenen Knotens Zeigt) an den neuen Knoten.
hänge des neuen Knoten an den gefundenen.
Was macht Dein Code?
Er zählt alle Indexe bis zur gewünschten Stelle, tut aber nichts mit der Liste selbst.
An dieser Stelle würde ich den Code löschen und noch mal von vorn anfangen.
Erzeuge erst mal ein paar zusätzliche lokale Variablen:
[ul]
[li]Eine für den aktuellen Knote der Liste, den wir gerade betrachten und der potentiell der Vorgänger des neuen Knotens sein könnte.
[/li][li]Eine für den neuen Knoten.
[/li][/ul]
Wenn Du das hast melde Dich noch mal…
@TO
Das was du da an Code hast geht eher in Richtung eines Tree anstatt als eine List.
Was ist dein Hauptproblem? Das du nur eine Klasse hast mit der du alles machen willst. Das kann so schon mal gar nicht hinkommen. Denn du hast einmal die Liste an sich als Datenstruktur und du hast die jeweiligen Elemente innerhalb dieser Liste.
In der List selbst hält man nur eine Referenz auf den ersten Knoten in der Liste, und die Info auf den nächsten Knoten dann in diesem ersten Knoten. Den letzten Knoten definiert man dadurch dass dessen next-Referenz entweder NULL ist oder wieder auf den ersten Knoten zeigt (gibt da verschiedene Implementierungen mit verschiedenen Namen).
Also bauen wir mal folgende Grundstruktur komplett from scratch:
{
private LinkedList<T>.Entry<T> first=null;
private class Entry<T>
{
private Entry<T> next=null;
private T payload=null;
}
}```
Dazu passende Konstruktor, Setter und Getter und man hat erstmal ein Grundgerüst dem man Elemente hinzufügen kann und die man auch wieder aus der Liste heraus bekommt. Für den Anfang würde ich erstmal nur add(Object) und get(int) implementieren. Und dann weiter mit dem was du eigentlich vor hast: add(int, Object) (um sich an java.util.List zu orientieren, der Name insertAt() oder ähnlich wäre halt ungewöhnlich).
[QUOTE=Sen-Mithrarin]@TO
Das was du da an Code hast geht eher in Richtung eines Tree anstatt als eine List.[/QUOTE]
Nein. Deine Variante, wo die Liste interne Knoten besitzt, mag für veränderliche Listen die üblichere Implementierung sein, für unveränderliche Listen wäre die vom TO verwendete Version (wo die Liste selbst eine Datenstruktur aus Wert und Restliste ist) Standard (siehe z.B. https://github.com/functionaljava/functionaljava/blob/master/core/src/main/java/fj/data/List.java ) und auch für veränderliche Listen ist diese Struktur möglich.
@Landei
Mag vielleicht dran liegen dass ich beim Versuch einen einfachen Tree zu implementieren kläglich gescheitert bin und daher durchaus einiges durcheinander bringe.
Hoffe ihr könnts trotzdem verstehen