# Doppelt verkettete Liste erzeugen und editieren



## Semox (11. Jun 2010)

Hallo Forum

Ich habe die Aufgabe ohne zur Hilfenahme von üblichen fertigen Java Klassenbibliotheken eine doppelt verkettete Liste zu erzeugen.

Folgende Eigenschaften soll sie haben:
Generisches Listenobjekt erzeugen
Elemente hinzufügen
Elemente löschen
Elemente ausgeben

Soweit habe ich das fast alles fertig, aber ich komme nicht die Sache mit dem Löschen des letzten Elements innerhalb der Liste hin. Kann mir bitte jemand erklären, was ich da richtig machen muß?


```
import java.util.EmptyStackException;

/**
 * SortedList ist ein Programm, mit dem beliebige Typen bzw. Werte in eine
 * aufsteigend sortierte Liste eingebettet werden koennen
 * 
 * @author Icke
 * @version 1.6.0_20-b02
 * @serial 0.3
 * @param <T>
 *            ist ein beliebiger primitiver oder Objekttyp
 */

public class SortedList<T extends Comparable<T>> {

	public Node head = null;
	public Node tail = null;

	class Node {

		public T value;
		public Node next;
		public Node previous;

		public T getValue() {
			return value;
		}

		public void setValue(T value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}

		public Node getPrevious() {
			return previous;
		}

		public void setPrevious(Node previous) {
			this.previous = previous;
		}

		public Node(T value, Node next, Node previous) {
			this.value = value;
			this.next = next;
			this.previous = previous;
		}

	}

	/**
	 * Methode add(T elem) zum Hinzufuegen eines Wertes in eine gemaess
	 * Comparable aufsteigend sortierte Liste. Dubletten sind zulaessig,
	 * erzeugen aber kein neues Objekt, aber eine weitere interne Referenz.
	 * 
	 * @param T
	 *            elem der hinzuzufuegende Wert
	 */
	public void add(T elem) {
		Node Lesekopf = head;
		Node Knoten = new Node(elem, null, null);

		// ### Wenn die Liste nicht leer ist...
		if (!empty()) {
			// Lesekopf-Value ist kleiner als Elem --> soll solange iterieren
			// bis das letztes Obj erreicht ist
			while ((Lesekopf != null)
					&& (Lesekopf.getValue().compareTo(elem) < 0)) {
				Lesekopf = Lesekopf.getNext();
			}
			// ### Wenn Lesekopf vor dem ersten Elem was einfuegen muss ###
			if (Lesekopf == head) {
				Knoten.setNext(Lesekopf);
				Lesekopf.setPrevious(Knoten);
				head = Knoten;
				System.out
						.println("### Wenn Lesekopf vor dem ersten Elem was einfuegen muss ###: "
								+ Knoten.getValue());
			}
			// ### Wenn Lesekopf nach letztem Elem was einfuegen muss ###
			else if (Lesekopf == null) {
				// Setze Link auf auf neuen nachfolgenden Knoten
				tail.setNext(Knoten);
				// Setze im neuen Knoten den Vorgaenger
				Knoten.setPrevious(tail);
				// Setze im neuen Knoten den Nachfolger --> kein weiteres Elem
				tail = Knoten;
				System.out
						.println("### Wenn Lesekopf nach letztem Elem was einfuegen muss ###: "
								+ Knoten.getValue());
			} else {
				// Hole den vorletzen Knoten und biege auf neuen Knoten
				Lesekopf.getPrevious().setNext(Knoten);
				// Setze im neuen Knoten den Vorgaenger
				Knoten.setPrevious(Lesekopf.getPrevious());
				// Biege Vorgaengerkante auf neuen Vorgaenger um
				Lesekopf.setPrevious(Knoten);
				// Setze im neuen Knoten den Nachfolger --> Lesekopf
				Knoten.setNext(Lesekopf);
				System.out
						.println("### Wenn Lesekopf dazwischen was einfuegen muss ###: "
								+ Knoten.getValue());
			}
		} else {
			// ### Wenn Liste Leer ist...
			Knoten.setNext(null);
			Knoten.setPrevious(null);
			head = Knoten;
			tail = Knoten;
			System.out.println("### Liste war leer ###: " + Knoten.getValue());
		}

	}

	/**
	 * Methode zum Entfernen von Werten aus einer Liste. Falls der uebergebene
	 * Wert mehrfach vorhanden ist, werden alle Vorkommen dieses Wertes aus der
	 * Liste entfernt
	 * 
	 * @param T
	 *            elem der zu entfernende Wert
	 */

	public void remove(T elem) throws EmptyStackException {
		Node Lesekopf = head;

		while (Lesekopf.getNext() != null && !empty()) {
			if (Lesekopf.getValue() == elem) {
				if (Lesekopf != head && Lesekopf != tail) {
					Lesekopf.getNext().setPrevious(Lesekopf.getPrevious());
					Lesekopf.getPrevious().setNext(Lesekopf.getNext());
					//Lesekopf = tail;
					break;
				}
				if (Lesekopf == head) {
					Lesekopf = Lesekopf.getNext();
					Lesekopf.setPrevious(null);
					Lesekopf = head;
					break;
				}
				if (Lesekopf == tail) {
					Lesekopf.getPrevious().setNext(null);
					Lesekopf = tail;
					break;
				}

			} else {
				if (empty()) {
					System.out
							.println("Nichts zu loeschen, weil die Liste leer, oder das gesuchte Element nicht vorhanden ist.");
					break;
				} else {
					Lesekopf = Lesekopf.getNext();
				}
			}

		}// Ende while-Schleife

	}

	/**
	 * 
	 * Wenn Start und Endknoten NULL sind, so existiert auch keine Vorgaenger
	 * oder Nachfolger was bedeutet, dass die Liste leer ist.
	 * 
	 * @return boolean
	 * */
	public boolean empty() {
		return ((head == null) && (tail == null));
	}

	/**
	 * Die Methode returnAll() gibt den gesamten Inhalt der gespeicherten
	 * Objekte zurueck
	 * 
	 * @return nothing
	 */

	public void returnAll() {
		Node Lesekopf = head;

		while (Lesekopf.getNext() != null) {
			Lesekopf = Lesekopf.getNext();
			System.out.println(Lesekopf.getValue());
		}
	}

	public static void main(String[] args) {
		SortedList<Integer> stuff = new SortedList<Integer>();
		System.out.println("Werte in Liste einbetten: ");
		stuff.add(100);
		stuff.add(101);
		stuff.add(5);
		stuff.add(3);
		stuff.add(8);
		System.out.println("Gespeicherte Werte ausgeben: ");
		stuff.returnAll();
		System.out.println("Etwas loeschen (8)... ");
		stuff.remove(8);
		stuff.returnAll();
		System.out.println("Etwas loeschen (100)... ");
		stuff.remove(100);
		stuff.returnAll();
		System.out.println("Etwas loeschen (101)... ");
		stuff.remove(101);
		stuff.returnAll();
		System.out.println("Etwas loeschen (5)... ");
		stuff.remove(5);
		stuff.returnAll();
		System.out.println("Ende des Programms.");
	}

}
```

Vieeelen Dank,
Semo


----------



## SlaterB (11. Jun 2010)

Semox hat gesagt.:


> ```
> public void remove(T elem) throws EmptyStackException {
> Node Lesekopf = head;
> 
> ...


->



```
public void remove(T elem)  {
        Node Lesekopf = head;
        while (!empty())   {
            if (Lesekopf.getValue() == elem)  {
...
            }
            else
            {
                if (empty())  {
                    break;
                }  else if (Lesekopf.getNext() != null)  {
                    Lesekopf = Lesekopf.getNext();
                } else {
                    break;
                }
            }
        }
    }
```
die Exception wird nie geworfen,

-------

ein interessanterer Fehler: 
für 1001 oder jede andere Zahl über 128 funktioniert das Löschen nicht wenn du den Parameter so wie bisher übergibst,
darüber kannst du erstmal nachdenken, spätestens morgen verrate ich es bei Rückfrage


----------



## newbie2009 (11. Jun 2010)

hey semox  


warum übergibst du überhaupt einen wert, wenn das letzte element gelöscht wird?
kannst nich einfach einen zeiger machen, der immer aufs letzte element zeigt, und dann hängst du diesen einfach um?


habe heute auch meiene doppelt verkettete liste fertig gemacht,aber bissl anders als du , aber  die hat auch die methoden addFirst,addLast, removeFirst,removeLast, getFirst,getLast, wenn du möchtest kann ich sie dir zur verfügung stellen, hast mir ja auch vorhin geholfen^^


----------



## Semox (11. Jun 2010)

SlaterB hat gesagt.:


> ->
> die Exception wird nie geworfen,
> 
> -------
> ...



Ein  interessanter Post... Mr. Watson... Wie ich stets zu sagen pflege: "Nichts ist trügerischer als eine offenkundige Tatsache.", so entdeckte ich genau diese Tatsache beim Ausführen im Debug-Modus- 

[kurzer S/W Film im Metropolis-Stil: Watson und Holmes im Labor. Rauchende Retorten ergießen eine weißdampfende Flüssigkeit in Erlenmeyerkolben, deren sich darin enthaltene Flüssigkeit unter Wärmewirkung rot verfärbt... Es gibt einen Knall. Beide Darsteller schauen erst verwundert auf die Behälter, dann sich in die Augen. Posaunen schwellen erst auf dann ab. Holmes ab.]

Für jedes zu löschende Element inmitten dieser Liste mag die gestellte Bedingung funktionieren, allein handelt es sich um's erste gar um's letzte Element, so will die "remove" Methode ihren Dienst versagen. Ich will diesen Ansatz verfolgen und ihm nachgehen...

Viele Grüße,
Semo

EDIT:
Natürlich wird die Exception nie geworfen, da ich sie eingangs bereits per Abbruchbedingung definiert habe und somit im weiteren Verlauf verboten habe...


----------



## Semox (14. Jun 2010)

Ok...  Ich habe nun gesucht und geschaut, warum das so ist. Ich habe keine Lösung gefunden. Auch wenn ich Long oder irgendwas anderes in der Liste nutze, dann habe ich den gleichen Fehler, daß ich jenseits der 127 nichts löschen kann... Warum ist das so?

Ich kenne, daß aus DOS Zeiten, wo man aufpassen mußte, wie man eine Datei allokiert, aber, bei JAVA und bei 32 Bit dachte ich nicht, daß so eine winzige Anzahl von Objekten ein Problem bereiten kann... 

Ich würde mich sehr über eine Erklärung freuen...

Viele Grüße,
Semo

PS. Mein Prof kann sich das auch nicht erklären... Woran das wohl liegt?


----------



## SlaterB (14. Jun 2010)

beim AutoBoxing int zu Ojbekt Integer wird Integer.valueOf() verwendet,
Integer.valueOf() liefert für kleine Zahlen immer exakt dasselbe gecachte Integer-Objekt,
für größere Zahlen wird aufwendiger immer ein neues Objekt erzeugt,

new Integer(300) != new Integer(300)

verwende equals() statt == zum Vergleich von Objekten


----------



## Semox (14. Jun 2010)

Hi SlaterB

Danke für die Antwort, aber ich habe es noch nicht ganz verstanden, wie es mit der Umwandlung Probleme geben soll... 

Heißt das ich muß den Primitivwert int in ein Integer wrappen und dann über "elem" an das neue Listenobjekt übergeben? Würde dann das Autoboxing funktionieren?

Wie hängt das mit dem Cache zusammen?

Gruß,
Semo


----------



## faetzminator (14. Jun 2010)

Es _wird_ aktuell in einen Integer gewrappt, darum funktioniert das [c]!=[/c] nicht zwingend, d.h. lediglich, wenn es sich um zwei gleiche Objektreferenzen (= gleiches Objekt) handelt. Ändere den Check von [c]!=[/c] auf [c]!... .equals(...)[/c].


----------



## SlaterB (14. Jun 2010)

und ich dachte meine Sätze wären verständlich 

Beispiel 101 -> durch Java-interne Mechanismen wird immer exakt dasselbe 101-Integer-Objekt verwendet, direkter Vergleich funktioniert
Beispiel 1001 -> zu groß für Cache, der übergebene Parameter ist ein anderes Integer-Objekt als in der Liste schon drin, wenn auch beide 1001 beschreiben, direkter Vergleich funktioniert nicht, equals würde gehen


----------



## Semox (14. Jun 2010)

Habe es geändert. Leider bin ich trotzdem noch an dem alten Problem dran. 

Ich kann das erste oder das letzte Element nicht löschen. Ich verstehe nicht ganz warum. Versuche die ich machte endeten bislang darin, daß alle Referenzen auf die nächsten Obj futsch waren, oder ich eine NullPointerException erhalte...

Hier noch mal die gegenwärtige Methode:


```
public void remove(T elem) throws EmptyStackException {
		Node Lesekopf = head;

		while ((Lesekopf.getNext() != null) && !empty()) {

			if (Lesekopf.getValue().compareTo(elem) == 0) {
				if (Lesekopf != head && Lesekopf != tail) {
					Lesekopf.getNext().setPrevious(Lesekopf.getPrevious());
					Lesekopf.getPrevious().setNext(Lesekopf.getNext());
					break;
					//erstes Element loeschen
				} else if (Lesekopf.equals(head)) {
					//Lesekopf.getNext().setPrevious(null);
					Lesekopf.getNext().setPrevious(null);
					//Lesekopf.getPrevious().setNext(null);
//					Lesekopf = head;
					break;
					//letztes Element loeschen
				} else if (Lesekopf.equals(tail)) {
					Lesekopf.getPrevious().setNext(null);
					break;
				}
			}
			Lesekopf = Lesekopf.getNext();
		}

	}
```

Kann mir jemand bitte einen Lösungsansatz verraten?

Grüße,
Semo


----------



## SlaterB (14. Jun 2010)

wie ich schon in der ersten Antwort geschrieben hatte, muss das (Lesekopf.getNext() != null) aus der while-Schleifen-Bedingung raus,

oder da tail sowieso gesondert behandelt werden muss, kannst du das auch schon vor der Schleife einmalig prüfen:

```
if () { // Objekt gehört zum tail
                    tail.getPrevious().setNext(null); // Vorsicht wenn nur ein Element in der Liste, testen!
                    break;
                }
```

----

compareTo() == 0 ist leicht gefährlich, wieso nicht equals?



> It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."


Comparable (Java 2 Platform SE v1.4.2)


----------



## Semox (14. Jun 2010)

Hi zusammen

Vieeelen Dank Euch. Habe nun die komplette Lösung. 

Wer möchte kann sich dieses "Meisterstück" kopieren und verwerten. Ich stelle es unter die GPL:

Funktioniert und getestet.


```
import java.util.EmptyStackException;

/**
 * SortedList ist ein Programm, mit dem beliebige Typen bzw. Werte in eine
 * aufsteigend sortierte Liste eingebettet werden koennen
 * 
 * @author carino
 * @version 1.6.0_20-b02
 * @serial 0.3.7
 * @param <T>
 *            ist ein generischer Typ
 * 
 */

public class SortedList<T extends Comparable<T>> {

	public Node head = null;
	public Node tail = null;

	class Node {

		public T value;
		public Node next;
		public Node previous;

		public T getValue() {
			return value;
		}

		public void setValue(T value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}

		public Node getPrevious() {
			return previous;
		}

		public void setPrevious(Node previous) {
			this.previous = previous;
		}

		public Node(T value, Node next, Node previous) {
			this.value = value;
			this.next = next;
			this.previous = previous;
		}

	}

	/**
	 * Methode add(T elem) zum Hinzufuegen eines Wertes in eine gemaess
	 * Comparable aufsteigend sortierte Liste. Dubletten sind zulaessig,
	 * erzeugen aber kein neues Objekt, aber eine weitere interne Referenz.
	 * 
	 * @param T
	 *            elem der hinzuzufuegende Wert
	 */
	public void add(T elem) {
		Node Lesekopf = head;
		Node Knoten = new Node(elem, null, null);

		// ### Wenn die Liste nicht leer ist...
		if (!empty()) {
			// Lesekopf-Value ist kleiner als Elem --> soll solange iterieren
			// bis das letztes Obj erreicht ist
			while ((Lesekopf != null)
					&& (Lesekopf.getValue().compareTo(elem) < 0)) {
				Lesekopf = Lesekopf.getNext();
			}
			// ### Wenn Lesekopf vor dem ersten Elem was einfuegen muss ###
			if (Lesekopf == head) {
				Knoten.setNext(Lesekopf);
				Lesekopf.setPrevious(Knoten);
				head = Knoten;
				System.out
						.println("### Wenn Lesekopf vor dem ersten Elem was einfuegen muss ###: "
								+ Knoten.getValue());
			}
			// ### Wenn Lesekopf nach letztem Elem was einfuegen muss ###
			else if (Lesekopf == null) {
				// Setze Link auf auf neuen nachfolgenden Knoten
				tail.setNext(Knoten);
				// Setze im neuen Knoten den Vorgaenger
				Knoten.setPrevious(tail);
				// Setze im neuen Knoten den Nachfolger --> kein weiteres Elem
				tail = Knoten;
				System.out
						.println("### Wenn Lesekopf nach letztem Elem was einfuegen muss ###: "
								+ Knoten.getValue());
			} else {
				// Hole den vorletzen Knoten und biege auf neuen Knoten
				Lesekopf.getPrevious().setNext(Knoten);
				// Setze im neuen Knoten den Vorgaenger
				Knoten.setPrevious(Lesekopf.getPrevious());
				// Biege Vorgaengerkante auf neuen Vorgaenger um
				Lesekopf.setPrevious(Knoten);
				// Setze im neuen Knoten den Nachfolger --> Lesekopf
				Knoten.setNext(Lesekopf);
				System.out
						.println("### Wenn Lesekopf dazwischen was einfuegen muss ###: "
								+ Knoten.getValue());
			}
		} else {
			// ### Wenn Liste Leer ist...
			Knoten.setNext(null);
			Knoten.setPrevious(null);
			head = Knoten;
			tail = Knoten;
			System.out.println("### Liste war leer ###: " + Knoten.getValue());
		}

	}

	/**
	 * Methode zum Entfernen von Werten aus einer Liste. Falls der uebergebene
	 * Wert mehrfach vorhanden ist, werden alle Vorkommen dieses Wertes aus der
	 * Liste entfernt
	 * 
	 * @param T
	 *            elem der zu entfernende Wert
	 */

	public void remove(T elem) throws EmptyStackException {
		Node Lesekopf = head;

		while ((Lesekopf != null) && !empty()) {

			if (Lesekopf.getValue().equals(elem)) {
				if (Lesekopf != head && Lesekopf != tail) {
					Lesekopf.getNext().setPrevious(Lesekopf.getPrevious());
					Lesekopf.getPrevious().setNext(Lesekopf.getNext());
					break;
					//erstes Element loeschen
				} else if (Lesekopf.equals(head)) {
					head = head.getNext();
					break;
					//letztes Element loeschen
				} else if (Lesekopf.equals(tail)) {
					tail = Lesekopf.getPrevious();
					tail.setNext(null);
					break;
				}
			} 
			Lesekopf = Lesekopf.getNext();
		}

	}

	// Ende while-Schleife

	/**
	 * 
	 * Wenn Start und Endknoten NULL sind, so existiert auch keine Vorgaenger
	 * oder Nachfolger was bedeutet, dass die Liste leer ist.
	 * 
	 * @return boolean
	 * */
	public boolean empty() {
		return ((head == null) && (tail == null));
	}

	/**
	 * Die Methode returnAll() gibt den gesamten Inhalt der gespeicherten
	 * Objekte zurueck
	 * 
	 * @return nothing
	 */

	public void returnAll() {
		Node Lesekopf = head;

		while (Lesekopf.getNext() != null) {
			System.out.println(Lesekopf.getValue());
			Lesekopf = Lesekopf.getNext();
		}
		System.out.println(Lesekopf.getValue());
	}

	public static void main(String[] args) {
		SortedList<Integer> stuff = new SortedList<Integer>();
		System.out.println("Werte in Liste einbetten: ");
		stuff.add(101);
		stuff.add(257);
		stuff.add(256);
		stuff.add(100);
		stuff.add(5);
		stuff.add(1);
		stuff.add(3);
		stuff.add(8);
		System.out.println("Gespeicherte Werte ausgeben: ");
		stuff.returnAll();
		System.out.println("Etwas loeschen (8)... ");
		stuff.remove(8);
		stuff.returnAll();
		System.out.println("Etwas loeschen (100)... ");
		stuff.remove(100);
		stuff.returnAll();
		System.out.println("Etwas loeschen (256)... ");
		stuff.remove(256);
		stuff.returnAll();
		System.out.println("Etwas loeschen (3)... ");
		stuff.remove(3);
		stuff.returnAll();
		System.out.println("Etwas loeschen (257)... ");
		stuff.remove(257);
		stuff.returnAll();
		System.out.println("Etwas loeschen (1)... ");
		stuff.remove(1);
		stuff.returnAll();
		System.out.println("Ende des Programms.");
	}

}
```

Viele Grüße,
Semo


----------

