Datentypen Doppelt verkettete Liste

Eddie

Mitglied
Hallo zusammen,

ich hab mal wieder ein Problem. Es geht um folgendes:
Ich soll eine doppelt verkettete Liste erzeugen. Jetzt hab ich aber das Problem, dass mein Programm in einer Endlosschleife endet. Vielleicht könnt ihr mir helfen und mir einen Tipp geben, wo denn der Fehler liegt.
Folgender Code führt das Programm aus:
Java:
public class Drive {
	public static void main(String[] args){

		DLinkedList<String> l = new DLinkedList<String>();
		System.out.println(l.isEmpty() );
		l.add( 1, "Kahn" );
		System.out.println(l.isEmpty() );
		l.add( 1, "Rudi" );													
		System.out.println( "Index von Kahn " + l.indexOf( "Kahn" ) );
		l.add( 2, "Linke" );
		System.out.println( l.get(2) );
		System.out.println( l.remove(2) );
		System.out.println( l.remove(2) );
	}
}
Und hier die Klasse DLinkedList, in der die doppelt verkettete Liste implementiert ist:

Java:
public class DLinkedList<T> implements List<T> {
	
	@SuppressWarnings("unchecked")
	static class Node<T>{
		T t;													//Element
		Node<T> prev;											//Zeiger auf Vorgänger
		Node<T> next;											//Zeiger auf Nachfolger
		
		public Node (T o, Node p, Node n){
			t = o;
			prev = p;
			next = n;
		}
		
		public Node() {
			t = null;
			prev = null;
			next = null;
		}
		
		public void setPrevious (Node p){						//Vorgänger neu belegen
			prev = p;
		}
		
		public Node getPrevious(){								//Zugriff auf Vorgänger
			return prev;
		}
		
		public void setNext (Node n){							//Nachfolger neu belegen
			next = n;
		}
		
		public Node getNext(){									//Zugriff auf Nachfolger
			return next;
		}
		
		public T getElement(){									//Gibt den Inhalt des aktuellen Knoten zurück
			T element = this.t;
			return element;
			
		}
	}
	
	@SuppressWarnings("unchecked")
	private Node head = null;
	@SuppressWarnings("unchecked")
	private Node tail = null;
	
	@SuppressWarnings("unchecked")
	public DLinkedList (){
		head = new Node();
		tail = new Node();
		head.setNext(tail);										//Anfang und Ende "verknüpfen"
		tail.setPrevious(head);
		tail.setNext(tail);
	}
	
	@SuppressWarnings("unchecked")
	public void addFirst (T o) {								//Knoten zwischen head und dessen Nachfolger einfügen
		Node n = new Node (o, head, head.getNext());
		head.getNext().setPrevious(n);
		head.setNext(n);
	}
	
	@SuppressWarnings("unchecked")
	public void addLast (T o) {									//Knoten zwischen tail und dessen Vorgänger einfügen
		Node l = tail.getPrevious();
		Node n = new Node(o, l, tail);
		l.setNext(n);
		tail.setPrevious(n);
	}
	
	//Warum wird hier nur Object und nicht T als Rückgabetyp akzeptiert?  
	@SuppressWarnings("unchecked")
	public T getFirst(){										//Zugriff über Listenanfang
		if (isEmpty() ==  true){
			return null;
		}
		else {
			return (T) head.getNext().getElement();
		}
	}
	
	//Warum wird hier nur Object und nicht T als Rückgabetyp akzeptiert?
	@SuppressWarnings("unchecked")
	public T getLast(){											//Zugriff über Listenende
		if (isEmpty() == true){
			return null;
		}
		else {
			return (T) tail.getPrevious().getElement();
		}
	}
	
	@SuppressWarnings("unchecked")
	public T removeFirst() {
		if (isEmpty() == true){
			return null;
		}
		else {
			T o = (T) head.getNext().getElement();				//Zugriff über Listenanfang
			head.setNext(head.getNext().getNext());				//Knoten zwischen head und Nachfolger entfernen
			head.getNext().setPrevious(head);
			return o;
		}
	}
	
	@SuppressWarnings("unchecked")
	public T removeLast(){
		if (isEmpty() == true){
			return null;
		}
		else{
			Node n = tail.getPrevious();						//Zugriff über Listenende
			n.getPrevious().setNext(tail);						//Knoten zwischen tail und Vorgänger entfernen
			tail.setPrevious(n.getPrevious());
			return (T) n.getElement();
		}
	}

	@SuppressWarnings("unchecked")
	public void add(int p, T x) {								//Fügt einen Knoten mit Inhalt x an der Stelle p hinzu, wobei gilt: 1 = head
		int size = size();
		if (p == 1){
			addFirst(x);
		}
		else {
			if (p <= (size/2)){										//Ermittelt, ob von vorne oder von hinten eingefügt wird
				Node n = head;										//von vorne einfügen:
				for (int i = 0; i <= p; i++){						//Ermittelt Knoten, nach dem eingefügt wird
				n = n.getNext();								//Es muss nach Knoten n einfügt werden
				}
				Node insert = new Node(x, n, n.getNext());			//Fügt den neuen Knoten zwischen n und dessen Nachfolger ein
				n.getNext().setPrevious(insert);
				n.setNext(insert);
			}
			else {
				Node n = tail;										//von hinten einfügen:
				for (int i = size; i >= p; i--){					//Ermittelt Knoten, vor dem eingeügt wird
					n = n.getPrevious();							//Es muss vor Knoten n eingefügt werden
				}
				Node help = n.getPrevious();						//Fügt den neuen Knoten zwischen n und dessen Vorgänger ein
				Node insert = new Node (x, help, n);
				help.setNext(insert);
				n.setPrevious(insert);
			}
		}
		
	}

	@SuppressWarnings("unchecked")
	public T get(int p) {										//Gibt das Element am Knoten p zurück
		if (p < (size()/2)) {									//Prüft, ob von vorne gestartet werden soll
			Node n = head;
			for (int i = 0; i <= p; i++){
				n = n.getNext();
			}
			return (T) n.getElement();							//gibt das Element zurück
		}
		else {
			Node n = tail;
			for (int i = size(); i >= p; i--){
				n = n.getPrevious();
			}
			return (T) n.getElement();							//gibt das Element zurück
		}
	}

	@SuppressWarnings("unchecked")
	public int indexOf(T x) {									//Gibt zurück, in welchem Knoten das Element x steht
		Node n = head;
		for (int i = 0; i <= size(); i++){
			if (n.getElement() == x){
				return i;
			}
			else {
				n.getNext();
			}
		}
		return 0;
	}

	public boolean isEmpty() {									//Keine Knoten zwischen head und tail
		return head.getNext() == tail;
	}

	@SuppressWarnings("unchecked")
	public T remove(int p) {									//entfernt ein Element an der Stelle p und gibt es zurück
		if (p <= (size()/2)){
			Node n = head;
			for (int i = 0; i <= p; i++){
				n = n.getNext();
			}
			Node prev = n.getPrevious();
			Node next = n.getNext();
			prev.setNext(next);
			next.setPrevious(prev);
			return (T) n.getElement();
		}
		else {
			Node n = tail;
			for (int i = size()+1; i >= p; i--){
				n = n.getPrevious();
			}
			Node prev = n.getPrevious();
			Node next = n.getNext();
			prev.setNext(next);
			next.setPrevious(prev);
			return (T) n.getElement();
		}
	}

	@SuppressWarnings("unchecked")
	public int size() {											//Gibt die Länge der Liste zurück
		int s = 0;
		Node n = head;
		while (n.getNext() != null){							//Knoten zählen
			s++;
			n = n.getNext();
		}
		return s;
	}

}

Das Problem muss wohl irgendwo in der add-Methode liegen, denn isEmpty() wird nocht ausgeführt. Die add-Methode allerings ist ne Endlosschleife...
 

turing

Mitglied
Nur überflogen: Wenn ein neuer Knoten eingefügt wird, dann müssen ja, je nach Position, die Nachfolger-Referenz des Vorgängers und die Vorgänger-Referenz des Nachfolgers gesetzt werden. Das kann man gleich beim Konstruieren eines Knotens machen. So in der Art:

Java:
        public Node (T o, Node p, Node n){
            t = o;
            prev = p;
            next = n;
            if (next != null) next.prev = this;
            if (prev != null) prev.next = this;
        }

Dann brauch im Konstruktor der Liste nur noch head und tail auf null setzen und benötigt keine Dummy-Nodes mehr. Nun kann man vorne und hinten sehr bequem anhängen:

Java:
  public void addFirst (T o) {
      head = new Node(o, null, head);
      if (head.next == null) tail = head;
  }  
  public void addLast (T o) {        
      tail = new Node(o, tail, null);
      if (tail.prev == null) head = tail;
  }
 
Zuletzt bearbeitet:

Eddie

Mitglied
@turing: danke für den tipp, da hast du wohl Recht.

@salaweis:
Damit verweist dann der letzte Knoten auf sich selber, wenn man nach dem nächsten fragt.
 

Sonecc

Gesperrter Benutzer
schau dir deine size methode mal an, n kann dort nie null werden, da du durch den verweis deines letzten knotens nie null referenzierst

Nimm die Zeile 55 raus, dann sollte es gehen
 

Markey

Mitglied
@salaweis:
Damit verweist dann der letzte Knoten auf sich selber, wenn man nach dem nächsten fragt.

Das macht doch in dem Fall nichts, wenn der letzte Knoten ins leere zeigt (Zeiger auf "null"). Ist das nicht sogar gefährlich wenn du es nicht tust? Angenommen du möchtest durch die ganze Liste itterieren. Angefangen beim "ersten Knoten". Suchst dir jedes mal wieder den Nachfolger. Da hast du doch kein Ende in Sicht, wenn der letzte Knoten immer wieder auf sich selber refferenziert!?
 

Andi_CH

Top Contributor
Es ist IMO wirklich sinnvoll dass der letzte Knoten als Nachfolger null hat. Dann weiss man wenigstens wo man die Iteration abbrechen muss.
Code:
while (k.next != null) ...
ist doch elegant, oder nicht?

Natürlich könnte man auch
Code:
while (k.next != k)  ...
schreiben aber warum?

Genauso soll der erste Knoten als Vorgänger null haben.

Anders gesagt der erste Knoten ist der erste weil er keinen Vorgänger hat und der letzte Knoten ist eben nur darum der letzte weil er keinen Nachfolger hat.
 

Eddie

Mitglied
Zunächst mal danke ich euch für die schnellen Antworten.
Ich habe mich mal an den Tip gehalten und ihr hattet Recht. Lag daran.
Eigentlich ganz einfach. :)

Jetzt hab ich noch ein Problem mit den Indizes, aber ich denk, das bekomm ich vollends hin.

Aus welchem Lehrbuch ich das habe..nun ja. Der code steht so ähnlich in "Algorithmen und Datenstrukturen - Eine Einführung mit Jave" von Gunter Saake und Kai-Uwe Sattler
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
B Doppelt Verkettete Liste - Ist alles gut so? Java Basics - Anfänger-Themen 3
U Datentypen Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 13
J Methoden Doppelt verkettete Liste remove(Object) Java Basics - Anfänger-Themen 8
B OOP Über eine doppelt verkettete Liste iterieren Java Basics - Anfänger-Themen 4
L Doppelt verkettete Liste Java Basics - Anfänger-Themen 6
R doppelt verkettete Liste aus Arrays erstellen Java Basics - Anfänger-Themen 1
S Doppelt verkettete Liste Java Basics - Anfänger-Themen 3
G Doppelt Verkettete Liste Java Basics - Anfänger-Themen 2
A Doppelt Verkettete Liste Java Basics - Anfänger-Themen 16
E doppelt verkettete liste Java Basics - Anfänger-Themen 10
P Einfügen in doppelt verkettete Liste Java Basics - Anfänger-Themen 7
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
K Datentypen Einfach/Doppelt verkettete Liste Java Basics - Anfänger-Themen 4
W Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 2
G Doppelt verkettete, generische Liste Java Basics - Anfänger-Themen 11
D doppelt verkettete Liste Java Basics - Anfänger-Themen 16
S Doppelt Verkettete Liste Java Basics - Anfänger-Themen 7
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
J doppelt verkettete Liste Java Basics - Anfänger-Themen 5
L doppelt verkettete Liste Java Basics - Anfänger-Themen 6
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 12
B Doppelt verkettete Liste Java Basics - Anfänger-Themen 16
R Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE! Java Basics - Anfänger-Themen 12
R doppelt verkettete Liste Java Basics - Anfänger-Themen 8
F doppelt verkettete liste! Java Basics - Anfänger-Themen 8
R doppelt verkettete azyklische Liste Java Basics - Anfänger-Themen 2
T Klasse in Java für doppelt verkettete Listen Java Basics - Anfänger-Themen 4
H Doppelt verkettete Listen Java Basics - Anfänger-Themen 2
S doppelt verkettete Listen Java Basics - Anfänger-Themen 4
X Vererbung: Doppelt verkettete Listen Java Basics - Anfänger-Themen 16
O Doppelt verkette Liste Element löschen Java Basics - Anfänger-Themen 15
J Doppelt verkette Liste ich bitte um Hilfe Java Basics - Anfänger-Themen 4
I Input/Output Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 3
N package wird doppelt im exporer angezeigt Java Basics - Anfänger-Themen 2
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
J Fehler beim generieren von 4 Zufallszahlen Zahl doppelt ist eigentlich ausgeschlossen Java Basics - Anfänger-Themen 9
T Löschen in doppelt verketteter Liste Java Basics - Anfänger-Themen 1
L Input/Output Println wird doppelt ausgeführt Java Basics - Anfänger-Themen 11
D Interface Frame doppelt durch Aufruf der GUI Klasse Java Basics - Anfänger-Themen 1
B BufferedReader gibt Datei-Inhalt doppelt aus Java Basics - Anfänger-Themen 3
M Liste Implementation, doppelt next() Java Basics - Anfänger-Themen 13
D Klassen Doppelt so viele Elemente in Arraylist ? Java Basics - Anfänger-Themen 4
Salo Datentypen "Doppelt" List(e) ("gesucht") Java Basics - Anfänger-Themen 6
L do-while-Schleife läuft doppelt, try catch fehler Java Basics - Anfänger-Themen 12
T Java Methode wird unerwünscht doppelt aufgerufen?! Java Basics - Anfänger-Themen 4
OnDemand Doppelt Werte CSV Java Basics - Anfänger-Themen 2
llabusch Verkette Listen - Einfach und Doppelt Java Basics - Anfänger-Themen 3
N Erste Zeile bei BufferedReader doppelt lesen? Java Basics - Anfänger-Themen 2
E Erste Schritte Sortieren von Objekten in doppelt-verlinkter Liste Java Basics - Anfänger-Themen 9
S Methoden Methode wird doppelt aufgerufen ... Java Basics - Anfänger-Themen 5
J Mehrere Zufallszahlen erzeugen, aber keine darf doppelt erzeugt werden - Wie? Java Basics - Anfänger-Themen 5
B Doppelt gekettete Listen Java Basics - Anfänger-Themen 4
G PropertyChangeListener empfängt Events doppelt Java Basics - Anfänger-Themen 5
L doppelt verkette Liste Java Basics - Anfänger-Themen 5
H Fenster doppelt gezeichnet. Java Basics - Anfänger-Themen 2
G Einfügen aus Zwischenablage - alles doppelt? Java Basics - Anfänger-Themen 2
G JFileChooser kommt doppelt Java Basics - Anfänger-Themen 3
N Nullpointerexception bei Doppelt verketteter Liste Java Basics - Anfänger-Themen 7
M Listen richtig doppelt verkettet? Java Basics - Anfänger-Themen 13
D Exceptions in doppelt verketteter Liste Java Basics - Anfänger-Themen 5
C verify() wird doppelt aufgerufen (JTable + InputVerifier) Java Basics - Anfänger-Themen 8
H doppelt verkette liste Java Basics - Anfänger-Themen 2
L rückwärtsausgeben einer doppelt verketteten liste Java Basics - Anfänger-Themen 2
G JList und ListCellRenderer - Vector erscheint doppelt Java Basics - Anfänger-Themen 6
G JComboBox gibt SelectedItem immer doppelt aus Java Basics - Anfänger-Themen 4
B Array doppelt Felder löschen Java Basics - Anfänger-Themen 27
M Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 2
R Zeilen aus datei lesen + doppelt gespeichert? Java Basics - Anfänger-Themen 3
G Trotz Abfrage immer noch Zahlen doppelt Java Basics - Anfänger-Themen 3
R Benutzerregistrierung: Doppelt registriert. Java Basics - Anfänger-Themen 8
M Verkettete Liste Java Basics - Anfänger-Themen 1
S Einfach-Verkettete-Listen Ausgabe zeigt nur 1. und letzte instanz Java Basics - Anfänger-Themen 2
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
Igig1 Autoparkplatz verkettete Liste erstes und letztes Auto Java Basics - Anfänger-Themen 13
R Rückgabe: verkettete Liste Java Basics - Anfänger-Themen 2
R einfach verkettete Liste Java Basics - Anfänger-Themen 1
R einfach verkettete Liste Java Basics - Anfänger-Themen 12
B Verkettete Liste durchgehen und einzelne Elemente in neue Liste tun Java Basics - Anfänger-Themen 9
B Bin komplett am verzweifeln :( Verkettete Liste die Objekte hat Attribut auslesen Java Basics - Anfänger-Themen 14
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A Verkettete Liste Java Basics - Anfänger-Themen 2
L verkettete Liste Java Basics - Anfänger-Themen 15
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
H Verkettete Liste Java Basics - Anfänger-Themen 7
N Verkettete liste rückwärts ausgeben Java Basics - Anfänger-Themen 18
K Verkettete Liste und seine Methoden Java Basics - Anfänger-Themen 1
A Was könnten typische Prüfungsaufgaben zum Thema lineare, verkettete Listen sein? Java Basics - Anfänger-Themen 5
N Verkettete Liste implementieren Java Basics - Anfänger-Themen 5
O Einfach verkettete Liste - Revert Methode Java Basics - Anfänger-Themen 1
G Verkettete Liste - Neu erzeugte Elemente werden nicht ausgegeben Java Basics - Anfänger-Themen 5
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
C Verkettete Liste - sortiert einfügen Java Basics - Anfänger-Themen 7
R Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Neue Themen


Oben