Doppelt verkettete Listen
Die Klasse DLinkedList modelliere doppelt verkettete Listen mit separaten Verwaltungsknoten für head und tail, wie in den Videos vorgestellt. Die Nutzdaten sind ausschließlich int-Werte. Implementieren Sie:
- addLast(): fügt einen neuen Wert ans Ende der Liste an.
- zip(): mischt zwei Listen reißverschlussartig ineinander. Lautet l1=[1,3,5] und l2=[2,4,6], soll nach Ausführung von l1.zip(l2) gelten: l1=[1,2,3,4,5,6]. Erzeugen Sie keine Kopien der Knoten. Die zweite Liste darf dementsprechend zerstört werden. Sollte l2 kürzer als l1 sein, fügen Sie soviele Elemente ein wie möglich, und die restlichen Elemente von l1 bleiben erhalten. Sollte l2 länger als l1 sein, hängen Sie die überschüssigen Elemente hinten an l1 an.
- selectionSort(): führt eine aufsteigende Sortierung durch. Die Methode soll eine neue Liste zurückgeben. Durchlaufen Sie in jedem Durchlauf die Liste this, finden Sie den Knoten mit kleinstem Wert, fügen Sie eine Kopie des Knotens in die Ergebnisliste ein, und löschen Sie den Knoten aus der alten Liste. Dementsprechend ist die alte Liste am Ende der Sortierung leer.
package de.hsrm.ads;
public class DLinkedList {
class Node {
Node next;
Node prev;
int obj;
}
Node head, tail;
public DLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public void addLast(int t) {
// FIXME
}
public void zip(DLinkedList other) {
// FIXME
}
public DLinkedList selectionSort() {
// FIXME
}
}
Subato
