Listen und Generics

[ETlearner]

hallo,
habe wieder mal hausaufgaben im hassfach

heir sind die aufgaben(bitte nicht abschrecken, sind nur anfängersachen!!!)

Aufgabe 1 Einfach verkettete Liste
1. Implementieren Sie eine generische Klasse SingleLinkedList<T>, die eine einfach verkettete
Liste von Elementen eines beliebigen Datentyps T darstellt. Sie soll eine innere Klasse
Node enthalten, die ein Element der Liste symbolisiert. Jeder Knoten muss eine Referenz
auf seinen Wert (vom Typ T) und eine Referenz auf den Nachfolgeknoten enthalten. Die
Liste selbst sollte Referenzen auf den ersten und den letzten Knoten besitzen.
2. Implementieren Sie einen parameterlosen Konstruktor SingleLinkedList(), der eine leere
Liste initialisiert.
3. Implementieren Sie einen Konstruktor SingleLinkedList(T[] elements), der eine Liste
initialisiert, welche bereits mit den Elementen im ubergebenen Array gefullt ist.


Aufgabe 2 Listenmethoden
1. Implementieren Sie die Methode void appendHead(T element), die ein neues Element
an den Anfang der Liste anfugt.
2. Implementieren Sie die Methode T popHead(), die das Element am Anfang der Liste
zuruckgibt und entfernt.
3. Implementieren Sie die Methode void appendTail(T element), die ein neues Element
an das Ende der Liste anfugt.
4. Implementieren Sie die Methode T popTail(), die das Element am Ende der Liste zuruckgibt
und entfernt.
Hinweis: Bedenken Sie bei allen Methoden den Sonderfall einer leeren oder einelementigen Liste.
Wenn versucht wird, ein Element aus einer leeren Liste zu entfernen, sollte die Methode den
Zustand der Liste nicht andern und null zuruckgeben.


Aufgabe 3 Test
Schreiben Sie eine Klasse TestListe, die einen Test Ihrer Listenimplementation erlaubt. Die
main-Methode soll eine Liste von Strings mit vier vorgegebenen Elementen erzeugen und mit
Hilfe der toString-Methode ausgeben. Testen Sie dann jede Methode zum Hinzufugen oder
Loschen von Elementen mindestens einmal und lassen Sie die Liste nach jedem Schritt erneut
ausgeben. Sie sollten dabei die Liste mindestens einmal komplett leeren und danach wieder
Elemente anfugen.

und hier sind meine 2 klassen...
bei beidem klappt die kompilierung, doch auf der console wird die folgende warnung ausgegeben:

Note:Testliste.java uses unchecked or unsafe operations
Note:Recompile with -Xlint:unchecked for details

public class SingleLinkedList <T> {

					private class Node{
						public T element;
						public Node next;
		
						public Node( T element){
							this.element=element;
							next=null;
							}
			
						public Node (T element, Node ref){
							this.element = element;
							this.next = ref;
							}
			
					}

	
	public Node head;
	public Node end;
	public SingleLinkedList(){		//Konstruktor, de eine leere Liste initialisiert
		head.next=end;
		end.next=null;
		}
	
	public SingleLinkedList (T[] elements){
		head.next=end;
		end.next=null;
		SingleLinkedList<T> L= new SingleLinkedList();
		for(int i=elements.length-1; i>=0; i--){
			L.appendHead(elements[i]);
			}
	}
	
	public void appendHead(T element){
		Node n=new Node(element);
		Node a= head.next;
		head.next=n;
		n.next=a;
		}
		
	T popHead(){
		if(head.next==end){ return null;}
		else{ 
			Node Anfang=head.next;
			head.next=head.next.next;
			return (T)Anfang;}
			
	}
	
	void appendTail(T element){
		if(head.next==end){appendHead(element);}
		else{
			Node v=head.next;
			while(v.next != null){
				v=v.next;}
			Node a=new Node(element);
			v.next=a;
			}
	}
	
	T popTail(){
		if(head.next==end){return null;}
		else{
			Node v=head.next;
			while (v.next!= null){
				v=v.next;}
			Node letztes=v;
			Node w=head.next;
			while(w.next!=v){
				w=w.next;}
			w.next=null;
			return (T) letztes;
			}
	}
	
	
		
			
}

public class TestListe{
	
	
	
	
	public static void main (String[]args){
		String[]a=new String[4];
		a[0]="Informatik";
		a[1]="ist";
		a[2]="mega-";
		a[3]="S*****e!";
		
	SingleLinkedList <String> A= new SingleLinkedList(a);
	
	//TESTE METHODE popHead()
	
	System.out.println(A.popHead());//wird "Informatik" ausgegeben?
	A.toString(); //wurde das erste Element gelöscht?
	
	//TESTE METHODE popTail()
	
	System.out.println(A.popTail());// wird "S*****e!" ausgegeben?
	A.toString(); //wurde das letzte Element gelöscht?
	
	//wir leeren die list : da es nur noch 2 elemente gibt muss man die
	// Methode potail() 2 mal aufrugen
	A.popTail();
	A.popTail();
	A.toString(); //ist die liste jetzt leer?
	
	// TESTE METHODE appendHEAD()
	A.appendHead("NEIN DAS STIMMT DOCH NICHT");
	A.toString();// wurde das element hinzugefügt?
	
	//TESTE METHODE appendTail()
	A.appendTail("INFO IST NICHT S*****E");
	A.toString();// wurde das element hinzugefügt?
	
	}
	
	
}

ich würde mich sehr auf antworten freuen

danke im vorraus

 

[julian.veh]

 SingleLinkedList<String> A= new SingleLinkedList<String>(a);

Ich denke das sollte das erste Problem beheben, wenn ich die Fehlermeldung richtig verstehe

 

[ETlearner]

danke für die schnelle antwort. habe es sofort geändert
warum erhalte ich den warnungen?i( 12 warnungen)
waurum gibt die konsole keine fehermeldungen aus, wenn etwas falsch ist?

 

[Sesostris]

Du verwendest an mehreren Stellen Typecasts, daher die Warnung "unchecked or unsafe operations". Genau denen will man doch mittels Generics aus dem Weg gehen. In deinem Fall geht das auch ganz einfach:

return Anfang.element;

statt

return (T)Anfang;

Du willst schließlich nicht einen Knoten zurückgeben, sondern das "darin gespeicherte" Element vom Typ T.

Ich fürchte aber, dass dein Programm trotzdem nicht funktionieren wird. Da sind viele kleine Logikfehler. Bekommst du beim Ausführen keine Exception?

 

[ETlearner]

leider keine

 

[Sesostris]

Wenn ich TestListe ausführe, bekomme ich:

Exception in thread "main" java.lang.NullPointerException
	at SingleLinkedList.<init>(SingleLinkedList.java:28)
	at TestListe.main(TestListe.java:12)

Das war auch zu erwarten, da du von head und end nie ein Objekt erzeugt hast. Folglich sind das Nullreferenzen, auf deren Instanzvariablen du nicht einfach so zugreifen kannst.

 

[ETlearner]

danke für die hinweise.
habe jetzt den quellcode verändert und das programm läuft endlich.
doch bei der methode poptail() wird das letzte element richtig entfernt, jedoch nicht ausgegeben...
und bei der methode appendtail() wird nicht das richtige element an das ende hinzugefügt...
sind die methoden falsch implementiert worden?

public class SingleLinkedList <T> {
 
                    public class Node{
                        public T element;
                        public Node next;
        
                        public Node( T element){
                            this.element=element;
                            next=null;
                            }
            
                        public Node (T element, Node ref){
                            this.element = element;
                            this.next = ref;
                            }
            
                    }
 
    
    public Node head=new Node(null);
    public Node end=new Node(null);
    public SingleLinkedList(){      //Konstruktor, de eine leere Liste initialisiert
        head.next=end;
        end.next=null;
        }
    
    public SingleLinkedList (T[] elements){
        head.next=end;
        end.next=null;
        SingleLinkedList<T> L= new SingleLinkedList();
        for(int i=elements.length-1; i>=0; i--){
            L.appendHead(elements[i]);
            }
    }
    
    public void appendHead(T element){
        Node n=new Node(element);
        Node a= head.next;
        head.next=n;
        n.next=a;
        }
        
    T popHead(){
       
			if(head.next==end){ return null;}
			else{
            Node Anfang=head.next;
            head.next=head.next.next;
            return Anfang.element;}
            
    }
    
    void appendTail(T element){
        if(head.next==end){appendHead(element);}
        else{
            Node v=head.next;
            while(v.next != null){
                v=v.next;}
            Node a=new Node(element);
            v.next=a;
            }
    }
    
    T popTail(){
        if(head.next==end){return null;}
        else{
            Node v=head.next;
            while (v.next!= null){
                v=v.next;}
            
            Node w=head.next;
            while(w.next!=v){
                w=w.next;}
			Node letztes=w.next;
            w.next=null;
            return letztes.element;
            }
    }
    
	public String toString() {
			if(this.head.next==null){return "Liste ist leer!";}
			else{
			String b = "";
			Node v=head.next;
				while(v.next!=null){
					b=b+"   "+v.element;
					v=v.next;}

				return b;}}
  }

public class TestListe{
	  
	
	
	
	public static void main (String[]args){
	
		
	SingleLinkedList<String> A= new SingleLinkedList<String>(); //leere Liste erzeugen
	A.appendHead("ehemalige Optimisten.");
	A.appendHead(" anderes als ");
	A.appendHead("sind nichts ");
	A.appendHead("Pessimisten ");
	System.out.println(A.toString()); //wird die ganze Liste in der richtigen reihenfolge ausgegeben?(funktioniert)
	
	//TESTE METHODE popHead()
	
	System.out.println(A.popHead());//wird "Pessimisten" ausgegeben? (funktioniert)
	System.out.println(A.toString()); //wurde das erste Element gelöscht?(funktioniert)
	
	
	
	//TESTE METHODE popTail()
	
	System.out.println(A.popTail());// wird "ehemalige Optimisten." ausgegeben?                        <<<<<<<<----------------(funktioniert NICHT)
	System.out.println(A.toString()); //wurde das letzte Element gelöscht?(funktioniert)
	

	
	//wir leeren die list : da es nur noch 2 elemente gibt muss man die
	// Methode potail() 2 mal aufrugen (funktioniert)
	A.popTail();
	A.popTail();
	
	System.out.println(A.toString()); //ist die liste jetzt leer?, dann werden mehrere  leere zeile	ausgegeben	 (funktioniert)			
	System.out.println(A.toString());
	System.out.println(A.toString());
	System.out.println(A.toString());

	// TESTE METHODE appendHEAD()
	A.appendHead("JA!");
	System.out.println(A.toString());// wurde das element hinzugefügt?(funktioniert)
	
	
	
	//TESTE METHODE appendTail()
	A.appendTail("DA HAST DU RECHT!");
	System.out.println(A.toString());// wurde das element hinzugefügt?					<<<<<<<--------------(funktioniert nicht!)
	}
	
	
}

danke im voraus

 

[SlaterB]

du beachtest einfach nicht, dass am Ende noch ein leerer Node steht, ähnlich dem am Anfang,
welchen du bei appendHead + popHead überspringst,

ich habe es jetzt bisschen untersucht und könnte mir natürlich richtigen Code ausdenken,
aber das ist ja gerade deine Aufgabe, da habe ich eigentlich genug Hinweis gegeben, welcher sowieso schon offensichtlich ist,

repariere erst appendTail(), fange mit einer leeren Liste und füge ein Element,
bzw. zwei, vorher zeigt deine Ausgabe den Fehler nicht,

mache das sowohl im Code (temporär neue main-Methode) als auch auf Papier,
überlege dir genau, welches Nodes es gibt, mit welchen Verknüpfungen,

auch die leeren Begin/ End-Nodes aufmalen und besonders auch vorerst im Programm in das toString() usw. integrieren!
es hilft nichts, diese in Logausgaben der Schönheit wegen zu überspringen, wenn du dann nicht genau weißt, was in deinem Programm exakt vorgeht

in Methoden wie appendTail() dürfen auch viele Logausgaben rein, was wird warum übersprungen,
welcher Node letztlich ausgewählt, was angehangen usw.

 

[fastjack]

Nur zur Info: mal mit

-Xlint:unchecked

kompilieren?

 

[Sesostris]

Ich glaube, mein letzter Hinweis ist etwas missverstanden worden: Ich meinte eigentlich nicht, dass du Objekte von head bzw. end erzeugen, sondern auf die undefinierten Instanzvariablen verzichten solltest. Es reicht, wenn head auf den ersten Knoten zeigt, ohne selbst ein eigenes Knoten-Objekt zu sein.
Und dein end zeigt überhaupt ins nirgendwo. Du setzt es im Konstruktur auf null, aber dann änderst du es nie wieder.

Ich habe dir einmal die appendHead-Methode korrigiert:

    public void appendHead(T element) {
    	Node n = new Node(element);
    	if (head == null) { // leere Liste?
    		head = end = n; // wenn  ja, dann gibt nur den neuen Knoten, der zugleich der erste (head) und der letzte (end) ist
    	} else {
    		n.next = head; // andernfalls wird der erste zum zweiten Knoten
    		head = n; // und der eben hinzugefügte Knoten ist nun der erste
    	}
    }