doppelt verkettete Listen?

[mobile]

Hi Leute,

sitze hier grad an meinen Übungsaufgaben. Dachte eigentlich ich habe sie verstanden, aber irgendwie geht grad gar nichts. Muss folgendes erreichen:

Ich soll einen ADT Interface mit doppelt verketteten Listen erstellen. Mit einfach verketteten habe ich. Versteh noch nich so ganz wie das mit den Zeigern funktioniert.

Also ein Listen Element (auch eine Liste, logisch) soll folgendermaßen aussehen:
Ein Verweis auf den Vorgänger - Inhalt des Elements - Verweis auf den Nachfolger

Der Konstruktor der Klasse Liste sieht bei mir jetzt so aus:

//....

//Datenfeld zugriff durch Methoden
	private Element item;
	
	//Zeigerfeld
	private List vor;
	private List next;
	
	/**
	 * Konstruktor
	 * erzeugt leere Liste
	 * */
	public List() {
		vor = null;
		item = null;
		next = null;
	}
//...

Stimmt das soweit mit der Beschreibung oben über ein? Dann soll ich noch ein Verweis auf das erste und Letzten setzen.

Ich weiß irgendwie nich, wie ich die Zeiger dann dann richtig auf Vorgänger und Nachfolger setze. Methoden insert und append sehen so aus, müssen dann natürlich irgendwie angepasst werden.

//...
/**Fügt x am Kopf ein, also am Anfang*/
	public List insert(Element x) {
		List l = new List();
		l.item = x;
		l.next = next;
		next = l;
		return this;
	}
	
	/**Hängt x ans Ende*/
	public List append(Element x) {
		if(isEmpty()) {
			return insert(x);
		}
		else {
			return next.append(x);
		}
	}
//...

Kann mir vielleicht jemand kurz die beien Methoden erläutern besonderns append.

So das reicht glaube ich erst mal. Hoffe ihr könnt mir helfen! Ich weiß, dass Listen in Java schon fertig sind, aber wir sollen es selber programmieren!

 

[Guest]

So ungefähr kann deine doppelt verkettete Liste aussehen.

public class DoubleLinkedList<T> implements List<T>
{
   private ListItem<T> root;
   private int size;

   ...

   private class ListItem<T>
   {
      public ListItem<T> previous;
      public ListItem<T> next;
      public T value;
   }
}

Den Rest kannst du dir selbst überlegen.

 

[Gast]

Ja, aber das Problem liegt denk ich daran dass er probleme hat bei der insert methode. Er weiss nicht wie er Zeiger auf das vorherige element setzen kann dort. Leider kann ich dir auch nicht helfen dabei da ich das gleiche problem habe.

public List insert(Element x) {
List l = new List();
l.item = x;
l.next = next;
l.prev = this;
next = l;
return this;
}


Das funktioniert schonmal nicht, der prev zeiger ist immer null. wenn einer Rat weiss bitte helfen.

 

[Guest]

Das funktioniert schonmal nicht, der prev zeiger ist immer null. wenn einer Rat weiss bitte helfen.

Denke an eine Menschenkette. Jeder hält mit einer Hand seinen Vorgänger und mit der anderen den Nachfolger.
Ist nur einer da bzw. erst einer da, kann er die Hände zusammenlegen und sich zum Vorgänger und Nachfolger
von sich selbst erklären.

 

[Guest]

Übrigens, eine geschlossene Menschenkette, da es eine doppelt verkettete Liste ist.

 

[Gast]

Hallo,
Es mach wenig sinn das alles in die Liste.class reinzupacken, du solltest lieber eine zusätzliche Klasse namesn Knoten verwenden die den Inhalt der Elemente und den Vorgänger/Nachfolger enthalten.