# Generics ... VerketteteListe<T> extends ArrayList<T>



## I2oxxi (18. Januar 2012)

Also ich soll eine eigene Verkettete Liste schreiben, mit diesem Generics gedöhns ^^ Is grad neu in der Vorlesung. Dazu noch ne Klasse ListenElement<T>.
Soweit sogut, hab mich im Inet schlau gemacht, was gefunden und mal angefangen.
Verkettete Listen sollen ja Vorgänger und Nachfolger haben, hab mir das ganze dann so vorgestellt:

ListenElement<T>

```
package aufgabe1;

public class ListenElement<T> {
	
	private T object;
	private ListenElement<T> nachfolger;
	private ListenElement<T> vorgänger;
	
	public ListenElement()
	{
	
	}
	
	public ListenElement(T object)
	{
		this.object=object;
	}
	
	public ListenElement<T> getVorgänger()
	{
		return this.vorgänger;
	}
	
	public ListenElement<T> getNachfolger()
	{
		return this.nachfolger;
	}
	
	public void setVorgänger(ListenElement<T> element)
	{
		this.vorgänger=element;
	}
	
	public void setNachfolger(ListenElement<T> element)
	{
		this.nachfolger=element;
	}

}
```

Dürfte denk ich passen. Das Problem jetzt mit der Liste selber:

VerketteteListe<T>:

```
package aufgabe1;

import java.util.*;

public class VerketteteListe<T> extends AbstractList<T> {

	private ListenElement<T> start;
	private ListenElement<T> ende;
	
	public VerketteteListe()
	{
		start = new ListenElement<T>();
		ende = new ListenElement<T>();
		start.setVorgänger(null);
		start.setNachfolger(ende);
		ende.setVorgänger(start);
		ende.setNachfolger(null);
	}
	

	public int size() 
	public boolean add(T element)
	public void add(int index, T element)
	public void clear()
	public T get(int index)
	public T remove(int index)
	public T set(int index, T element)

}
```
Rümpfe hab ich weggelassen, sind imo eh leer.
Am Anfang hat die Liste ja Anfang und Ende (habs im Inet so gelesen).
Vorm Anfang is nix (null) und nach dem Ende halt au nix.
Aber wie geht nun weiter? Wie fülle ich die Rümpfe?
bei size() habe ich mir z.B. gedacht, sowas wie gehe immer weiter zum nächsten Nachfolger und zähle nen Zähler immer um 1 hoch, bis der Null Pointer kommt.
Da dies ja über Generics läuft, kann ich dort nicht einfach t.getnachfolger() machen...

btw: Die Methoden müssen nach Aufgabe alle implementiert (überschrieben) werden.
Ich darf in dieser Aufgabe keine Collection oder Arrays verwenden.

Ich hoffe ihr versteht iwie wo mein Problem liegt


----------



## CPoly (18. Januar 2012)

Deine Idee für size() ist völlig korrekt. Aber dein Problem mit t.getnachfolger() verstehe ich nicht, aber Generics sind ja auch neu für dich.

Hier mal beispielhaft die size() Methode


```
T tmp = this.start;
int counter = 0;

while(tmp != null) {
    tmp = tmp.getNachfolger();
    counter++;
}

return counter;
```


Ich würde deine "VerketteteListe" Klasse noch etwas ändern. Aktuell hat diese ja von Beginn an zwei Elemente. Ich würde Sie am Anfang leer lassen (start und ende auf null).


Edit: Üblicherweise brauchst du in der size() Methode gar nichts zu programmieren, sondern du zählst in add(), remove() und clear() einfach die Anzahl mit.


----------



## I2oxxi (18. Januar 2012)

Danke, für die Antwort, ich schau mal mit deim Code das ich die Syntax für die andren schaff.
Falls noch fragen aufkommen editier ichs rein.
Die Size muss rein, da die durch das extends als abstact von Collection kommt.

Edit:: Kann es sein, das ich bei jeder Methode eigentlich nur Start setze und dann so mit einer while schleife durchgehe? also z.B. bei add dann genau das gleiche, bis der pointer null sagt, und dann das element nehmen, was den nullpointer wirft, und nachfolger setzen, richtig?


Edit2:: hier schon das erste problem:

```
public boolean add(T element)
	{
		ListenElement<T> elem = this.start;
		 
		while(elem != null) 
		{
		    elem = elem.getNachfolger();
		}
		elem.setNachfolger(element);
		element.setNachfolger(null);
		 
		return true;
	}
```

Die Nachfolger sind ungültig, da der Typ nicht stimmen würde ...
Ist wohl alles bischen anders mit den Generics ^^

Ich finds  eh sinnlos die VerketteteListe mit <T> zu machen wenn ja eh ListElement<T> daa rein soll ... naja ...


----------



## CPoly (18. Januar 2012)

Dass du die Methode "size()" brauchst kann ja sein, aber das heißt nicht, dass du nicht intern die Größe mit zählen kannst und in der Methode nur "return this.size" schreibst.


Der Nachfolger muss vom Typ ListElement<T> sein und nicht vom Typ T.


```
//falsch
elem.setNachfolger(element);

//richtig
elem.setNachfolger(new ListenElement<T>(element));
```


----------



## I2oxxi (18. Januar 2012)

ok, also muss ich ganz genau aufpassen dabei, hab das einfach übersehen bzw nicht gemerkt was ich ändern muss. ok hat alles ganz gut geklappt bis jetz, hab nur grad gemerkt das ich bei add etc auch noch das objekt als nachfolger vom vorgänger setzen muss ... hach is das ein wirr warr ^^


----------



## CPoly (18. Januar 2012)

I2oxxi hat gesagt.:


> hab nur grad gemerkt das ich bei add etc auch noch das objekt als nachfolger vom vorgänger setzen muss ... hach is das ein wirr warr ^^



Ja, das sind halt die Grundlagen ;-). Listen, Bäume, Graphen etc. sollte man alles mal selbst implementiert haben.


----------



## I2oxxi (18. Januar 2012)

Ja, hab schon viel gemacht, nur Java nie wirklich ^^ hab  vorher 4 Jahre c und  c++ programmiert aber jetzt durchs Studium muss ich Java. 
Und Generics, wie ich jetzt gelesen habe gibt es zwar in C++, sind mir aber nie unter die Augen gekommen ^^




Hab jetzt alle Methoden fertig, kann aber leider nix testen, in der add is noch ein Fehler ...

```
public boolean add(T element)
	{
		ListenElement<T> elementInList = this.start;
		 
		while(elementInList != null) 
		{
			elementInList = elementInList.getNachfolger();
		}
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		elementInList.setNachfolger(dranhängen);
		dranhängen.setVorgänger(elementInList);
		dranhängen.setNachfolger(null);
		 
		return true;
	}
```

elementInList.setNachfolger(dranhängen);      ->    Can only be null at this location


komischerweise hab ich das hier nicht:

```
public void add(int index, T element)
	{
		ListenElement<T> elementInList = this.start;
		 
		for(int i=0;i<index;i++)
		{
			elementInList = elementInList.getNachfolger();
		}
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		elementInList.setNachfolger(dranhängen);
		dranhängen.setVorgänger(elementInList);
		dranhängen.setNachfolger(null);
	}
```
wobei dies am ende trotzdem ne NullPointerException schmeißt

btw: bei start und ende im konstruktor steht jetz nurnoch wie du vorgeschlagen hast 
start=null;
ende=null;

sind aber halt in der klasse als private ListenElement<T> deklariert

Kanns du mir vllt auch verraten wieso die abstrackte Methode add(T) bool zurückgibt?
könnte mir höchsten vorstellen das mir try zu machen und true zurück wenns geklappt hat, aber wieso hat add(index,T) dann nur void?
Scheins dich ja gut auszukennen


----------



## CPoly (18. Januar 2012)

Naja, wenn du ein Element an Stelle 10 einfügen willst, aber nur 5 Elemente in der Liste sind, läuft die Schleife in die NULL rein. Deshalb solltest du die Zahl der Elemente mitzählen und darauf prüfen.


```
public void add(int index, T element) {
    if(index > this.numElements) {
        throw new ArrayIndexOutOfBoundsException("You can't add an Element add position " + index);
    }

    //Dein Code
}
```


----------



## I2oxxi (18. Januar 2012)

ja, sowas kenn ich ja, meine for schleife läuft doch aber über den index, worauf ich in  der main selbs noch bestimme wos geaddet wird. und v1.add(0,s1); gibt mir schon ne nulltpointerexception (s1 is ein objekt, v1 die liste). 
Und die boolean add(obj) geht ja ans ende und will dranhängen.

ich glaube ich hab den fehler gefunden.
start ist ja null
elementinliste ist start
elementinliste läuft durch
elementinliste wird letztes element bzw element am index 
elementinliste.addnachfolger(obj)

da es mal null war kann es die methoden nicht anwenden, weil nie eine instanz erstellt wurde.
hier sollte ich die methoden von ListElement<T> dann static machen, oder?
Oder bin ich jetzt komplett auf nem falschen dampfer? ^^
habe meine ich in der letzten vorlesung nachmal den satz gehört, das static da ist um ne methode ohne gebildete instanz aufzurufen. 
hab nie gerafft wofür static ist habs nie gebraucht aber das war doch dafür um methoden ohne instanz zu nutzen richtig? ^^


----------



## CPoly (18. Januar 2012)

static hilft dir da nichts. Was du machen muss ist einfach eine Sonderbehandlung für den Fall, das start/nde == null ist.


```
public void add(int index, T element) {
    //Index Prüfung


    //Sonderfall bei leerer Liste
    if(this.start == null) {
        this.start = this.ende = new ListenElement<T>(element);
        return;
    }

    //Schleifen Kram
}
```


----------



## I2oxxi (18. Januar 2012)

Ichglaube jetzt reden wir grade aneinander vorbei, jedenfalls weiß ich nicht was deins helfen soll.
Habs aber trotzdem ausprobiert, kommt immernoch das selbe

```
public void add(int index, T element)
	{
	    if(index > this.size())
	    {
	        throw new ArrayIndexOutOfBoundsException("You can't add an Element add position " + index);
	    }
	    
	    if(this.start == null)
	    {
	        this.start = this.ende = new ListenElement<T>(element);
	        return;
	    }
		ListenElement<T> elementInList = this.start;
		 
		for(int i=0;i<index;i++)
		{
			elementInList = elementInList.getNachfolger();
		}
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		elementInList.setNachfolger(dranhängen);
		dranhängen.setVorgänger(elementInList);
		dranhängen.setNachfolger(null);
	}
```

das Problem ist ja kein outofbounds, wie schon gesagt, sowas wird bei mir ja durch eigene eingabe in der main noch bestimmt, und die boolean add() ohne index, die hinten dranhängt, hat ja das selbe problem.
start und ende sind ja so oder so auf null, hab ich ja auf deine empfehlung noch auf null gesetzt.

das elementinlist.setnachfolger(dranhängen) schmeißt ne nullpointer, eclipse warnt auch schon "can only be null at this location"


----------



## CPoly (18. Januar 2012)

Kannst du die ganze Klasse samt main mal zeigen? Ich kann dir jetzt mit den paar Zeilen nicht weiter helfen.


----------



## I2oxxi (18. Januar 2012)

Klar:

ListenElement:

```
package aufgabe1;

public class ListenElement<T> {
	
	private T object;
	private ListenElement<T> nachfolger;
	private ListenElement<T> vorgänger;
	
	public ListenElement()
	{
	
	}
	
	public ListenElement(T object)
	{
		this.object=object;
	}
	
	public ListenElement<T> getVorgänger()
	{
		return this.vorgänger;
	}
	
	public ListenElement<T> getNachfolger()
	{
		return this.nachfolger;
	}
	
	public void setVorgänger(ListenElement<T> element)
	{
		this.vorgänger=element;
	}
	
	public void setNachfolger(ListenElement<T> element)
	{
		this.nachfolger=element;
	}

}
```

VerketteteListe:

```
package aufgabe1;

import java.util.*;

public class VerketteteListe<T> extends AbstractList<T> {

	private ListenElement<T> start;
	private ListenElement<T> ende;
	
	public VerketteteListe()
	{
		start = null;
		ende=null;
	}
	

	public int size() 
	{
		ListenElement<T> element = this.start;
		int counter = 0;
		 
		while(element != null) {
		    element = element.getNachfolger();
		    counter++;
		}
		 
		return counter;
	}
	
	public boolean add(T element)
	{
	    if(this.start == null)
	    {
	        this.start = this.ende = new ListenElement<T>(element);
	        return false;
	    }
		ListenElement<T> elementInList = this.start;
		 
		while(elementInList != null) 
		{
			elementInList = elementInList.getNachfolger();
		}
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		elementInList.setNachfolger(dranhängen);
		dranhängen.setVorgänger(elementInList);
		dranhängen.setNachfolger(null);
		 
		return true;
	}
	
	public void add(int index, T element)
	{
	    if(index > this.size())
	    {
	        throw new ArrayIndexOutOfBoundsException("You can't add an Element add position " + index);
	    }
	    
	    if(this.start == null)
	    {
	        this.start = this.ende = new ListenElement<T>(element);
	        return;
	    }
		ListenElement<T> elementInList = this.start;
		 
		for(int i=0;i<index;i++)
		{
			elementInList = elementInList.getNachfolger();
		}
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		elementInList.setNachfolger(dranhängen);
		dranhängen.setVorgänger(elementInList);
		dranhängen.setNachfolger(null);
	}
	
	public void clear()
	{
		ListenElement<T> element = this.start;
		 
		for(int i=0; i<this.size();i++)
		{
			element=null;
		    element = element.getNachfolger();
		}
	}
	
	public T get(int index)
	{
		ListenElement<T> element = this.start;
		for(int i=0; i<index;i++)
		{
			element = element.getNachfolger();
		}
		
		T t = (T) element;
		
		return t;
	}
	
	public T remove(int index)
	{
		return null;
		
	}
	
	public T set(int index, T element)
	{
		return null;
	}

}
```

Simulierung aka Main(Da schneid ich jetz mal das grundlegende raus, ich hab objekte der klasse studen bli bla blub die heißen s1 s2 s3)

```
package aufgabe1;

import java.util.ArrayList;

public class Simulierung {


	public static void main(String[] args) 
        {
		VerketteteListe<Student> v1 = new VerketteteListe<Student>();
		
		v1.add(0,s1);
		v1.add(1,s2);
		v1.add(2,s3);
		
		System.out.println(v1.size());
		
		
	}

}
```


ich denke ich kann das anfang/ende wohl doch nicht einfach null setzen, daher kommt das wohl.
weil objekt, was null ist, kann ja schlecht dann nachfolger() aufrufen


Edit:: Hab jetzt selber noch ein bischen rumgebastelt um das ganze ander zu gestalten, so erscheint mir das eig auch ziemlich logisch, klappt aber trotzdem nicht:

```
public boolean add(T element)
	{
		ListenElement<T> elementInList = this.start;
		 
		while(elementInList != null) 
		{
			elementInList = elementInList.getNachfolger();
		}
		
		ListenElement<T> dranhängen = new ListenElement<T>(element);
		
		dranhängen.setVorgänger(elementInList);
		
		if(dranhängen.getVorgänger()==null)
		{
			this.start = new ListenElement<T>(element);
			this.start.setVorgänger(null);
			this.start.setNachfolger(null);
			return true;
		}
		else
		{
			dranhängen.setNachfolger(null);
			dranhängen.getVorgänger().setNachfolger(dranhängen);
			return true;
		}
	}
```


----------



## Fabio Hellmann (19. Januar 2012)

Hi,
du kannst dir auch mal die Klasse Vector ansehen zu dem Thema. Vielleicht kannst du davon ein wenig abkupfern. 

Gruß

Fabio


----------



## CPoly (19. Januar 2012)

Ganz einfach


```
//Vorher
for(int i=0; i < index; i++)

//Nachher
for(int i=0; i < index - 1; i++)
```


Und das Problem bei add (ohne index) ist das gleiche. Du läufst genau ein Element zu weit. Aber üblicherweise würde man das so machen:


```
public boolean add(T element)
{
    return add(size(), element);
}
```


----------



## I2oxxi (19. Januar 2012)

ändert leider nix, immernoch gleiche ausgabe. 
wäre mid -1 ja aber auch unlogisch der index fängt ja bei 0 an, und wenn man 0 übergibt wäre for(int i=0; i < 0-1;i++), womit die schleife übersprungen wird, genau wie bei index 1.
wie gesagt, das problem ist nicht outofbounds.
ich hab da grad ne idee, das das alles nicht klappt weils über nen start pointer läuft, ich versuch grad was umzubauen das ein hilfsobjekt erstellt wird, das sich wie start verhält, und das es dann dadrüber die schleife durchgeht


----------



## CPoly (19. Januar 2012)

Ich rate ja nicht rum. Ich kann es mit den Änderungen kompilieren, Elemente einfügen und bekomme die korrekte Anzahl ausgegeben.


----------



## I2oxxi (19. Januar 2012)

hm also  ich hab deins übernommen und bekam immernoch die falsche anzahl. 
jedoch habe ich es jetzt so umgeschrieben, das es bei mir funktioniert:

```
public boolean add(T element)
	{
		ListenElement<T> elementInList = this.start;
		if(elementInList==null)
		{
			this.start = new ListenElement<T>(element);
			this.start.setNachfolger(null);
			this.start.setVorgänger(null);
		}
		else
		{
			while(elementInList.getNachfolger()!=null)
			{
				elementInList=elementInList.getNachfolger();
			}
			ListenElement<T> myElement = new ListenElement<T>(element);
			myElement.setNachfolger(null);
			myElement.setVorgänger(elementInList);
			elementInList.setNachfolger(myElement);
		}
		
		return true;
	}
```


Edit:: meine add(index,obj) klappt jetzt auch, da konnte ich dine index-1 gebrauchen  

```
public void add(int index, T element)
	{
		ListenElement<T> elementInList = this.start;
		if(index==0)
		{
			if(elementInList==null)
			{
				this.start = new ListenElement<T>(element);
				this.start.setNachfolger(null);
				this.start.setVorgänger(null);
			}
			else
			{
				ListenElement<T> hilfselement = new ListenElement<T>(this.start.getObj());
				
				hilfselement.setNachfolger(this.start.getNachfolger());
				hilfselement.setVorgänger(this.start);
				this.start.setObj(element);
				this.start.setVorgänger(null);
				this.start.setNachfolger(hilfselement);
				
				
				
			}
		}
		else if(index==1)
		{
			ListenElement<T> myElement = new ListenElement<T>(element);
			myElement.setVorgänger(this.start);
			myElement.setNachfolger(this.start.getNachfolger());
			if(this.start.getNachfolger()!=null)
			{
				this.start.getNachfolger().setVorgänger(myElement);
			}
			this.start.setNachfolger(myElement);
		}
		else
		{
			for(int i=0; i<index-1; i++)
			{
				elementInList=elementInList.getNachfolger();
			}
			ListenElement<T> myElement = new ListenElement<T>(element);
			myElement.setVorgänger(elementInList);
			if(elementInList.getNachfolger()==null)
			{
				myElement.setNachfolger(null);
			}
			else
			{
				myElement.setNachfolger(elementInList.getNachfolger());
				elementInList.getNachfolger().setVorgänger(myElement);
			}
			elementInList.setNachfolger(myElement);
			
		}
		
	}
```

Edit2::
Ich hab da nochmal ne ganz Java spezifische frage. clear soll ja die liste löschen. Wie läuft das jetzt mit dem Garbage Collector ab? Objekte kann man ja nicht selbs löschen, richtig?
heißt, für clear muss ich eigentlich nur start=null machen, und da so keine verbindungmehr besteht, da der startpointer leer is wird ja die ganze liste leer, die objekte werden dann von allein gelöscht da sie nicht mehr genutzt werden?


Edit::
Ok, ich habe jetzt alle methoden fertig und alles klappt, das einzige was zu fehlern in der liste führt ist wenn ich add(0,obj) mache, wenn schon ein objekt auf null liegt, also das objekt an die erste stelle gesetzt werden soll (als start) und dann das vorherige start element folgt.
 bei 0 klappt iwas nicht da verhaut der mir die ganze liste.
ist jetzt nur der ausschnitt für den fall 0, hab ja mit if ein paar sonderfälle extra behandelt

```
public void add(int index, T element)
	{
		ListenElement<T> elementInList = this.start;
		if(index==0)
		{
			if(elementInList==null)
			{
				this.start = new ListenElement<T>(element);
				this.start.setNachfolger(null);
				this.start.setVorgänger(null);
			}
			else
			{
				elementInList=new ListenElement<T>(this.start.getObj());
				elementInList.setNachfolger(this.start.getNachfolger());
				this.start.setObj(element);
				this.start.setNachfolger(elementInList);
				this.start.setVorgänger(null);
				elementInList.setVorgänger(this.start);
			}
        }
    }
```
eigentlich kommen halt noch fall für index=1 und index > 1 aber das hab ich jetz mal weggelassen, das funktioniert alles. nur bei add(0,obj) wenn schon was auf 0 existiert nicht .... also muss der fehler in dem  else block liegen. hab auch schon mit this.start = new ListenElement<T>(element); versucht aber des klappt au nich, da verhauts mir auch die liste


----------

