Erste Schritte Doppelt verkettete Liste

[Varthor]

Hallo zusammen,

derzeitig beschäftige ich mich mit Doppelt verketteten Listen (DvL) und hänge schon direkt am Anfang. Da ich noch ein Neuling bin, was Java Programmierung angeht, fehlt mir wahrscheinlich der Überblick oder der richtige Gedankengang, daher hoffe ich das Ihr mir auf die Sprünge helfen könnt.

Meine Liste besitzt drei Klassen (ValueElement, ListElement, List), welche wiederum jeweils ein dazugehöriges Interface (IValueElement, IListElement, Ilist) implementieren.

Zu meiner Frage:
Ich habe ein Verständnisproblem damit wie die Klassen ValueElement und ListElement zusammen funktionieren / interagieren.

Im Interface IValueElement steht:

public interface IValueElement
{
public String getName();
public void setName(String paramName);
public int getValue();
public void setValue(int paramValue);
}

In der Klasse ValueElement steht:

public class ValueElement
{
private String paramName;
private int paramValue;

// Es soll einen Konstruktor mit zwei Parametern geben, jeweils einen für den Namen und den Zahlenwert

public ValueElement(String paramName, int paramValue);

// ...  aufgeschlüsselt die im Interface genannten Methoden....

}

Im Interface IListElement steht:

public interface IlistElement
{
public IValueElement getValueElement();
public void setValueElement(IValueElement value);
public IlistElement get Predecessor();
public void setPredecessor(IlistElement predecessor);
public IlistElement getSuccessor();
public void setSuccessor(IlistElement successor);
}

Bei der der Klasse ListElement setzen meine Fragen ein (siehe Kommentare).
Das grundlegende System der Listen habe ich verstanden, die Umsetzung in Java bereitet mir aber
die Verständnisprobleme.

public class ListElement
{

/** Zitat: IListElement spezifiziert eine einzelne Position der Liste, die jeweils auf ihren Vorgänger und auf ihren Nachfolger zeit sowie einen Wert (Objekt vom Typ IvalueElement) aufnehmen kann **/

	private IValueElement value;
	private ListElement predecessor, successor, element;

/** Es soll einen Konstruktor geben der den initialen Wert 
des Elementes darstellt. 

Frage:
Wenn ich nun aber ein Objekt 
vom Typ "ListElement" erzeuge müsste ich an dieser Stelle doch auch die Position / Namen
des Elementes mitgeben? Welche Informationen trägt das Objekt ListElement mit der geforderten Umsetzung?

Nach meinem Verständnis erzeuge ich ein Objekt ListElement aus einem Objekt ValueElement, welches 2 Parameter beinhaltet,
ich übergebe an dieser Stelle aber nur einen?

Über die Methoden setSuccessor / setPredecessor gebe ich auch nur "Werte" und keine Positionen vor, wobei zweiteres mir sinnvoller erscheint?

**/

	public ListElement(IValueElement value)
	{
		element = value;
	}

// IValueElement

	public IValueElement getValueElement()
	{
		return element;
	}

	public void setValueElement(IValueElement value)
	{
		element = value;
		predecessor = null;
	}

// Successor

	public void setSuccessor(IListElement successor)
	{
		this.successor = successor;
	}

	public IListElement getSuccessor()
	{
		return this.successor;
	}

// Predecessor

	public void setPredecessor(IListElement predecessor)
	{
		this.predecessor = predecessor;
	}

	public IListElement getPredecessor()
	{
		return this.predecessor;
	}

}

Zur Ergänzung: Im Interface IList steht:

public interface IList
{
public IListElement getHead();
public void insertAtTheEnd(IValueElement value);
public void insertAtPos(int pos, IValueElement value);
public IValueElement getElementAt(int position);
public int getFirstPisOf(IValueElement value);
public void deleteFIrstOf(IValueElement value);
public void deleteAllOf(IValueElement value);
public boolean member(IValueElement value);
public void reverse();
public String toString();
}

Wenn ihr mir weiterhelfen könntet wäre ich super glücklich =)

 

[eMmiE]

Ich nehme an, deine Liste besteht aus ganz vielen ListElements.
Das erste ListElement mit dem Wert value1 verfügt über einen Nachfolger, aber keinen Vorgänger.
Dieses List Element nennst du einfach "begin".
Der Nachfolger mit dem Wert value2 hat den Vorgänger (-> "begin") als Referenz enthalten und kann einen Nachfolger haben. Wenn ein nachfolgendes Element deiner Kette aber keinen Nachfolger hat, dann nennst du es einfach "end"

Du durchläufst die Liste einfach mit einer Schleife

Pseudo Code:
var listelement = root;
solange listelement.nachfolger nicht null:
listelement = listelement.nachfolger;
macheirgendwasmitdendaten(listelement);

Wenn du jetzt als Vorgänger von "begin" "end" nimmst und als nachfolger von "end" "begin", dann hast du eine ringförmige struktur ohne ende

Einfach nochmal nachfragen, wenn du was anderes wissen wolltest

Gruß eMmiE

 

[Varthor]

Hey eMmiE,

deine Erklärung hilft definitiv bei dem verstehen wie eine doppelt verkettete Liste aufgebaut ist, vielen Dank dafür =)

Mir ist leider noch nicht so ganz klar was passiert wenn ich ein Objekt ListElement erzeuge.



Beispiel.:
ValueElement setzt sich aus einen

String paramName

und einem

int paramWert

zusammen.

Wenn ich also ein Objekt des Types ValueElement erzeuge gilt:

IValueElement Element00 = new ValueElement("PO1", 0);
IValueElement Element01 = new ValueElement("PO2", 5);

Durch diesen Schritt erzeuge ich die einzelnen Datensätze (Objekte).
Um diese zu Ordnen benötige ich meine Klasse ListElement (später natürlich auch die Klasse List).


Zitat aus der Aufgabe zu ListElement: "Es gibt einen Konstruktor mit einem Parameter. Der Parameter ist vom Typ IValueElement und stellt den initialen Wert des Elementes dar"

Der Konstruktor ListElement sieht einen Parameter des Types Objekt ValueElement vor...soweit so gut.

Nach meinem Verständnis beziehe ich mich dadurch auf die bereits existierenden Objekte Element00 oder Element01 um einen Vorgänger oder Nachfolger zu setzen --> Element01.setSuccessor(Element00)


Aber wo / wie definiere ich über ListElement den Initialwert? Wie sieht der ListElement Konstruktor aus?


Beispiel:
Würde der Aufruf ListElement(Element02) mir einfach ein "leeres" ValueElement Objekt Element02 erzeugen, welches ich später mit dem setter noch "füllen" muss? Ich denke nein, sonst wäre nicht die rede von einem dem initialwert.


Ich hoffe das macht mein Verständnisproblem etwas klarer

 

[eMmiE]

Nein,

der Konstuktor sieht meiner Meinung nach so aus

public ListElement (IValueElement e) {
this.value = e;
}

Das heißt, dass du ein schon bestehendes IValueElement-Objekt brauchst, um den Konstruktor aufzurufen
Es kann allerdings auch sein, dass du einfach sagst

IValueElement value = null;

und das dann in den Konstruktor einsetzt.
Das solltest du aber im Konstruktor imo ausschließen, weil das bei einer verketteten Liste keinen Sinn macht. (-> if-Abfrage)

Damit hast du dann allerdings nur ein ListElement, was du dann in eine beliebige verkettete Liste mit dem referenzieren von anderen ListElementen erledigen kannst

Gruß eMmiE

 

[Varthor]

Besten Dank, das macht die Sache klarer und ich habe es m.E. verstanden. Jedefalls ist nicht mehr der große Knoten im Hirn da =)