Doppelt verkettete Liste

[Bodo1981]

Bin gerade dabei eine Buchverwaltung zu schreiben und bin dabei auf die Idee einer doppelt verketteten Liste gestoßen. Ich habe mich auch schon versucht hier im Forum und auf anderen diversen Seiten schlau zu machen, wie das Grundgerüst einer solche Liste aussieht, hab aber nichts passendes gefunden.

Des wegen wäre meine Frage: Kann mir einer von euch bitte einen Quellcode zeigen, wie ich eine solche doppelt verkettete Liste aufbauen muss. Will auch keine komplette Lösung, sondern nur wie gesagt das Grundgerüst. Aber ein Quellcode sollte es schon sein.

Wär euch echt sehr dankbar.

 

[SamHotte]

Google ist dein Freund:

Suchterm: Algorithmus doppelt verkettete Liste Quellcode

Treffer Nr. 2 (man muss dann etwa 3 Sekunden lesen): Quellcode

 

[Leroy42]

Bin gerade dabei eine Buchverwaltung zu schreiben...

Hört sich nicht an als ob es eine Aufgabenstellung wäre eine Liste selbst zu implementieren.

In dem Fall nutze doch einfach die Klassen, die Java dafür von Haus aus mitbringt
und die du imn java.util package findest.

 

[Bodo1981]

leider doch. ich muss die liste selbst implementieren. hab mir den quellcode auch gerade angeschaut, aber irgendwie komm ich damit nicht klar. Kann mir irgendjemand einen ganz einfachen Quellcode schreiben, wie das grundgerüst einer doppelt verketteten liste auszusehen hat.

Sehr hilfreich wäre auch noch wie das mit dem Buch dann geht. Die Aufgabenstellung sagt, das der Knoten Buch den Buchtitel, den Autor sowie Referenzen auf den vorhergehenden und nachfolgenden Knoten enthält. Der Quellcode sollte gut kommentiert sein, damit ich das mal verstehe. ich bin zwar kein java anfänger mehr, aber das mit den verketteten listen (vor allem doppelt) bekomm ich noch nicht ganz auf die reihe.

 

[Leroy42]

class BuchNode {
	String titel;
	String autor;
	BuchNode next;
	BuchNode prev;
	...
}

class DLList {
	BuchNode first;
	BuchNode last;
	
	public void insert(String autor, String titel) {...}
	public void delete(BuchNode buch) {...}
}

Das ist das Gerüst. Welche Funktionen du implementieren mußt,
weiß ich nicht. Und implementieren solltest du sie schon selbst versuchen.

Falls es dabei Schwierigkeiten gibt, kannst du ja gezielt nachfragen.

 

[Bodo1981]

Eine Frage hätte ich da schon noch:

Was muss denn noch alles in die Klasse BuchNode wo du die Punkte hast. Irgendwie steig ich da echt nicht durch.

Achja und kann ich die Klasse BuchNode auch in die Klasse DLList hineinschreiben?

 

[Leroy42]

Was muss denn noch alles in die Klasse BuchNode wo du die Punkte hast.

Eigentlich gar nichts mehr. Die Punkte stehen für Attribute/Methoden die du eventuell noch hast.

Achja und kann ich die Klasse BuchNode auch in die Klasse DLList hineinschreiben?

Yep, da gehört sie eigentlich auch rein. Dann mußt du sie aber statisch machen, damit
nicht jeder Node einen (internen) Zeiger auf die umgebende DLList hat.

Ich schreib dir mal als Beispiel die insert-Methode.

public void insert(String autor, String titel) {addLast(autor, titel);}
public void addLast(String autor, String titel) {
  BuchNode buch = new BuchNode(autor, titel);
  buch.prev = last;
  buch.next = null;
  if (last == null)
    first = buch; // Liste war bisher leer
   else 
    last.next = buch; // Das bisher letzte Buch hat jetzt einen Nachfolger
  last = buch;
}

 

[Bodo1981]

Merci dir. Hab jetzt alles soweit ganz gut hinbekommen, nur mit der Ausgabe haut es irgendwie nicht so ganz hin. Ich hoffe das ist die letzte Hilfe die ich von dir brauche. achja und kennst du vielleicht ein gutes tutorial über verkettete listen, denn ich will endlich mal meine wissenslücken schließen

 

[Leroy42]

Sorry, muß los...

 

[Bodo1981]

kann ich das eigentlich auch so machen, das ich gleich so einfüge, das die Liste nach den Autoren alphabetisch sortiert ist. also z.b ich hab eine bisherige liste mit folgenden autoren:

Bertold Brecht
Grass Günter
Zitzmann Jürgen

und jetzt kommt ein neuer Autor mit Buch hinzu: z.B. Deutinger Harald und der soll gleich zwischen Bertold Brecht und Grass Jürgen eingefügt werden

 

[Leroy42]

Sicher!

Du setzt einen Zeiger auf den aktuellen Listenanfang und setzt
ihn solange auf den Nachfolger, wie das einzufügende Element lexikalisch
kleiner als das aktuelle ist und es überhaupt noch einen Nachfolger
gibt.

Wenn die Schleife, aufgrund der eben genannten Kriterien, beendet ist,
weißt du wo das neue Element einzufügen ist. Jetzt noch ein bischen
Zeiger-jonglieren und fertig.

Probier's am besten mal auf dem Papier mit ein paar Elementen aus
um die Sonderfälle (leere Liste, ...) zu erkennen und um zu sehen,
welcher Zeiger von welchen Elementen wie verbogen werden müssen.

 

[Bodo1981]

So hier mal mein einigermaßen fertiges Programm:

public class Buchverwaltung {

	public class BuchNode{
		String buchtitel;
		String autor;
		BuchNode prev;
		BuchNode next;
		
		BuchNode(String titel, String verfasser){
		buchtitel = titel;
		autor = verfasser;
		}
	}
	
	BuchNode first;
	BuchNode last;
	int count = 0;
	
	/** Methode um einen neuen Knoten in die Liste
	 *  lexikographisch einfügen
	 */
	public void insert(String titel, String autor){
		BuchNode buch = new BuchNode(titel, autor);		// Erzeugen eines neuen BuchKnotens
		
		// falls die Liste leer war
		if (first == null){
			buch.prev = buch;
			buch.next = null;
			first = buch;
		}
		
		// falls die Liste NICHT leer war
		else{
			int count2 = 0;
			BuchNode zeiger = first;

			// Der Zeiger durchläuft solange die Schleife bis
			// entweder das Ende der Liste erreicht ist oder
			// die richtige Stellen gefunden wurde
			while (autor.compareTo(zeiger.autor) >= 0 && count2 < count){
				if (zeiger.next != null)
					zeiger = zeiger.next;
				count2++;
			}
			
			
			// Einfügen am Anfang der Liste
			if (count2 == 0){
				buch.prev = buch;
				buch.next = first;
				first.prev = buch;
				first = buch;
			}
			
			// Einfügen am Ende der Liste
			if (count2 == count){
				System.out.println ("ZEIGER: " + zeiger.autor);
				buch.prev = zeiger;
				buch.next = buch;
				zeiger.next = buch;
				zeiger = buch;
			}
			
			// Einfügen irgendwo in der Mitte der Liste
			if (count2 != 0 && count2 != count){
				//System.out.println ("Zeiger: " + zeiger.autor);
				buch.next = zeiger;
				buch.prev = zeiger.prev;
				zeiger.prev.next = buch;
				zeiger.prev = buch;
				zeiger = buch;
			}
		}
		count++;
	}
	
	/** Methode um die komplette Liste auszugeben */
	public void ausgabe(){
		BuchNode temp = first;
		int n = 1;
		
		// Schleife in der die komplette Liste ausgegeben wird
		while (n <= count){
			System.out.println ("Autor " + n + ": " + temp.autor);
			temp = temp.next;
			n++;
		}
	}
	
	/** Methode um den Autor eines bestimmten Buches zu finden */
	public String autorSuche(String titel){
		BuchNode temp = first;
		int i = 0;
		boolean found = false;
		
		// Schleife in der die Liste durchsucht wird
		while (titel.compareTo(temp.buchtitel) != 0 && i < count){
			if (temp.next != null)
				temp = temp.next;
			i++;
			if (titel.compareTo(temp.buchtitel) == 0)
				found = true;
		}
		
		// Falls der Autor eines bestimmten Buches gefunden wird, 
		// wird er hier ausgegeben
		if (found){
			return "Das Buch " + titel + " ist vom Autor: " + temp.autor;
		}
		
		// Falls der Titel nicht in der Liste ist
		else
			return "Das Buch " + titel + " ist NICHT in der Liste enthalten";
	}
	
	public void delete (String autor){
		int count2 = 1;
		BuchNode zeiger = first;
		
		while (count2 <= count){
			System.out.println ("Counter: " + count + " Counter2: " + count2);
			if (autor.compareTo(zeiger.autor) == 0){
				System.out.println ("IF1");
				if (count2 == count){
					System.out.println (zeiger.autor);
					zeiger = zeiger.prev;
					zeiger.next = zeiger;
					System.out.println (zeiger.autor);
				}
			}
			zeiger = zeiger.next;
			count2++;
		}
	}
	
	public static void main(String[] args) {
		Buchverwaltung test = new Buchverwaltung();
		
		test.insert("Buch1", "Zacherl Jürgen");
		test.insert("Buch2", "Bahl Christian");
		test.insert("Buch3", "Ahl Christian");
		test.insert("Buch4", "Grass Günter");
		test.insert("Buch5", "Bernd Günter");
		test.insert("Buch6", "Früchtl Christiane");
		test.insert("Buch7", "Ditz Christian");
		test.insert("Buch8", "Zitz Christian");
		test.insert("Buch9", "Deutz Christian");
		test.ausgabe();
		test.delete(("Zitz Christian"));
		test.ausgabe();
		System.out.println(test.autorSuche("Orgasmusgarantie1"));
	}
}

Leider funktioniert das löschen noch nicht ganz. kannst du mir da evtl weiterhelfen? Wär echt super. Die Aufgabe besteht darin eine Methode zu implementieren die alle gleichen Autoren und deren Buchtitel aus der Liste löscht. habs versucht wenn es der Fall ist, das das letzte Element gelöscht wird, aber das haut nicht so ganz hin.

Achja und desweiteren hab ich noch eine Frage zum einfügen eines neuen BuchKnotens an letzter Stellen. Ich mach das ja mit Hilfe des Zeigers, also wofür brauch ich dann das "BuchNode last".

Und wenn du Lust hast kannst du mir ja auch noch weitere Optimierungsvorschläge geben bzw auf Fehler hinweisen.

Merci dir schonmal!!!

 

[mattulla]

Also was du nicht brauchst ist der Zaehler (count). Wenn du die Liste durlaufen willst geht das immer in etwa so:

Buchnode akt = first;
while(akt!=null)
{
    //deine Aktion
    akt = akt.next;
}

Das last hat den selben Sinn wie das first, so kannst du die liste auch von hinten nach vorne durchlaufen. Wenn du die Funktion nicht brauchst kannst dir eigentlich auch das previous schenken.

 

[Bodo1981]

soweit hab ich das jetzt verstanden, aber wie sieht es mit der delete()-Methode aus? was muss ich da genau machen um einen knoten aus der liste zu löschen

 

[mattulla]

also wenn du den Eintrag in der Liste gefunden hast den du loeschen moechtest dann musst du noch das hier machen:

Buchnote n  = zuLoeschendeBuchnote.next;
Buchnote p = zuLoeschendeBuchnote.prev;
p.next = n;
n.prev = p;

Natuerlich musst du auch hier die beiden Sonderfaelle, dass du die erste bzw. letzte Buchnote loeschen willst extra behandeln.

 

[Bodo1981]

das funktioniert nicht so ganz. der name (also irgendeiner aus der mitte der liste) wird zwar gelöscht, aber dann wird der name am ende der liste zweimal aufgeführt

 

[mattulla]

Hast die Sache mit dem count denn schon rausgenommen, wenn nicht hat es bestimmt zu tun. Sonst poste doch bitte noch mal deinen aktuellen Code.