doppelt verkette Liste

[loxa789]

Hallo:
So ich soll eine DList so verändern (DList ist gegeben) dass:

 Jeder Knoten sowohl einen Schüssel als auch einen Wert beinhaltet.
 Nach einen Wert über einen Schlüssel gesucht werden kann.
 Ein Schüssel mit seinem Wert bei Zugriff an den Anfang der Liste wandert.

Was meint unser Prof. mit Schlüssel?
Ist der Schlüssel der Wert der in den Knoten geschrieben wird?

kann mir einer von euch bitte erklären was ich in etwa machen soll. Bräuchte eine Anleitung (Kochbuch).
programmieren will ich mit etwas hilfe von euch aber selber.
danke loxa789

 

[Gelöschtes Mitglied 5909]

Ich denke er will ne wart HashMap ohne Hash mechanismus.

Dafür gibst du deinen knoten noch einen key zusätzlich
und 2 methoden (bzw du änderst die alten 2 ab)

Pseudomäßig etwa so

private static class Node<K, V> {

	public Node(K key, V val) { ... }
	K key;
	V val;
	Node<K,V> next;
	Node<K,V> prev;
}

put (k key, V val) {
	Node<K,V> node = new Node<K,V>(key, val);
	Node<K,V> last = getLast();
	node.next = null;
	node.prev = last;
	last.next = node;   // node ist jetzt last
}

get(K key) {
	// über liste iterieren
	// und schlüssel vergleichen

	Node<K,V> hit = iter.next();	// treffer
	// next, prev umbiegen
	Node<K, V> first = getFirst();
	hit.next = first;
	hit.prev = null;
	first.prev = hit;	// hit ist jetzt first
}

Sinn dabei ist dass wenn der gleiche key mehrmals angefragt ist er ganz vorne bze weiter vorne ist und nicht am ende.
Dadurch muss nicht so oft iteriert werden und der hit kommt schneller.

=> die liste sortiert sich praktisch selbst nach anzahl der "zugriffe" mit den keys

 

[loxa789]

Hallo!
Leider versteh ichs noch nicht ganz habe drei Klassen DNode DList und meine Testklasse.
Könnt ihr mit Bitte in Grundzügen erklären wie eine DList funktioniert. So wie ich die Dlist versteh braucht jeder Knoten eine Zuweisung zum vorigen und nächsten Knoten. Wie schreibe ich dass ein Knoten mit den String "Hans" auf den ersten und dritten Knoten verweist.
Wenn ich einen neuen Knoten am Anfang er Liste einsetzen will schreibe ich dann dl.pushHead(); aber was schreib ich in die Klammern.
Wie setzte ich Knoten an der xsten Stelle bzw. wie rufe ich sie auf. Geht das einfügen mit dl.insertAt(xsten,"Franz",xsten+1) kann ich auch mit dem Befehl setAt() arbeiten was mach ich mir dem wieso brauch ich in wenn ich insertAt habe.
Muss ich die Anzahl der Knoten wie ein Array[] vorher definieren und fängt die Liste auch bei 0 an.Fragen über Fraben. Leider sind meine Skripten zu diesem Thema sehr dürftig, bzw unversändlich für mich,daher muss ich euch Bitten mir dies zu erklären.
Danke

 

[jeansmander]

Hallo schreibe das erste mal hier ins Forum. Habe auch mit den Listen so meine Probleme. Könnte jemand die Fragen von Loxa789 beantworten würde mich auch interessieren. Danke Jeans

 

[SlaterB]

> Könnt ihr mit Bitte in Grundzügen erklären wie eine DList funktioniert.

was eine DList ist weiß niemand, ist wohl kein Fachbegriff in dieser Welt,
oder gehts allgemein um 'doppelt verkettete Listen'?
das gibts ja nun überall nachzulesen, wozu das kopieren?
in einem Satz: einzelne Knoten, die sich gegenseitig referenzieren/ verlinken

> schreibe ich dann dl.pushHead(); aber was schreib ich in die Klammern

von pushHead() hat auch keiner eine Ahnung

> Wie schreibe ich dass ein Knoten mit den String "Hans" auf den ersten und dritten Knoten verweist.

zweier.prev = einser
zweier.next = dreier
+ von einser und dreier aus korrekt auf den neuen zweier verweisen

> Wie setzte ich Knoten an der xsten Stelle bzw. wie rufe ich sie auf.

einfügen so wie der zweier eingefügt wurde,
abfragen indem man die Liste durchläuft und die Position mitzählt

> insertAt()/ setAt()

den Unterschied zwischen diesen beiden Operationen kennt wieder niemand,
ganz grob geschätzt setzt setAt() nur den Wert an Stelle x neu, die Liste bleibt gleich lang, ein alter Wert geht verloren,
insertAt() fügt einen neuen Knoten mit Wert ein

> Muss ich die Anzahl der Knoten wie ein Array[] vorher definieren

nein

> und fängt die Liste auch bei 0 an

es gibt in dem Sinne überhaupt keine Indexe wie bei einem Array aber natürlich ein erstes zweites Element usw. wenn man sie in Reihenfolge nummeriert
(und sei es nur gedanklich)

 

[Pappenheimer++]

Loxa, du stellst hier Fragen zu einem dir gegebenen Code, den hier noch nie jemand gesehen hat. Woher sollen wir wissen, was in den Methoden, von denen du da redest, drin steht?^^ Prinzipiell funktioniert doch eine LinkedList ganz einfach: In einem DList-Objekt hast du eine Referenz auf den ersten Knoten und eine auf den letzten. Die einzelnen Knoten haben jeweils immer eine Referenz au den direkten Vorgänger und den direkten Nachfolger. Bei den ganzen Such-Lösch oder Einfügoperationen hangelst du dich einfach an den Knoten entlang und biegst Referenzen ggf. um. Der Schlüssel ist einfach ein zusätzliches Attribut eines Knotens, der nur zur Identifikation der Nutzdaten dient, aber das hat mein Vorposter ja schon gezeigt