Doppelt Verkettete Zirkular-Liste

D

DanielaLima

Mitglied
Hi zusammen,

könnte mir jemand diesen Konstruktor erläutern?

public SortedListGen() {
DListNode<E> dummy = new DListNode<E>();
dummy.next = dummy;
dummy.prev = dummy;
head = dummy;
current = dummy;
}

vor allem die Methode : private E delete().... funktioniert in meinen Augen nicht, weil ja durrent immer auf ein dummy zeigt, und damit erst gar
nicht ausgeführt werden kann?
Ich kann nicht ganz nachvollziehen, welchen Zweck die dummys haben? und warum head und current auf diese zeigen.

danke!

hier vorsorglich mal der gesamte Code der classe bis auf die Interfaces und die exceptionsklasse...
Code:
public class SortedListGen<E extends Comparable<? super E>> implements
        DynamicSetGen<E> {

    DListNode<E> head;
    DListNode<E> current;

   /**
     * Erzeugt eine doppelt-verkettete Zirkularliste mit einem Dummy-Knoten, der
     * auf sich selber zeigt.
     */
    public SortedListGen() {
        DListNode<E> dummy = new DListNode<E>();
        dummy.next = dummy;
        dummy.prev = dummy;
        head = dummy;
        current = dummy;
    }

    /**
     * Liefert zurueck, ob die Liste leer ist.
     *
     * @return <code>boolean</code>
     */
    public boolean isEmpty() {
        return head.next == head;
    }

    /**
     * Leert die Liste.
     */
    public void empty() {
        head.next = head;
        head.prev = head;
    }

    /**
     * Liefert zurueck, ob der current-Zeiger auf ein gueltiges Element zeigt.
     *
     * @return <code>boolean</code>
     */
    private boolean current_in_list() {
        return (!isEmpty() && current != head);
    }

    /**
     * Loescht das Element, auf das <code>current</code> zeigt, aus der Liste,
     * setzt current auf den Anfang der Liste zurueck und liefert das geloeschte
     * Element zurueck.
     *
     * @return <code>element</code>
     * @throws EmptySetException
     */
    public E delete() throws EmptySetException {
        E o = null;
        if (current_in_list()) {
            o = current.element;
            current.prev.next = current.next;
            current.next.prev = current.prev;
            current = head;
        } else
            throw new EmptySetException(
                    "Das Objekt konnte nicht gelöscht werden");
        return o;
    }

    /**
     * Loescht das erste Element der Liste und liefert es zurueck.
     *
     * @return <code>element</code>
     * @throws ListEmptyException
     */
    public E removeFirst() throws EmptySetException {
        if (isEmpty())
            throw new EmptySetException(
                    "It was not posible to remove the first element because "
                    + "the list is empty");
        E element = head.next.element;
        head.next = head.next.next;
        head.next.prev = head;
        return element;
    }

    /**
     * Fuegt das uebergebene Element so ein, dass die Liste sortiert bleibt.
     *
     * @param element
     *            - das uebergebene Element
     */
    public void insert(E element) {
        DListNode<E> newElement = new DListNode<E>(element);
        if (isEmpty()) {
            insertNode(head, newElement);
        } else {
            DListNode<E> temp = head;
            while ((temp.next != head)
                    && ((newElement.element).compareTo(temp.next.element) > 0)) {
                // richtiger Platz gefunden
                temp = temp.next;
            }
            insertNode(temp, newElement);
        } // end of if
    } // end of add

    /**
     * Fuegt das uebergebene Knoten-Element node in die Liste nach
     * <code>pos</code> ein.
     *
     * @param pos
     *            - die Position zum einfuegen
     * @param node
     *            - das Element, dass eingefuegt wird
     */
    private void insertNode(DListNode<E> pos, DListNode<E> node) {
        node.prev = pos;
        node.next = pos.next;
        pos.next = node;
        node.next.prev = node;
    }

    /**
     * Prueft, ob die Liste das uebergebene Element enthaelt und liefert das
     * Ergebnis als Wahrheitswert zurueck. Wenn ja, wird current auf das
     * gesuchte Element gesetzt und true zurueck geliefert. Wenn nein, wird
     * false zurueck geliefert.
     *
     * @param o
     *            das uebergebene Element
     * @return <code>boolean</code>
     */
    public boolean contains(E o) {
        // einfacher Fall beseitigen
        if (isEmpty())
            return false;

        current = head.next; // die Suche am Anfang der Liste starten
        E elem = current.element;
        // die Tatsache, dass die Liste sortiert ist, wird hier benutzt
        while ((current != head) && elem.compareTo(o) < 0) {
            current = current.next;
            elem = current.element;
        }
        if (elem.compareTo(o) == 0) {
            return true;
        } else {
            return false; // wir verlassen die Methode
            // das aktuelle Element ist groesser als o
        }
    }

    /**
     * Liefert eine String-Repraesentation der Liste zurueck.
     *
     * @return <code>String</code>
     */
    public String toString() {
        String ss = "Liste: ";
        if (isEmpty())
            return ss + "Empty";
        else {
            DListNode<E> temp = head.next;
            do {
                ss = ss + "  " + temp.element.toString();
                temp = temp.next;
            } while (temp != head);
        }
        ss = ss + "\n";
        return ss;
    }

    /**
     * Gibt eine String-Repraesentation der Liste zur Konsole aus.
     *
     */
    public void print() {
        System.out.println(toString());
    }

    /**
     * Liefert die Anzahl der Elemente in der Liste zurueck.
     *
     * @return <code>int</code>
     */
    public int size() {
        int counter = 0;
        DListNode<E> temp = head;
        if (!isEmpty()) {
            while (temp.next != head) {
                ++counter;
                temp = temp.next;
            }
        } // end of if
        return counter;
    }

    // innere Klasse DListNode

    private class DListNode<E extends Comparable<? super E>> {
        private E element;
        private DListNode<E> next;
        private DListNode<E> prev;

        private DListNode(E e) {
            element = e;
            next = null;
            prev = null;
        }

        private DListNode() {
            this(null);
        }
    }

   
    public static void main (String[] args) throws EmptySetException {
       
        SortedListGen<String> neueListe = new SortedListGen<>();

        System.out.println(neueListe.current_in_list());
        neueListe.insert("ABC1");
        neueListe.insert("ABC2");
        neueListe.insert("ABC3");
        neueListe.insert("ABC4");
        neueListe.print();
        System.out.println(neueListe.isEmpty());
       
        System.out.println(neueListe.current_in_list());
//        System.out.println(neueListe.size());
//        neueListe.print();
//        neueListe.delete();
//        System.out.println(neueListe.size());
//        System.out.println(neueListe.current_in_list());
//        neueListe.print();
       
    }
} // end of class SortedList


EDIT: die Methode funktioniert! man muss nur zuvor schon einaml eine andere methode wie z.b. contains (o) benutzen, da mit sich der current zeiger auch bewegt.
das mit den dummys hab ich aber noch immer nicht verstanden :(
 
Zuletzt bearbeitet:
HarleyDavidson

HarleyDavidson

Bekanntes Mitglied
Ein Dummy ist in der Regel (wie auch hier) ein Platzhalter.
Hätte man die Klasse ohne diesen Dummy implementiert, wäre der Code durch null-Tests aufgeblasen gewesen.
Wenn man also eine Instanz dieser Klasse erstellt, erhält man eine Liste mit einem "Dummy"-Objekt, welches auf sich selbst zeigt und damit die korrekte Funktionalität aller Methoden gewährleistet.

Würde man die Felder prev, next und head mit "null" initialisieren, müsste man in allen Methoden eine zusätzliche Prüfung implementieren, ob der Zeiger null ist..
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
B Doppelt Verkettete Liste - Ist alles gut so? Java Basics - Anfänger-Themen 3
U Datentypen Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 13
J Methoden Doppelt verkettete Liste remove(Object) Java Basics - Anfänger-Themen 8
B OOP Über eine doppelt verkettete Liste iterieren Java Basics - Anfänger-Themen 4
L Doppelt verkettete Liste Java Basics - Anfänger-Themen 6
R doppelt verkettete Liste aus Arrays erstellen Java Basics - Anfänger-Themen 1
S Doppelt verkettete Liste Java Basics - Anfänger-Themen 3
G Doppelt Verkettete Liste Java Basics - Anfänger-Themen 2
A Doppelt Verkettete Liste Java Basics - Anfänger-Themen 16
E doppelt verkettete liste Java Basics - Anfänger-Themen 10
E Datentypen Doppelt verkettete Liste Java Basics - Anfänger-Themen 10
P Einfügen in doppelt verkettete Liste Java Basics - Anfänger-Themen 7
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
K Datentypen Einfach/Doppelt verkettete Liste Java Basics - Anfänger-Themen 4
W Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 2
T Klasse in Java für doppelt verkettete Listen Java Basics - Anfänger-Themen 4
G Doppelt verkettete, generische Liste Java Basics - Anfänger-Themen 11
D doppelt verkettete Liste Java Basics - Anfänger-Themen 16
S Doppelt Verkettete Liste Java Basics - Anfänger-Themen 7
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
J doppelt verkettete Liste Java Basics - Anfänger-Themen 5
L doppelt verkettete Liste Java Basics - Anfänger-Themen 6
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 12
B Doppelt verkettete Liste Java Basics - Anfänger-Themen 16
R Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE! Java Basics - Anfänger-Themen 12
H Doppelt verkettete Listen Java Basics - Anfänger-Themen 2
S doppelt verkettete Listen Java Basics - Anfänger-Themen 4
X Vererbung: Doppelt verkettete Listen Java Basics - Anfänger-Themen 16
R doppelt verkettete Liste Java Basics - Anfänger-Themen 8
F doppelt verkettete liste! Java Basics - Anfänger-Themen 8
R doppelt verkettete azyklische Liste Java Basics - Anfänger-Themen 2
I Input/Output Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 3
N package wird doppelt im exporer angezeigt Java Basics - Anfänger-Themen 2
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
J Fehler beim generieren von 4 Zufallszahlen Zahl doppelt ist eigentlich ausgeschlossen Java Basics - Anfänger-Themen 9
T Löschen in doppelt verketteter Liste Java Basics - Anfänger-Themen 1
L Input/Output Println wird doppelt ausgeführt Java Basics - Anfänger-Themen 11
D Interface Frame doppelt durch Aufruf der GUI Klasse Java Basics - Anfänger-Themen 1
B BufferedReader gibt Datei-Inhalt doppelt aus Java Basics - Anfänger-Themen 3
M Liste Implementation, doppelt next() Java Basics - Anfänger-Themen 13
D Klassen Doppelt so viele Elemente in Arraylist ? Java Basics - Anfänger-Themen 4
Salo Datentypen "Doppelt" List(e) ("gesucht") Java Basics - Anfänger-Themen 6
L do-while-Schleife läuft doppelt, try catch fehler Java Basics - Anfänger-Themen 12
T Java Methode wird unerwünscht doppelt aufgerufen?! Java Basics - Anfänger-Themen 4
NicoDeluxe Doppelt Werte CSV Java Basics - Anfänger-Themen 2
llabusch Verkette Listen - Einfach und Doppelt Java Basics - Anfänger-Themen 3
N Erste Zeile bei BufferedReader doppelt lesen? Java Basics - Anfänger-Themen 2
E Erste Schritte Sortieren von Objekten in doppelt-verlinkter Liste Java Basics - Anfänger-Themen 9
S Methoden Methode wird doppelt aufgerufen ... Java Basics - Anfänger-Themen 5
J Mehrere Zufallszahlen erzeugen, aber keine darf doppelt erzeugt werden - Wie? Java Basics - Anfänger-Themen 5
B Doppelt gekettete Listen Java Basics - Anfänger-Themen 4
G PropertyChangeListener empfängt Events doppelt Java Basics - Anfänger-Themen 5
L doppelt verkette Liste Java Basics - Anfänger-Themen 5
H Fenster doppelt gezeichnet. Java Basics - Anfänger-Themen 2
G Einfügen aus Zwischenablage - alles doppelt? Java Basics - Anfänger-Themen 2
G JFileChooser kommt doppelt Java Basics - Anfänger-Themen 3
N Nullpointerexception bei Doppelt verketteter Liste Java Basics - Anfänger-Themen 7
M Listen richtig doppelt verkettet? Java Basics - Anfänger-Themen 13
D Exceptions in doppelt verketteter Liste Java Basics - Anfänger-Themen 5
C verify() wird doppelt aufgerufen (JTable + InputVerifier) Java Basics - Anfänger-Themen 8
H doppelt verkette liste Java Basics - Anfänger-Themen 2
L rückwärtsausgeben einer doppelt verketteten liste Java Basics - Anfänger-Themen 2
G JList und ListCellRenderer - Vector erscheint doppelt Java Basics - Anfänger-Themen 6
G JComboBox gibt SelectedItem immer doppelt aus Java Basics - Anfänger-Themen 4
B Array doppelt Felder löschen Java Basics - Anfänger-Themen 27
M Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 2
R Zeilen aus datei lesen + doppelt gespeichert? Java Basics - Anfänger-Themen 3
G Trotz Abfrage immer noch Zahlen doppelt Java Basics - Anfänger-Themen 3
R Benutzerregistrierung: Doppelt registriert. Java Basics - Anfänger-Themen 8
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A Verkettete Liste Java Basics - Anfänger-Themen 2
L verkettete Liste Java Basics - Anfänger-Themen 15
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
H Verkettete Liste Java Basics - Anfänger-Themen 7
N Verkettete liste rückwärts ausgeben Java Basics - Anfänger-Themen 5
K Verkettete Liste und seine Methoden Java Basics - Anfänger-Themen 1
A Was könnten typische Prüfungsaufgaben zum Thema lineare, verkettete Listen sein? Java Basics - Anfänger-Themen 5
N Verkettete Liste implementieren Java Basics - Anfänger-Themen 5
O Einfach verkettete Liste - Revert Methode Java Basics - Anfänger-Themen 1
G Verkettete Liste - Neu erzeugte Elemente werden nicht ausgegeben Java Basics - Anfänger-Themen 5
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
C Verkettete Liste - sortiert einfügen Java Basics - Anfänger-Themen 7
R Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel Java Basics - Anfänger-Themen 11
B in einem abstrakten Set ,Elemente einer einfache verkettete List epeichern Java Basics - Anfänger-Themen 13
hooked Verkettete Liste / linked list Java Basics - Anfänger-Themen 2
J Eine Art verkettete Liste aber mit teils mehr als einem Nachfolger Java Basics - Anfänger-Themen 8
V Verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 3
N verkettete Listen Java Basics - Anfänger-Themen 4
K Einfach Verkettete Liste - addFirst() Java Basics - Anfänger-Themen 7
M verkettete Listen Java Basics - Anfänger-Themen 1
G 2 Aufgabe rund um eine verkettete Liste Java Basics - Anfänger-Themen 2
O Verkettete Liste Java Basics - Anfänger-Themen 10
E Methoden auf von Methoden erstellte Objekte zugreifen (verkettete Liste) Java Basics - Anfänger-Themen 10
X Einfach verkettete Liste, keine Fehlermeldung Programm friert ein Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben