Verkettete Listen

[Usarian]

Hallo schon wieder Ich hab Probleme mit 'ne Aufgabe und zwar:

Aus einer einfach-verketteten Liste soll eine doppelt-verkettete Liste erstellt werden. Führen Sie dazu folgende
Schritte aus:
• Implementieren Sie für die aus der Vorlesung bekannte doppelt-verkettete Liste DList die Methoden
insertFirst, insertLast und delete.
• Erstellen Sie eine einfach-verkettete Liste mit den Elementen 1, 7, 3, 5, 2, 9.
• Wandeln Sie die einfach-verkettete Liste in eine doppelt-verkettete Liste um!
• Lassen Sie sich anschließend die doppelt-verkettete Liste ausgeben, inklusive Minimum und Maximum.
• Führen Sie auf der doppelt-verketteten Liste die Operationen delete(9), insertLast(14),
delete(0), insertFirst(-5) und delete(3) aus.
• Lassen Sie sich abschließend die resultierende doppelt-verkettete Liste ausgeben.

Da hab ich mich schon einige Tage damit beschaeftigt, aber da kriege ich es immer noch nicht her.
Also die aus der Vorlesung bekannte doppelt-verkettet Liste DList ist:

class DList {
DNode head, last; // erstes und letztes Listenelement
DList() {head = null; last = null;}
// weitere Methoden siehe etwa wie nachfolgende
   . . .
   String toStringInverse(){ // Zeichenkette für invertierte Liste
if(head == null)  // Trivialfall: Leere Liste 
return ''( )'';
String s = ''('';
DNode tmp = last;// ans Ende der Liste gehen
while(tmp != null){
s = s + tmp.data + '' '';
tmp = tmp.prev;
}
s = s + '')'';
return s;
    }   
}

Fuer die insertFirst Methode hab ich so was herausgedacht, bin aber ueberhaupt nicht sicher ob es stimmt und was es bedeutet (hab ich es in ein Java Programmierbuch gefunden)

public void insertFirst(int data) {
    Element n = new Element(data);
    n.next = last;
    last = n;
  }

Also das hier sollte meine insertLast Methode sein. Das verstehe ich schon, aber ich bin nicht sicher ob ich es auch fuer doppelt-verkettete Listen benutzen darf.

public void insertLast(Object item) {
if (head == null) {
// Wir haben eine leere Liste
head = new DNode(item);
last = head;
} else {
// Wir haben eine nichtleere Liste
DNode newDNode = new DNode(item, last);
last = newDNode;
}
count++;
}

Und fuer die delete Methode hab ich gar keine Ahnung wie ich diese erzeugen kann. Ausserdem wie erstelle ich eine einfach-verkaettete Liste und wie fuelle ich diese mit Zahlen(darf ich das in meine main Methode machen oder soll ich noch eine Methode extra schaffen, damit ich meine Liste mit Zahlen fuelle?) Und noch was. Wie bekomm ich aus eine einfach-verkettete Liste eine doppelt-verkettete Liste?

Huh es wurde ein langes Thema daraus Aber ich weiss echt nicht was ich machen muss.

Herzlichen Dank im voraus.

 

[DamienX]

Also hier
Doubly linked list (Java) - LiteratePrograms

gibts ne komplette Implementierung einer Double Linked List.
(Ich geh hier mal davon aus dass du weist was das ist.)

Das einzige Problem ist der Generic "<E>". Die kannste aber auch weglassen und in
den Klassen statt dem Typen E auch einfach Integer benutzen. Dann klappt das
auch.

Der Autor is bemüht das bewährte Knotensystem zu implementieren. Wenns an grundsätzlichem
hapert musst du leider genauer werden (Welche zusammenhänge bleiben dir verschlossen?).

EDIT: Die DNode Klasse wäre auch hilfreich da du ja bestehenden source anpassen sollst.

Mfg Alex

 

[Usarian]

Vielleicht ist diese Methode fuer insertLast besser?:

private DNode last = null;

  // private DNode ende = null;

  public void insertLast(int data) {
    if (last == null) {
      last = new DNode(data);
    } else {
      // suche Ende
      DNode e = last;
      while (e.next != null) {
        e = e.next;
      }
      // e ist das letzte DNode (Ende)
      e.next = new DNode(data);
    }
  }

 

[Usarian]

Naja nach einige Stunden muehe hab ich folgendes da liegen:

class Listen {
	
	class DNode {
		public static final int val = 0;
		int data;
		DNode element;
		DNode next, prev;
		DNode(int d) {data = d; prev = null; next = null;}
		DNode(int d, DNode p, DNode n){
		data = d; prev = p; next = n; }
		}
	
	
	public void insertFirst(int data) {
	    DNode n = new DNode(data);
	    n.next = last;
	    last = n;
	  }

	  // private DNode ende = null;
	 
	  public void insertLast(int data) {
	    if (last == null) {
	      last = new DNode(data);
	    } else {
	      // suche Ende
	      DNode e = last;
	      while (e.next != null) {
	        e = e.next;
	      }
	      // e ist das letzte DNode (Ende)
	      e.next = new DNode(data);
	    }
	  }
	
	  DNode head, last; // erstes und letztes Listenelement
	  Listen() {head = null; last = null;}
	  	// weitere Methoden siehe etwa wie nachfolgende
   
	    
	  
	  public void printList() {
		    System.out.print("[");
		    for (DNode e = last; e != null; e = e.next) {
		      System.out.print(e.data + " ");
		    }
		    System.out.println("]");
		  }

	  
	  


	  public static void main(String[] args) {
		  
		  Listen liste = new Listen();
		  liste.insertLast(new Integer(1));
		  liste.insertLast(new Integer(7));
		  liste.insertLast(new Integer(3));
		  liste.insertLast(new Integer(5));
		  liste.insertLast(new Integer(2));
		  liste.insertLast(new Integer(9));
		  liste.printList();
		  liste.delete(3);
		  liste.printList();
		  
	  }
}

Jetzt funktionieren beide Methode, aber ich hab immer noch keine Ahnung wie ich die delete Methode machen kann ???:L Koennte mir jemand bisschen helfen?

Ausserdem bin ich nicht sicher ob ich das richtig gemacht hab:

• Erstellen Sie eine einfach-verkettete Liste mit den Elementen 1, 7, 3, 5, 2, 9.

Aus dem obestehenden Quellcode bekomme ich folgendes als Ausgabe:

[1 7 3 5 2 9 ]

 

[Usarian]

Könnte mir niemand bisschen weiter helfen?

 

[Firestorm87]

Du musst den zu löschenen Knoten ausfindig machen, wovon du dann ja zugriff auf den Knoten davor und danach hast...

Und hier musst du dann nur die referenzen tauschen.... (d = zu löschen; p = knoten davor; a = knoten danach)
1) Suche d.
2) p = d.prev
a = d.next
3) p.next = a
a.prev = p

So in etwa

/EDIT: oder:
1) suche d
2) d.prev.next = d.next
d.next.prev = d.prev

 

[SlaterB]

hast du denn eine Vorstellung von der Liste?
auf Papier schonmal Rechtecke pro Node aufmalt und Linien für die Verlinkungen?
fürs Löschen musst du doch nur den Link vom Vorgänger auf den Übernächsten setzen, schon ist einer ausgelassen,

war dir das nicht klar oder gehts jetzt ums Programieren, was ist das aktuelle Problem?
(auch Spezialfälle wie Löschen am Anfang/ Ende bedenken und testen)

 

[Usarian]

Naja ich weis wie ich es machen muss. Wie du gesagt hast hab ich's auch gemalt, aber ich kann es einfach in eclipse nicht kriegen. Also das Ding nicht implementieren.

 

[Firestorm87]

Ich versteh nur bahnhof... was kriegst du in eclipse nicht hin?
Die Methode deklarieren, die Nodes ansprechen, die Referenzen tauschen?

 

[Usarian]

Ich krieg die delete Methode nicht funktionierend. Jetzt bekomm ich folgendes als Ausgabe:

[1 7 3 5 2 9 ]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Invalid index: 3
	at Listen.remove(Listen.java:101)
	at Listen.main(Listen.java:137)

Und das ist meine main Methode:

public static void main(String[] args) {
		  
		  Listen liste = new Listen();
		  liste.insertLast(new Integer(1));
		  liste.insertLast(new Integer(7));
		  liste.insertLast(new Integer(3));
		  liste.insertLast(new Integer(5));
		  liste.insertLast(new Integer(2));
		  liste.insertLast(new Integer(9));
		  liste.printList();
		  liste.remove(3);
		  liste.printList();
		  
	  }

Und das soll meine delete Methode sein:

public DNode remove(int index) {
		  
		if (index>=length || index<0) {
			  throw new IndexOutOfBoundsException(
					  "Invalid index: " + index);
		  }
		  // Element mit index finden
		  	int currentIndex = 0;
		  	DNode currentNode = head;
		  	DNode prevNode = null;
		  		while (currentIndex < index) {
		  			prevNode = currentNode;
		  			currentNode = currentNode.next;
		  			currentIndex++;
		  		}
		  // Entfernen des elements
		  	length--;
		  		if (length==0) {
		  			head = null;
		  			last = null;
		  		} else if (prevNode == null) {
		  			head = currentNode.next;
		  		} else {
		  			prevNode.next = currentNode.next;
		  		}
		  		return (DNode) currentNode.element;
		 	 }

 

[Firestorm87]

Die Exception (also deine Fehlermeldung) verursachst du selber

if (index>=length || index<0) {
              throw new IndexOutOfBoundsException(
                      "Invalid index: " + index);
          }

Dabei sei die Frage gestattet was ist die Variable "length"

 

[SlaterB]

so einen Stand schreibst du hier ins Forum?
denk doch bitte vorher etwas darüber nach, worum es dann bei diesem Problem geht, was du selber noch beitragen kannst

vollkommen vorhersehbare Antwort:
- die Exception ist offensichtlich von dir selber am Anfang der Methode
- niemand hier kennt length, das tauchte in deinem bisherigen Codes gar nicht auf
- in jedem Fall kannst du doch selber locker leicht klären, warum der Index 3 unverständlicherweise größer als length ist,
logge doch nach jedem Einfügen und besonders vor dem Löschen den Wert von length (System.out.println),
wenn der nicht ordentlich gesetzt ist, dann musst du erstmal dieses Problem lösen, über delete() gar nicht nachdenken

so, diese Minuten hätten wir uns alle sparen können, erst denken dann weitermachen

(edit: sogar schon zu spät, alles nimmt seinen Lauf )

 

[Usarian]

lenght sollte eigentlich die laenge meiner Liste sein. Achso ja stimmt! Danke

 

[SlaterB]

ich hoffe, das war nur auf Firestorm87 bezogen,
siehe meine Antwort was du alles noch schreiben musst, bevor es weitergeht