verlinkte Liste mit generics

[Mark3108]

Hallo alle zusammen...

ich möchte eine einfach verlinkte Liste in Java basteln. Dabei soll das letzte element nicht mit null gekennzeichnet sein, sondern wieder auf das Erste zeigen. Einfach deshalb das ich ein element aus der Liste nehmen kann ohne die Liste kennen zu müssen.

Folgende Datenstrukturen hab ich jetzt angelegt:

ACHTUNG addToQueue() und getItem sind nur dummies zum testen...

public abstract class TObjectQueueItem<ObjectQueueItem extends TObjectQueueItem<?>> 
{
	protected ObjectQueueItem FObjectLink;

	public TObjectQueueItem()
	{
		FObjectLink = (ObjectQueueItem)this;
	}
	
	public void addToQueue(ObjectQueueItem aItem)
	{
		FObjectLink = aItem;
	}
	
	public ObjectQueueItem getItem()
	{
		return FObjectLink;
	}
}


public class TObjectQueue<ObjectQueueItem extends TObjectQueueItem<?>> extends TObjectQueueItem<ObjectQueueItem>
{
	public TObjectQueue()
	{
		super();
	}
}

ACHTUNG addToQueue() und getItem sind nur dummies zum testen...

TObjectQueueItem repräsentiert ein Element in der Liste. FObjLink ist der ptr auf das nächste Objekt. Dieser wird parametrisiert mit ObjectQueueItem welches zumindest von TObjectQueueItem erben muss... soweit so gut.

Erste Frage:

was bedeutet das <?> in der Zeile
"class TObjectQueueItem<ObjectQueueItem extends TObjectQueueItem<?>>"

Ich hab das nur hingemacht weil ich ansonsten ne warning bekomme da ich ObjectQueueItem nicht parametrisiert hab. Aber ich weiß ja an der Stelle noch nicht was <?> sein wird...


Zweite Frage:

Also TObjectQueue ist jetzt meine Liste und erbt von TObjectQueueItem. Dabei ist FObjLink der ptr auf das erste Element bzw auf die Liste selbst wenn sie leer ist. Und genau das ist das Problem. FObjLink ist ja parametrisiert und zeigt auf irgendein "höheres" Object. Wenn ich den jetzt auf die Liste selbst zeigen lassen will, gibt das ne Exception weil Java das implizit auf Typkompatibilität prüft.

Ich möchte aber TObjectQueue allgemein halten. Sprich da soll nur ein ptr aufs erste Object stehen und halt generische Methoden um was mit der Liste zu machen. Deshalb kann TObjectQueue nicht von "ObjectQueue" abgeleitet sein. Oder seh ich das falsch?

Liegt der Fehler jetzt in meinem Ansatz? Also denk ich falsch? Würde man das anders machen?
Gibt es in Java auch die Möglichkeit Objekte zu casten ohne das überprüft wird ob die kompatibel sind?

Hoffe ich konnte einigermaßen rüber bringen was ich machen will und wo das Problem liegt.

lg

 

[Marco13]

So halb...

Das <?> bedeutet nur, dass die Klasse "irgendeinen" Typ-Parameter hat, aber an dieser Stelle nicht bekannt ist, welcher das sein soll.

Das zweite... muss ich morgend ggf. mal testen, vielleicht wird (mir) dann klarer, was du meinst.

 

[Mark3108]

Ok ich versuche es nochmal zu verdeutlichen...

Bei einer klassischen verketteten Liste ist das letzte Element dadurch gekennzeichnet das der next ptr null ist. Die Liste selbst kann also aus einem simplen ptr auf das erste Objekt repräsentiert werden.

list--->objekt1--->objekt2--->objekt3--->null

Dabei kann list vom gleichen Typ wie objekt1 sein. Ist die liste leer dann ist list einfach null. list ist also keine Instanz sondern nur ein ptr auf ein Objekt.

Das ist simpel und funktioniert. Das Problem dabei: Ich muss die Liste, sprich den ptr auf das erste Objekt kennen um ein Objekt aus der Liste nehmen zu können. Wenn ich Objekte aus einer Liste nehmen können will, ohne die Liste zu kennen, brauch ich entweder eine doppelt verkettete Liste, sodass ich den Vorgänger kenne, oder ich mache es mit der einfach verketteten Liste und lasse den next ptr des letzten Objektes auf das erste Objekt zeigen. Dann kann ich mit "listItem.reclaim()" - Name gerade erfunden - das listItem aus der Liste entfernen ohne diese zu kennen. Ich muss nur einmal im Kreis laufen, bis ich ein Objekt habe dessen next ptr auf mein zu entfernendes Objekt zeigt. Alles von der Logik kein Problem.

Das führt nur dazu dass ich die Liste nicht mehr simpel durch einen ptr auf das erste Objekt repräsentieren kann, da eine leere liste auf sich selbst zeigen muss.

--->list.next---
| | leere Liste
---------------

--->list.next--->Objekt1--->Objekt2--->Objekt3---
| | liste mit drei Objekten
--------------------------------------------------

In diesem Fall ist list, im Gegensatz zum letzten Beispiel, schon eine Instanz deren next ptr erst auf das erste Objekt zeigt.
Ich brauche also ein Objekt mehr um eine Liste mit gleicher Anzahl von Elementen darzustellen. Wenn das schon so ist, dann sage ich eben es gibt zu den Typen ListItem eben noch einen Typ List. Das ist ja nicht so doof.
Wie sieht dieser Typ rein von der Datenstruktur aus?
Also für mich hat er erstmal nur einen first/next ptr. Also wie jedes ListItem auch. Also leite ich list, sinnvollerweise von listItem ab. Das Problem ist jetzt das die nextPtr ja parametrisiert werden. Die next ptr sind also von einem Typen der zwar von ListItem erbt aber dieses auch erweitert. Wenn ich jetzt den next ptr von Objekt3 auf list zeigen lassen will, stimmen die Typen nicht überein, da list vom Typ TList extends TListItem ist und der next ptr von Objekt3 vom Typ TExtendedListItem extends ListItem ist. Das gibt dann bei java eben ne Exception.

Abhilfe?
Naja man könnte List von dem konkreten Typ der ListItems erben lassen. Finde ich aber total doof, da dann die Liste Felder hat die sie nicht brauch, und was viel schlimmer ist, ich kann das nicht generisch implementieren. Ich will ja einen Typ List habe von dem nur bekannt ist das er einen next/first ptr hat der auf das erste Objekt zeigt. Vielleicht noch ein paar Methoden die man allgemein für so eine Liste vereinbaren kann.
Ich frage mich jetzt ob das ein Fehler in meiner Denkweise ist und man sowas einfach anders implementieren würde.

 

[Marco13]

:bahnhof: Ich versteh's nicht - ich kann nicht filtern, was von dem, was du geschrieben hast, nur allgemeines Gelaber ist, und was tatsächlich mit dem Problem zu tun hat, und was vermeintliche Lösungsansätze sind (evtl. um Probleme zu lösen, die gar nicht existieren). Vielleicht versteht's irgendjemand anderes, oder du versuchst mal, das so zu schreiben, als wüßtest du selbst nicht, worum es da geht...

 

[Andi_CH]

Ok ich versuche es nochmal zu verdeutlichen...

Bei einer klassischen verketteten Liste ist das letzte Element dadurch gekennzeichnet das der next ptr null ist. Die Liste selbst kann also aus einem simplen ptr auf das erste Objekt repräsentiert werden.

list--->objekt1--->objekt2--->objekt3--->null

NIEMAND behauptet, dass der letzte pointer nicht wieder auf das erste Element zeigen darf
Die Objekte müssen einfach eine gemeinsame Vaterklasse haben, die next und previous enthält

Die leere Liste ist dann, wenn list == null ist

Das erste Element ist referenziert durch list
Das letzte Element durch list.previous

Also wo ist das Problem? (Aber bitte schreib nicht wieder eine halbe Dissertation - wir möchten nicht 100 Zeilen filtern bis wir irgendwo eine Problembeschreibung finden)

Das ganze nennt sich Ringbuffer:

google treffer 1

google treffer 2

 

[Marco13]

Irgendwie klang das mit dem Zeiger auf's erste Element nach einem Versuch, sowas wie
einElement.löscheDichAusDerListeInDerDuBistOhneDassIchDieInstanzDieserListeKenne();
anbieten zu können?

 

[Mark3108]

@Marco13

ja genau "einElement.löscheDichAusDerListeInDerDuBistOhneDassIchDieInstanzDieserListeKenne();" triffts genau.

@Andi_CH

Diese Ringpuffer Lösungen funktionieren anders. Da ist es so wie ich das sehe auch nicht möglich Elemente aus der Liste zu löschen ohne diese zu kennen.

Das letze Element zeigt aufs erste war falsch ausgedrückt merke ich eben. Das letzte Element zeigt in meinem Ansatz auf die Liste selbst. Was ich also bräuchte wäre ein cast von TExtendedListItem extends TListItem nach TList extends TListItem. Die zwei Typen sind nicht kompatibel. Deshalb gibts ne Exception wenn ich dem next des letzten objekts die liste zuweisen will.

Frage mich jetzt ob mein Ansatz einfach falsch ist und man sowas anders machen würde.

 

[Mark3108]

Habs jetzt hinbekommen. Parametrisier das ganze jetzt anders und dann gehts. Dachte ich kann mir diese "unnötigen" cast überall sparen. Das klappt wohl nicht. Hab jetzt noch einen drin aber gut.

Danke für eure Hilfe