Doppelte Verkettung

[stiffy]

Hi,

ich soll einen FIFO-Puffer mit doppelter Verkettung erstellen. Leider bin ich in Java nicht wirklich bewandert, ich habe mal ein Programm zusammengestellt, dessen put und get Methoden auch funktionieren, leider bin ich mir nicht ganz sicher ob das alles richtig funktioniert wie ich mir das vorstelle. Hier mal der source:

public class FIFOBuffer implements Buffer{
	
	Node first, last;
	
	class Node {
		Object data;
		Node pre;
		Node post;
		
		Node (Object x, Node n, Node m) {
			data = x;
			pre = n;
			post = m;

		}	
	}

	public FIFOBuffer () {
		first = null;
		last = null;
	}
	
	public boolean isEmpty (){
		return (first == null && last == null);
	}
	
	public boolean isFull (){
		return(false);
	}
	
	public void put (Object x){
		if(first == null){
			first = last = new Node(x, null, last);
		}
		else{
			last.pre = last;
			last = last.post = new Node(x, last.pre, last);
		}
	}
	
	public Object get (){
		Object x = first.data;
		first = first.post;
		return(x);
	}
	
	public Object getLast (){
		Object x = last.data;
		return (x);
	}
	
	public Object getAndDelete (int y){

	}
	
	public Object getPosition (int y){
	
	}
	
	public void putToPosition (Object x, int y){
	
	}
	
	public int countObjects (){
	
	}
		
}

Nun folgende Fragen: Funktioniert das so als doppelte Verkettung, also jeder Knoten kennt seinen Vorgänger bzw Nachfolger? Und wie kann ich bei den 4 noch nicht programmierten Methoden auf Knoten mitten in der Verkettung (also nicht den letzten bzw ersten) zugreifen?

thx

 

[Matze]

Ich weiß zwar nicht was ein FIFO-Puffer ist, aber wegen deinem Code:
1. In der Regel heisßen sie in Java nicht put() Mehtoden, sonder set() (Ist aber deine Sache)
2. Lass den Code doch mal laufen, wenn er funktioniert, hast du deine Bitte selbst erfüllt. Ansonsten kannst du ja nochmal nachfragen wo der Fehler liegt

 

[Navy]

> last.pre = last;
>last = last.post = new Node(x, last.pre, last);

dürfte nicht funktionieren. Du setzt den Vorgänger des letzten Nodes auf sich selber (also den letzten Node), aber den darfst Du nicht ändern. Dann erstellst Du jedesmal wieder einen letzten Node, Deine Referenzierung des vorletzten Nodes bleibt auf den richtigen, Du erstellst aber keine neue des "neuen" vorletzten Nodes auf den letzten.

Ich versuchs mal zu visualisieren.

So sollte Deine Liste initial aussehen:
null

Dann das erste Eingefügt:

null <-- X --> null

Beim nächsten klappt das nicht mehr

Es sollte so aussehen:

null <-- X <---> Y --> null

sieht aber so aus

X <-- X --> null
nichtgesetzt(null) <-- Y --> Y

Du hast also 2 nichtaufeinander referenzierte Objekte. Erstell Dir *erst* ein Hilfsobjekt, änder die Referenzen entsprechend und dann setz "last" auf den letzten Node.

> Ich weiß zwar nicht was ein FIFO-Puffer ist, aber wegen deinem Code:

First-In-First-Out
> 1. In der Regel heisßen sie in Java nicht put() Mehtoden, sonder set() (Ist aber deine
> Sache)

Das ist hier nicht angebracht, da es sich um eine doppelt verkettet Liste handelt, die eine Queue werden soll.

PS: Du behinderst Dich selber in Deiner Programmierung mit Deinem seltsamen Stil.
1. So setzt Du z.B. den ersten node mit "first = last = new Node(x, null, last);", warum einmal "null" und einmal "last"?
2. Wenn first null ist, dann ist auch last null, demnach brauchst Du auch nur auf einen von beiden prüfen.
3. Außer aus Performancegründen: Wozu brauchst Du "last"?

 

[zeja]

Andere Frage: Warum sollte man FIFO als doppelt verkettete Liste implementieren? Was macht das für einen Sinn?

 

[Navy]

> Andere Frage: Warum sollte man FIFO als doppelt verkettete Liste implementieren? Was
> macht das für einen Sinn?

Für spätere Erweiterungen kann das durchaus Sinnvoll sein, ebenso für Lernzwecke. Da eine Implementation einer FIFO-Queue nur abstrakt beschrieben ist, muß sie nur nach den Vorgaben funktionieren -- das *wie* ist egal. Du könntest eine Queue ebenso über einen mailaccount aufbauen, wenngleich das auch niemand machen würde.

Natürlich ist sie dann nicht mehr minimal aber das verlangt ja auch keiner