package doublelist;
import java.lang.Comparable.*;
import java.util.Comparator.*;
class DoubleList {
private ListElem m_Head; // Anfang der Liste
private ListElem m_Tail; // Ende der Liste
private boolean m_isQueue;
// Der Listen-Konstruktor ...
public DoubleList(boolean isQueue) {
m_Head = null; // ... erwartet kein Argument.
m_Tail = null;
m_isQueue = isQueue;
if (! m_isQueue)
System.out.println("Hallo, ich bin ein Stack! :-)");
if (m_isQueue)
System.out.println("Hi! Ich bin die Queue! ;-)");
}
// Durchlauf und Ausgabe aller Elemente
public void print() {
/* Die Liste wird so lange durchlaufen, bis das letzte Element erfasst
* und ausgegeben wurde - eben so lange, so lange elem != NULL ist. */
if (m_isQueue) {
for (ListElem elem = m_Tail; elem != null; elem = elem.getPrev())
System.out.print(elem.getElement() + "; ");
}
else {
for (ListElem elem = m_Head; elem != null; elem = elem.getNext())
System.out.print(elem.getElement() + "; ");
}
System.out.println();
}
// Fügt ein Element in die Liste ein
public void addElement(Object obj) {
/* Das 1. Element ist das kürzlich eingefügte Element. Ein Nachfolger-
* Element existiert nicht, folglich ist es sein eigener Nachfolger.*/
m_Head = new ListElem(obj, m_Head, null);
// Falls die Liste eine Queue ist ...
if (m_isQueue) {
// ... und die Liste noch leer ist ...
if (m_Tail == null)
// ... lege das letzte Element fest.
m_Tail = m_Head;
}
}
// Findet ein Element
public ListElem findElement(Object obj) {
// Durchläuft die Liste so lange, bis ...
for (ListElem tmp = m_Head; tmp != null; tmp = tmp.getNext()) {
// ... ein Element gefunden wurde, was der Suchanfrage entspricht.
if (tmp.getElement().equals(obj)) {
// Liefere gefundenes element zurück.
return tmp;
}
}
// Ansonsten gebe null zurück (nichts gefunden).
return null;
}
void deleteElem(ListElem pElem2Delete) {
// Soll überhaupt ein Element gelöscht werden?
if (pElem2Delete != null) {
// Soll das Start-Element gelöscht werden?
if (m_Head == pElem2Delete) {
// Setze das nächste Element als Start-Element
m_Head = pElem2Delete.getNext();
}
// Wenn es einen Vorgänger gibt, ...
if (pElem2Delete.getPrev() != null) {
// ... häng dessen Nachfolger um.
pElem2Delete.getPrev().setNext(pElem2Delete.getNext());
}
// Wenn es einen Nachfolger gibt, ..
if (pElem2Delete.getNext() != null) {
// ... häng dessen Vorgänger um.
pElem2Delete.getNext().setPrev(pElem2Delete.getPrev());
}
}
}
// Selection Sort
void selectionSort() {
// Durchlaufe die gesamte Liste bis zum Ende
for (ListElem i1 = m_Head; i1 != null; i1 = i1.getNext()) {
// Merke dabei die Position des jeweils kleinsten Elements
ListElem min = i1;
// Durchlaufe die Liste bis zu Ende, jeweils ab i1 + 1 und ...
for (ListElem i2 = i1.getNext(); i2 != null; i2.getNext()) {
// prüfe auf den kleinsten Wert.
i2.getElement().compareTo(min.getElement());
if ( < 0) {
// Merke klensten Wert
min = i2;
}
}
// Vertausche Elemente
swap(min, i1);
}
}
// Vertausche Elemente
static void swap(ListElem iPos1, ListElem iPos2) {
ListElem tmp = iPos1;
iPos1 = iPos2;
iPos2 = tmp;
}
// implementiert ein Listen-Element
class ListElem {
// Ein Listen-Element merkt sich ...
private ListElem m_Next; // ... den Verweis auf das nächste Element, ...
private ListElem m_Prev; // ... den Verweis auf das vorherige Element...
private Object m_Elem; // ... und das Element.
// Der Konstruktor des Listen-Elements erwartet ...
public ListElem(Object obj, ListElem next, ListElem prev) {
m_Next = next; // ... den Verweis auf das nächste Element ...
m_Prev = prev; // ... den Verweis auf das vorherige Element...
m_Elem = obj; // ... und das zu speichernde Element.
// Wenn es ein nächstes Element gibt, dann ...
if (m_Next != null)
// ... bin ich der Vorgänger von meinem vorherigen Element.
m_Next.setPrev(this);
// Wenn es ein vorheriges Element gibt, dann ...
if (m_Prev != null)
// ... bin ich der Nachfolger von meinem vorherigen Element.
m_Prev.setNext(this);
}
// Liefert ein Element aus der Liste
public Object getElement() {
return m_Elem;
}
// Liefert den Verweis auf das nächste Element
public ListElem getNext() {
return m_Next;
}
// Liefert den Verweis auf das vorherige Element
public ListElem getPrev() {
return m_Prev;
}
public void setNext(ListElem next) {
this.m_Next = next;
}
public void setPrev(ListElem prev) {
this.m_Prev = prev;
}
}
}
public class Main {
public static void main(String[] args) {
// Erstelle eine Liste
DoubleList dl = new DoubleList(false);
// Fülle Liste mit 20 Zahlen
for (int i = 0; i < 20; ++i)
dl.addElement((int)Math.round(Math.random() * 20));
// Gebe Liste aus
dl.print();
dl.selectionSort();
// dl.deleteElem(dl.findElement(8));
// dl.print();
}
}
Was mache ich nur falsch?
