Überprüfung einer Aufgabe zu verketteten Listen

[townandroid]

Hallo,

ich bin gerade dabei, ein paar Aufgaben vor der Klausur (Programmierung I) zu lösen und wollte fragen, ob ihr mich bei meinen Lösungen auf Fehler hinweisen könntet.
Ich könnte eigentlich auch eine Liste erstellen und dann ein wenig rumtesten, aber dabei könnte ich ja etwas übersehen, also wäre es sehr nett, wenn ihr schnell einen Blick drüberwerfen könntet.🙂

Also die Aufgabe lautet:
Implementieren Sie eine doppelt verkettete Liste mittels der Klassen Node und List. Die Liste soll Objekte vom Typ String speichern und folgende Methoden besitzen.

1. public void display(): gibt die gesamte Liste (d.h., den Inhalt aller Knoten) beginnend mit dem ersten Knoten auf der Konsole aus.

2. public void add(int i, String content): fügt den übergebenen String an Position i in die Liste ein.

3. public void remove(int pos): löscht das Element an Stelle i aus der Liste.

Zuerst die Klasse Node.
Da die Knoten ja doppelt verknüpft sein müssen, einmal prev und einmal next.
Dann habe ich noch die Methode toString() neu geschrieben, sodass ich den Inhalt der Knoten ausgeben kann und ich habe noch Getter und Setter für prev und next eingefügt.

public class Node {
	
	String data;
	Node next;
	Node prev;
	
	Node(String data) {
		
		this.data = data;
		next = null;
		prev = null;
	}
	
	public String toString() {
		
		return "{" + data + "} ";
	}
	
	public void setNextNode(Node n) {
		this.next = n;
	}
	
	public Node getNextNode() {
		return next;
	}
	
	public void setPrevNode(Node n) {
		this.prev = n;
	}
	
	public Node getPrevNode() {
		return prev;
	}

}

Und die Klasse List.
Diese braucht ja einmal Zugriff auf den Anfang und auf das Ende.

public class List {
	
	Node front;
	Node rear;
	
	List(Node a, Node b) {
		this.front = a;
		this.rear = b;
	}
	
	public boolean isEmpty() {
		return front == null;
	}

Die erste Methode.
Wenn die Liste leer ist, wird das mitgeteilt und ansonsten sollte das so passen.

public void display() {
		
		if(front == null) {
			System.out.println("The list is empty");
		} else {
			
			
			for (Node it = front; it != null; it = it.next) {
				System.out.println(it);
			}
		}
	}

Dann die zweite Methode.
Hier frage ich mich, wenn die Liste leer ist, gibt es dann eine nullte Position? In dem Fall zeigen dann front und rear auf den selben Knoten
Ansonsten wird durchgelaufen und der Knoten eingefügt.
Und hier noch eine Frage, der letzte Knoten hat ja eine Nullpointer-Referenz, zählt diese auch als Position?
Wenn ja, würde ich sie aber auch nicht erreichen, weil ja nur die aktuelle Position abgefragt wird.

public void add(int i, String content) {
		if(front == null && i == 0) {         
			Node newNode = new Node(content); 
			front = newNode;
			rear = newNode;
		} else {
			Node it = front;
			int actPos;
			for (actPos = 0; it != null && actPos <i; actPos++) {
				it = it.next;
			}
			if(actPos == i) {
				Node newNode = new Node(content);
				newNode = it;
				it.prev = newNode;
				
			} else {
				System.out.println("There is no positon" + i + " in this list");
			}
		  
		}
	}

Und die letzte Methode.
Hier wird ja dann einfach der Knoten gelöscht, ich hoffe das passt.

public void remove(int pos) {
		
		if(front == null) {
			System.out.println("There is no position" + pos + " in this list");
		} else {
			
			Node it = front;
			int actPos;
			for (actPos = 0; actPos < pos && it != null; actPos++ ) {
				
				it = it.next;
			}
			if(actPos == pos) {
				rear = it.prev;
				it.prev.next = null;
			}
				
		}
		
	}

}

 

[Flown]

Ich könnte eigentlich auch eine Liste erstellen und dann ein wenig rumtesten, aber dabei könnte ich ja etwas übersehen, also wäre es sehr nett, wenn ihr schnell einen Blick drüberwerfen könntet.

Nimms mir jetzt nicht übel, aber hier ist keiner ein Tutor der dir deine Aufgaben testet. Das was du anfragst ist eigentlich deine Aufgabe.

Wir helfen hier gerne bei konkreten Problemen und Fragen, aber machen keine Codereviews (ohne das vorher ein Aufwand betrieben wurde).

Was ich dir sagen kann ist, versuch es selbst. Dann wirst du schnell feststellen, dass deine Methoden nicht funktionieren. Zumindest add/remove passen nicht.

 

[townandroid]

Ok, du hast natürlich Recht, ich habe ja selber noch gar nicht geschaut, ob die Methoden überhaupt funktionieren.
Ich melde mich bei Konkreterem wieder.

 

[townandroid]

Ich habe die Methoden add und remove umgeschrieben, das war wirklich ziemlich falsch.
Ich habe mir eine Lise gemacht und jeweils Elemente am Ende, am Anfang und irgendwo in der Mitte entfernt und Elemente am Anfang, am Ende und irgendwo in der Mitte hinzugefügt.

Die Liste sah auch immer so aus, wie ich mir das vorgestellt hatte, es hat auch jedes Element den richtigen Nachfolger und Vorgänger gehabt. Das sollte dann wohl ein Indiz für die Korrektheit der Methoden sein.

Die Methode add

public void add(int i, String content) { 
		if(front == null && i == 0) {        
			Node newNode = new Node(content); 
			front = newNode;                  
			rear = newNode;                   
		} else {
			Node it = front;
			int actPos;
			for (actPos = 0; it != null && actPos < i; actPos++) {
				it = it.next;
			}
			if(actPos == i) {
				if(it == front) {
				    Node newNode = new Node(content);			
				    newNode.next = it;
				    it.prev = newNode;
           		            front = newNode;
           		            newNode.prev = null;
				} else if(it == rear) {
					Node newNode = new Node(content);
					newNode.next = it;
					newNode.prev = it.prev;
					it.prev.next = newNode;
					it.prev = newNode;
					rear = newNode.next;
					
				} else {
					Node newNode = new Node(content);
					newNode.next = it;
					newNode.prev = it.prev;
					it.prev.next = newNode;
					it.prev = newNode;
				}
				
			} else {
			System.out.println("There is no positon" + i + " in this list");
			}
		  
		}
	}

Die Methode remove

public void remove(int pos) {
		
		if(front == null) {
			System.out.println("There is no position" + pos + " in this list");
		} else {
			
			Node it = front;
			int actPos;
			for (actPos = 0; actPos < pos && it != null; actPos++ ) {
				
				it = it.next;
				
			}
			if(actPos == pos) {       
                if(it == front) {       
                	it.next.prev = null; 
                	front = it.next;
                	it.next = null;
                } else if(it == rear) {
                	it.prev.next = null;
                	rear = it.prev;
                	it.prev = null;
                } else {
                	
                	it.prev.next = it.next;
                    it.next.prev = it.prev;
                	it.next = null;
                	it.prev = null;
                }

			}
				
		}
		
	}

 

[Flashed]

Theoretisch würdest du die Aufgabe auch so erfüllen:

import java.util.LinkedList;


public class MyList<string> extends LinkedList{
    
    public MyList(){
        super();
    }
    
    //Die Methode müsstest du trotzdem selbst ausprogrammieren, da LinkedList sowas nicht hat
    public void display(){
        this.forEach((s) -> {
            System.out.println(s);
        });
    }
    
        
    //Könntest du auch weglassen
    @Override
    public void add(int pIndex, Object pString){
        super.add(pIndex, (String)pString);
    }


    //Könntest du auch weglassen
    @Override
    public Object remove(int pIndex){
        return super.remove(pIndex);
    }
    
}

Wobei du die add und remove methode selbst gar nicht schreiben müsstest, da sie in LinkedList schon implementiert sind.

Innerhalb von LinkedList wird das ganze genau so gehandelt (mit Nodes, die die nächste und vorherige Node kennen) wie in der Aufgabenstellung verlangt. Ich weiß allerdings nicht wie dein Lehrer/Prof oder was auch immer das finden wird, da du es dir ja schon recht leicht machst damit 😛

Wenn du willst, kannst du dir ja das Ganze mal ansehen.
Einfach in netbeans/eclipse oder welche IDE auch immer du verwendest "LinkedList" schreiben und dann kann man normalerweise rechtsklick drauf machen und "go to declaration" oder irgendwas in die Richtung.

Beste Grüße Flashed</string>

 

[townandroid]

Danke für den Tipp, das habe ich mir auch schon angeschaut, aber in den Übungen haben wir das alles immer mit den Klassen Node und List geschrieben und auf den Aufgaben stünde dann glaube ich auch, dass man die Aufgabenstellung mittels Node und List implementieren soll, also die sind sich dessen schon bewusst.🙂