"LinkedList" einfach verkettete Liste, Probleme bei Umsetzung

[rendner[i]]

Ich wollte eine Verkettete Liste als Klasse zu erstellen.
Dabei fehlt mir aber des öfteren einfach der Überblick was man doch lieber in eine Extraklasse packen sollte und was nicht.

Momentan sieht das bis jetzt so aus:

Interface "IList"

interface IList
{
	
	function isEmpty(): Boolean
	
	// function insert( o: Object ): Boolean
	function insert( index: Number , o: Object ): Boolean
	
	function remove( o: Object ): Boolean
	
	function clear(): Void
	
	function contains( o: Object ): Boolean
}

Klasse "Linkable"

class Linkable
{
	
	public var o: Object;		
	public var next: Linkable;
	
	public function Linkable( o: Object )
	{
		this.o = o;
		next = null;
	}
}

Klasse "LinkedList"

class LinkedList 
	implements IList
{
	
	private var fstE: Object;		// first Element
	private var lstE: Object;		// last Elemnt
	
	private var l: Number;			// how many elements "contains" the list
	
	
	public function LinkedList( link: Object )
	{
		if( arguments.length )
		{
			lstE = fstE = new Linkable( link );	
			l = 1;
		}
		else
		{
			fstE = lstE = new Object();
			l = 0;
		}
	}
	
	public function clear(): Void
	{
		var tmp1: Object = fstE;
		var tmp2: Object = tmp1.next;
		
		while( tmp1 != null )
		{
			deleteLink( tmp1 );
			
			tmp1 = tmp2;
			tmp2 = tmp2.next;
		}
		
		l = 0;
	}
	
	private function deleteLink( link: Object ): Void
	{
		link.next = link.o = null;
		
		delete link;
	}
	
	public function get first(): Object		
	{ 
		return isEmpty() ? null : fstE.o; 	   
	}
	
	public function get last(): Object		
	{ 
		return isEmpty() ? null : lstE.o; 	   
	}
	
	public function isEmpty(): Boolean		
	{ 
		return ! l; 
	}
	
	public function get length(): Number		
	{ 
		return l; 
	}
	
	public function contains( o: Object ): Boolean
	{
		var tmp: Object = fstE;
		
		while( tmp.o != lstE.o )
		{
			if( tmp.o == o ) return true;
			
			tmp = tmp.next;
		}
		
		return false;
	}
	
	public function push( o: Object ): Void
	{
		if( ! contains( o ) )
		{
			lstE.next = new Linkable( o );
		
			lstE = lstE.next;
		
			l++;
		}
	}
	
	public function insert( index: Number , o: Object ): Boolean
	{
		if( ! isEmpty() )
		{
			if( index < length && index >= 0 )
			{
				if( ! contains( o )  )
				{
					var i = 0;
					var tmp: Object = fstE;
			
					while( i++ < index ) tmp = tmp.next;
			
					if( i != index )
					{
						tmp.o = o;
						l++;
						
						return true;
					}
				}
			}
		}
		 
		return false;
	}
	
	public function remove( o: Object ): Boolean
	{
		if( ! isEmpty() )
		{
			var tmp: Object = fstE;
		
			while( (tmp.next.o != o) && (tmp.next.next != null) ) tmp = tmp.next;
			
			if( tmp.next.o != o ) return false;
			
			deleteLink( tmp.next );
			
			lstE = tmp;
			l--;
			
			return true;
		}
		return false;
	}
	
	public function pop(): Boolean
	{
		if( ! isEmpty() )
		{
			var tmp: Object = fstE;
			
			while( tmp.next.next != null ) tmp = tmp.next;
		
			deleteLink( tmp.next );
			
			lstE = tmp;
			l--;
			
			return true;
		}
		
		return false; 
	}
}

Dabei bin ich auf folgende Fragen gestoßen:

"LinkedList":

- meine Membervariablen der Klasse "LinkedList" habe ich als "Object" definiert und nicht als "Linkable", da ich diese nur als Pointer nutzen und nur die Referenz auf das erste und das letzte Element in diesen speichern will.
Dabei hab ich immer die Funktionsweise von C-Pointern vor Augen, kann man das ungefähr vergleichen oder ist das bei Flash komplett anders?


- Wenn ich die Funktion "clear" aufrufe, will ich ja alle Elemente der Liste löschen, also die angelegten Referenzen.

Nun ist mir aber folgendes aufgefallen:

PHP-Code:

// Version 1:
//---------------------------------
var o1: Object = { x: 100 };

var link: LinkedList = new LinkedList();

link.push( o1 );

trace( delete o1 );

trace( link.first.x );    // undefined?


// Version 2:
//---------------------------------
var o1: Object = { x: 100 };

var link: LinkedList = new LinkedList( o1 );

trace( delete o1 );

trace( link.first.x );    // 100 ! 


Bei Version 1 kommt ein undefined heraus, aber warum ?
Eigentlich dürfte das Objekt nicht gelöscht werden da doch eine Referenz auf dieses in der Klasse "LinkedList" besteht.
Und bei beiden gibt delete jeweils true zurück (?), sollte das eigentlich nicht erst passieren wenn keine Referenz mehr auf diese Objekt existiert?
Und wie könnte man am besten prüfen ob meine Klasse auch wirklich die Objekte wieder freigibt so das der GC diese Objekte "zerstören" kann.



"IList":

- In diesem Interface würde ich gerne die Funktion "insert" so wie sie auskommentiert ist implementieren, da ja nicht jede Liste unbedingt ein einfügen innerhalb der Liste benötigt (z.B.: Stack, Queue, ...).

Wie könnte man dies noch "Ausmerzen"?
Oder ist es da besser noch ein Interface für die genannten Ausnahmen zu erstellen?


Und nun auch eine Frage die vielleicht schon eher in diesen Bereich passt...

- Könnte man die Klassen so lassen, oder würde sich da noch eine Unterteilung, ein besserer Aufbau, etc. anbieten?

- Wie sieht es mit einer Sortierung so einer "einfach" verketteten Liste aus?
Das dürfte doch sehr problematisch werden, da ja nur der Nachfolger bekannt ist.

Da müsste man schon merfach mit dem BubbleSort durchgehen, oder gibt es da was was sich für so etwas anbietet?

So, hoffentlich antwortet da noch einer bei der Masse an Input...

[[je]]

Nur zum schauen: http://je2050.de/stuff.php?p=/source/de/je2050/util/

Bin grade nur über die Überschrift gestolpert, aber schreibe gerne später etwas mehr dazu!

[[je]]

1.) Sortierung
Ein Link zur sortierten Liste von mir: SortedList
Der Trick ist: Beim Einfügen eines Elements in die Liste checkst du, ob es kleiner als der Start-Knoten ist, usw. Das geht man ganz einfach Rekursiv durch.

Eine extra sortier-Funktion ist auch nicht so schwer. Das habe ich in Pascal auch schon mal machen müssen glaube ich. Vielleicht finde ich die noch und könnte dir das am Mittwoch schicken.

2.) Clear Problem
Ich verstehe leider noch nicht ganz, wo der Unterschied zwischen deinen Beiden Versionen ist.

3.) IList und insert()
Ehrlichgesagt würde ich ein anderes Design wählen. Bei dir ist jedes List-Element die ganze Liste(?). Also einfacher ist es, wenn du ein Start-Knoten explizit hast, der von einem (List-)Element erbt und die Liste/Queue/Stack Funktionen bietet.

4.) Aufbau
Wie erwähnt. Ich würde eine Liste wie folgt aufbauen:
- Listen Element (Beinhaltet dynamischen Datentyp und Pointer)
- Datentyp (Funktionen wie toString, zum Vergleich etc.)
- Builder (Erbt vom standart Element und handhabt die Bewegungen inerhalb deiner Struktur, wie Liste/Stack/Queue)

Möchtest du z.B. eine einfache Liste haben, hast du deine simple List. Willst du eine sortierte Liste haben, musst du nur die insert-Funktion der List überschreiben und schon hast du eine sortierte Liste usw.

[rendner[i]]

Habe mir deine Sachen mal angeguckt, find ich schön Struckturiert (da ich immer zum "alles-in-einer-Klasse" programmieren neige).
Was mir besonders gefallen hat war die Sache mit dem Datentypen ("IData").

Ich verstehe leider noch nicht ganz, wo der Unterschied zwischen deinen Beiden Versionen ist.

Ich erstelle ja jeweils ein Objekt, was ich in Version1 per push der Liste zufüge und bei Version2 über den Konstruktor.
Die Funktion push und der Konstruktor tragen jeweils das übergebene Objekt in der art "pointer = new Linkable( object );" in die Liste.
Danach "lösche" ich das Objekt, in Version1 ist meine Referenz gelöscht, das Objekt ist weg, aber warum?

Und in Version2 habe ich Zugriff auf das Objekt, so wie es nach meiner Auffassung auch sein sollte.

Bei dir ist jedes List-Element die ganze Liste(?).

Oh ja, das habe ich gar nicht bedacht.
Das kommt daher das ich nur an Pointer gedacht habe .

Also einfacher ist es, wenn du ein Start-Knoten explizit hast, der von einem (List-)Element erbt und die Liste/Queue/Stack Funktionen bietet.

Kannst du das etwas genauer Erklären, ich verstehe nicht ganz was du damit sagen willst.

Gut das werd ich mal Sacken lassen und bei gegebener Freizeit mal umsetzen.

[[je]]

Also anfangen würde ich mit einer einfachen Liste.
Was bei jeder Liste von dir gleich sein wird ist das Listen-Element.

Grob ist ein Listenelement aufgebaut aus:
- Pointer auf nächstes Element
- Daten

Das kann man ja simpel in einer Klasse festhalten (genannt Element).

Schon kannst du deine einfache Liste bauen, die aus den einfachen Elementen besteht. Bei dir besitzt zur Zeit jedes Element alle Funktionen.

Ich würde jetzt anders vorgehen. Dazu schreibst du eine neue Klasse "List" z.B.
List erweitert Element, also "List extends Element" (ich will nicht kindisch wirken, aber so kann man leichter folgen glaube ich und weiß sofort was gemeint ist).

Deine List Klasse verfügt jetzt über die eigenschaften eines Elements. Was fehlt sind die Funktionen. Also z.B. eine Funktion zum einfügen.

Dazu schreibst du in die List die Funktion insert(), wie du es auch kennst. Schon hättest du eine Liste, bei der nur die Basis-Klasse über insert(), delete() usw. bescheid weiß. Das spart auch Resourcen, bei größeren Datenmengen z.B.

Als nächstes möchtest du vielleicht eine automatisch sortierte Liste schreiben. Die delete() oder exists() Funktionen kannst du noch von der anderen Liste übernehmen. Nur die insert() Funktion müsstest du jetzt überschreiben.

Also eine neue Klasse SortedList oder so anlegen, welche List erweitert. In dieser musst du nur die insert() Funktion überschreiben und du hast deine Sortierte Liste.

So kannst du immer weiter machen, mit Stack, Queue usw.
Stack würde ich z.B. von Element erben lassen und dann nur push() und pop() als Funktionen definieren. Mehr weiß der Stack-Typ ja eigentlich nicht.

Fals es dich interessiert, kannst du dir auch mal die Bäume anschauen.

[Janoscharlipp]

Also ich weiß nicht, was eine LinkedList ist, und wofür man sie braucht, aber deine Umsetzung scheint mir etwas wackelig.

Beispielsweise die push-Methode ist mir ungeheuer, solltest du beabsichtigen, beim ersten push-Aufruf sowohl in lstE als auch in fstE zu schreiben (es sind ja die gleichen Objekte), dann würde ich versuchen, das expliziter zu tun.

Warum sind eigentlich fstE und lstE keine Elemente? Und warum heißen sie nicht einfach fistElement und lastElement?

Wofür braucht man denn sowas? Erinnert mich irgendwie an die XML-Klasse.

[rendner[i]]

Beispielsweise die push-Methode ist mir ungeheuer, solltest du beabsichtigen, beim ersten push-Aufruf sowohl in lstE als auch in fstE zu schreiben (es sind ja die gleichen Objekte), dann würde ich versuchen, das expliziter zu tun.

Wow. Das ist der Fehler warum in meiner Version1 ( da Beispiel mit dem deleten) da undfined rauskommt, da ja das Element nicht in fstE gespeichert wird.

Warum sind eigentlich fstE und lstE keine Elemente?

Weil sie als Pointer dienen sollten.
Wenn man ein Objekt einem anderen Objekt zuweist, speichert man ja nur eine Referenz auf dieses.
Darum habe ich mir gedacht diese gleich als Objekt zu lassen, da fstE und lstE nicht die Methoden, Variablen der Klasse "Linkable" (Element) brauchen.

Und warum heißen sie nicht einfach fistElement und lastElement?

fstE steht fur firstElement, da mir die andere Screibweise zu lang war.

Wofür braucht man denn sowas? Erinnert mich irgendwie an die XML-Klasse.

Kann ich dir auch nicht genau sagen, da ich das nur aus lernzwecken umsetzen wollte.
Aber der Vorteil gegenüber einem Array ist (zumindest in C), das du nicht wieder das Array neu anlegen musst wenn du ein Element in ein volles Array zusätzlich einfügen willst.
Da du ja nur die Verweise auf den Nachfolger verändern musst.

[Janoscharlipp]

Zitat von rendner[i]

Weil sie als Pointer dienen sollten.
Wenn man ein Objekt einem anderen Objekt zuweist, speichert man ja nur eine Referenz auf dieses.
Darum habe ich mir gedacht diese gleich als Objekt zu lassen, da fstE und lstE nicht die Methoden, Variablen der Klasse "Linkable" (Element) brauchen.

Kann ich nachvollziehen, ist aber in dem Fall trotzdem nicht so ganz richtig, schließlich verwendest du die Eigenschaften next und o von fstE, welche also irgendwo definiert sein sollten.

Zitat von rendner[i]

Aber der Vorteil gegenüber einem Array ist (zumindest in C), das du nicht wieder das Array neu anlegen musst wenn du ein Element in ein volles Array zusätzlich einfügen willst.
Da du ja nur die Verweise auf den Nachfolger verändern musst.

Ah, ok, das stimmt natürlich. Dass du dafür dann für ein pop eine Schleife brauchst finde ich aber schade. Könnte man das nicht mit einer Pflege von lstE umgehen? (hmm, geht wohl nicht, ohne eine previous-Eigenschaft)

Sollte pop nicht das Element (eine Referenz darauf) zurück geben?

[rendner[i]]

Kann ich nachvollziehen, ist aber in dem Fall trotzdem nicht so ganz richtig, schließlich verwendest du die Eigenschaften next und o von fstE, welche also irgendwo definiert sein sollten.

Wieso?
Ich habe ja in fstE eine Referenz von dem Objekt gespeichert und somit kann ich ja auch dessen Methoden benutzen, dafür muss ich diese doch nicht auch selber besitzen.

Ah, ok, das stimmt natürlich. Dass du dafür dann für ein pop eine Schleife brauchst finde ich aber schade. Könnte man das nicht mit einer Pflege von lstE umgehen? (hmm, geht wohl nicht, ohne eine previous-Eigenschaft)

Dafür gibt es eine doppelt verkettete Liste, wo jedes Element auf einen Vorgänger und einen Nachfolger zeigt.
Somit kann man dann auch "normal" pop'en.

[Janoscharlipp]

Dass du weißt, dass du in fstE ein Objekt mit den Eigenschaften next und o speicherst, hilft dem Compiler herzlich wenig. Wenn du jetzt auf fstE.mext zugreifst wirst du keine Warnung bekommen …

[rendner[i]]

Ja ich verstehe schon was du meinst, aber auf next und o des Objektes greift nur die Liste selber zu.
Und wenn die Liste das erste oder letzte gespeicherte Objekt zurückgegeben soll, dann wird vorher geprüft ob die Liste leer ist.

Aber ich werds dann doch so machen das die Pointer fstE und lastE ebenfalls vom Element erben.

[rendner[i]]

So hab die Liste überarbeitet, hoffe das kommt schon eher einer verketteten Liste nahe.
Sehr grosse Probleme hatte ich beim "umdenken" wenn Elemente eingefügt oder gelöscht werden sollen, hatte gedacht man kann da einfach die Zeiger tauschen und gut is, aber das hat so nicht geklappt.

Dürfte so doch jetzt eigentlich gehen, oder?

Klasse ListElement:
(Das Interface IData, ist das von [je]. Link -->IData)

class ListElement
{
	
	private var data: IData;		
	private var next: ListElement;
	
	public function ListElement( data: IData )
	{
		this.data = data;
		next = null;
	}
	
	public function getNext(): ListElement
	{
		return next;
	}
	
	public function setNext( e: ListElement ): Void
	{
		next = e;
	}
	
	public function getData(): IData
	{
		return data;
	}
	
	public function setData( data: IData ): Void
	{
		this.data = data;
	}
	
	public function clone(): ListElement
	{
		var e: ListElement = new ListElement( data );
		
		e.setNext( next );
		
		return e;
	}
	
	public function copy( e: ListElement ): Void
	{
		setData( e.getData() );
		
		setNext( e.getNext() );
	}
	
	public function clear()
	{
		setData( null );
		
		setNext( null );
	}
}

Klasse LinkedList:

class LinkedList extends ListElement
{
	
	private var l: Number;		// length of the LinkedList
	
	public function LinkedList()
	{
		super( null );
		
		l = 0;
	}
	
	public function insert( d: IData ): Void
	{
		var e: ListElement = new ListElement( d );
		
		e.setNext( clone() );
			
		copy( e );
		
		l++;
	}
	
	public function remove(): Void
	{
		if( l )
		{
			copy( getNext() );
			
			l--;
		}
	}
	
	public function insertAt( index: Number , d: IData ): Boolean
	{
		if( index == 0 ) 
		{
			insert( d );
			
			return true;
		}
		
		if( l < index ) return false;
		
		var i: Number = 1;
		var e: ListElement = new ListElement( d );
		var p: ListElement = searchElement( index - 1 ); 
		
		e.setNext( p.getNext().clone() );
		
		p.getNext().copy( e );
		
		l++;
		
		return true;
	}
	
	public function removeAt( index: Number ): Boolean
	{
		if( index == 0 && l ) 
		{
			remove();
			
			return true;
		}
		
		if( l <= index ) return false;
		
		var p: ListElement = searchElement( index - 1 );
		
		if(  p.getNext().getNext() == null )
		{
			p.setNext( null );
		}
		else
		{
			var e: ListElement = new ListElement();
			
			e.copy( p.getNext() );
			
			p.getNext().copy( e.getNext().clone() );
			
			e.clear();
		}
		
		l--;
		
		return true;
	}
	
	public function get head(): IData
	{
		return getData();
	}
	
	public function getAt( index: Number ): IData
	{
		if( index == 0 ) return head;
		
		return searchElement( index ).getData();	
	}
	
	private function searchElement( index: Number ): ListElement
	{
		var p: ListElement = new ListElement( null );
		var i: Number = 0;
		
		p.copy( this );
	
		while( i++ < index ) 
		{
			p.copy( p.getNext() );
		}
	
		return p;
	}
	
	public function isEmpty(): Boolean
	{ 
		return l == 0 ? true : false;
	}
	
	public function get length(): Number
	{
		return l;
	}
	
	public function clear(): Void 
	{
		while( getNext() != null )
		{
			setNext( getNext().getNext() );
		}
		
		super.clear();
		
		l = 0;
	}
}

Wenn das so hinhaut, kann ich dann die sortierte Liste angehen.