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:
Und hier die Klasse DLinkedList, in der die doppelt verkettete Liste implementiert ist:
Das Problem muss wohl irgendwo in der add-Methode liegen, denn isEmpty() wird nocht ausgeführt. Die add-Methode allerings ist ne Endlosschleife...
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) );
}
}
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...
