Doppelt verkettete Liste implementieren

B

breezy

Mitglied
Hallo zusammen,

ich habe die Aufgabe bekommen eine doppelt verkettete Liste zu implementieren.

Wir haben folgenden Code als Vorlage bekommen:

Java:
/**
 * Class representing a list of int values based on double linking
 */
public class MyDoubleLinkedList {
    /**
     * the header element of this list linking to the first and last element *
     */
    private final DEntry header;

    /** the number of elements in the list */
    private int size;

    public MyDoubleLinkedList() {
        header = new DEntry(0, null, null);
        header.next = header;
        header.previous = header;
        size = 0;
    }

    /**
     * Returns the number of elements in this list
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

    /**
     * Returns the value at the position specified
     *
     * @param position the 0 based position of the value to return
     * @return the value at the passed position, -1 if unsuccessful. This means that
     *         this implementation is not working properly if -1 is stored in the
     *         list
     */
    public int get(int position) {
        // TODO: please put your code here

        return 0;
    }

    /**
     * Returns object of type DEntry at the position specified
     *
     * @param position the 0 based position of the value to return
     * @return the object at the passed position, -1 if unsuccessful. This means
     *         that this implementation is not working properly if -1 is stored in
     *         the list
     */
    public DEntry getEntry(int position) {
        // TODO: please put your code here
        return null;
    }

    /**
     * Adds a new element into the list at the position specified
     *
     * @param position the 0 based position at which to add the passed value
     * @param value    the value to add
     * @return 0 if adding was successful, -1 if not
     */
    public int add(int position, int value) {
        // TODO: please put your code here

        if (position < 0) {
            return -1;
        }

        DEntry temp = header;

        int i = 0;

        if (position == 0) {
            temp = header;
        } else {
            while (i < position) {

                temp = temp.next;
                i++;

            }
        }

        DEntry listEntry = new DEntry(value, null, null);
        listEntry.next = temp;
        listEntry.previous = temp.previous;

        temp.previous.next = listEntry;
        temp.previous = listEntry;

        return 0;
    }

    /**
     * Removes an element at the position specified from the list
     *
     * @param position the 0 based position of the value to remove
     * @return value of the removed entry if removing was successful, -1 if not
     */
    public int remove(int position) {
        // TODO: please put your code here
        size--;
        return 0;
    }

    /**
     * Searches for the first occurrence of the passed value in the list
     *
     * @param value the value to search
     * @return the position of the value in the list, -1 if not found
     */
    public int indexOf(int value) {
        // TODO: please put your code here
        return 0;
    }

    /**
     * Prints the numbers in the list to console
     */
    public void print() {
        System.out.print("List: ");
        DEntry result = header.next;
        while (result != header) {
            System.out.print(result.data + ", ");
            result = result.next;
        }
        System.out.println();
    }

    /**
     * A single list entry for double linking.
     */
    @SuppressWarnings("unused")
    class DEntry {
        /** the data element represented by this entry */
        private final int data;

        /** reference to the previous element in the list */
        private DEntry previous;

        /** reference to the next element in the list */
        private DEntry next;

        /**
         * @param data     the data object this entry represents
         * @param previous reference to the previous element in the list
         * @param next     reference to the next element in the list
         */
        public DEntry(int data, DEntry previous, DEntry next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }
    }
}

Ich habe bereits versucht die "add" methode zu schreiben, jedoch fügt er das Element immer ganz hinten an die Liste, nicht an Position 0, falls diese übergeben wird.

Wo liegt bei "add" mein Fehler?
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Ich kann spontan nicht erkennen warum add den Entry am Ende anfügen sollte, aber die Zeile schmeißt sicher eine NullPointerException:
temp.previous.next = listEntry;
Im Fall temp == header, dann ist previous null und du kannst nicht auf next von null zugreifen.

Bist du dir außerdem sicher, dass while in print() nicht auf Ungleichheit mit null prüfen sollte?

Und fange um himmels Willen nicht mit add an. Erstmal brauchst du get, das kannst du dir für add auch zu Nutzen machen.

Edit: Ich sehe gerade du hast einen circle implementiert, das ist nicht der Zweck einer "normalen" doppelt verketteten Liste.
 
Zuletzt bearbeitet:
B

breezy

Mitglied
Danke für deine Antwort!

Alles, ausser was ich in add() schon verbrochen habe, war vorgegeben und soll nicht verändert werden, auch print().

Dann werde ich mich erstmal mit get() versuchen. Leider gabs nicht viel Erklärung zu der doppelt verketteten Liste, ich werde mich mit Sicherheit nochmal melden..
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Wenn der Konstruktor auch schon vorgegeben war, dann wirst du mit der Suche mit DV-Liste nicht so viel Freude haben.
Die eigentliche DV-Liste sieht so aus:

Code:
    head    next    next    next
    ---->xxx---->xxx---->xxx---->null
null<----xxx<----xxx<----xxx<----
    prev    prev    prev    tail

Dein Konstruktor indiziert aber sowas:

Code:
         head
xx---->xx<----
xx<----xx
^|     ^|
||     ||
|v     |v
xx---->xx
xx<----xx

Das wirst du mit dem Begriff RingBuffer vermutlich eher fündig.
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Ansonsten kann ich dir die Frage beantworten warum dein Element ans Ende gestellt wird. Überleg mal...

Angenommen du hast bereits A, B und C in die Liste eingefügt. D ist das neue Element für Stelle 0.

listEntry.next = temp;
listEntry.previous = temp.previous;

temp.previous.next = listEntry;
temp.previous = listEntry;

Das ist das was du mit den 4 Zeilen tust:

breezy.png

Wie du siehst ist D am Ende der Kette. Du musst einfach nur den head noch auf D zeigen lassen.
 
B

breezy

Mitglied
Danke für deine tolle Erklärung!!

Deshalb tuts mir umso mehr leid, dass ich die Verknüpfung einfach nicht hinbekomme...

Den header auf D zeigen lassen heisst für mich in meinem code dann soviel wie:

Java:
header.previous = listEntry;

Zumindest so oder so ähnlich...aber egal was ich mit wem Verknüpfe, wenn ich das teste mit:
list.add(0, 10);
list.add(1, 20);
list.add(0, 30);
list.print();

Ist das Ergebnis immer 10, 20, 30.
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Nein, richtig wäre
Java:
header=listEntry;

Aber eben nur im Fall du willst den Knoten an Stelle 0 einfügen.
 
B

breezy

Mitglied
So, ich bins wieder. Deine Veranschaulichung hat mir sehr geholfen.

Ich bin nun soweit fast durch und alles funktioniert so wie es soll. Allein das Entfernen eines Elements an einer bestimmten Position will nicht klappen, zwar entferne ich ein Element, jedoch verliere ich immer das davor mit.

Bsp.:
Liste -> A / B / C
remove(Element 2);
Liste -> C

Ich sehe einfach nicht das Problem.

Hier jedenfalls mein Code:

Java:
public class MyDoubleLinkedList {
    /**
     * the header element of this list linking to the first and last element *
     */
    private final DEntry header;

    /** the number of elements in the list */
    private int size;

    public MyDoubleLinkedList() {
        header = new DEntry(0, null, null);
        header.next = header;
        header.previous = header;
        size = 0;
    }

    /**
     * Returns the number of elements in this list
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

    /**
     * Returns the value at the position specified
     *
     * @param position the 0 based position of the value to return
     * @return the value at the passed position, -1 if unsuccessful. This means that
     *         this implementation is not working properly if -1 is stored in the
     *         list
     */
    public int get(int position) {
        // TODO: please put your code here
        DEntry temp;
        int i = 0;

        if (position < 0 || position >= size) {
            return -1;
        } else {
            temp = header;
            while (i < position) {
                temp = temp.next;
                i++;
            }
            temp = temp.next;

        }
        return temp.data;
    }

    /**
     * Returns object of type DEntry at the position specified
     *
     * @param position the 0 based position of the value to return
     * @return the object at the passed position, -1 if unsuccessful. This means
     *         that this implementation is not working properly if -1 is stored in
     *         the list
     */
    public DEntry getEntry(int position) {
        // TODO: please put your code here
        DEntry temp;
        int i = 0;

        if (position < 0 || position >= size) {
            return null;
        } else {
            temp = header;
            while (i < position) {
                temp = temp.next;
                i++;
            }
            temp = temp.next;
        }
        return temp;
    }

    /**
     * Adds a new element into the list at the position specified
     *
     * @param position the 0 based position at which to add the passed value
     * @param value    the value to add
     * @return 0 if adding was successful, -1 if not
     */
    public int add(int position, int value) {
        // TODO: please put your code here
        DEntry listEntry = new DEntry(value, null, null);

        DEntry temp = header;
        int i = 0;

        if (position < 0 || position > size) {
            return -1;
        }

        if (position == 0) {
            temp = header;

        } else {
            while (i < position) {
                temp = temp.next;
                i++;
            }
        }

        listEntry.next = temp.next;
        listEntry.previous = temp.next;
        temp.next = listEntry;
        temp.next.previous = listEntry.next;
        size++;

        return 0;
    }

    /**
     * Removes an element at the position specified from the list
     *
     * @param position the 0 based position of the value to remove
     * @return value of the removed entry if removing was successful, -1 if not
     */
    public int remove(int position) {
        // TODO: please put your code here
        
        if(position < 0 || position >= size) {
            return -1;
        }
        
        DEntry toBeDeleted = getEntry(position);
        int dataOfDeletedNode = toBeDeleted.data;
        
        toBeDeleted.next.previous = toBeDeleted.previous;
        toBeDeleted.previous.next = toBeDeleted.next;
        
        
        size--;
        System.out.println(dataOfDeletedNode);
        return dataOfDeletedNode;
    }

    /**
     * Searches for the first occurrence of the passed value in the list
     *
     * @param value the value to search
     * @return the position of the value in the list, -1 if not found
     */
    public int indexOf(int value) {
        // TODO: please put your code here
        DEntry temp = header;
        int position = 0;
        boolean notFound = false;

        do {
            position++;
            temp = temp.next;
            if (position-1 >= size) {
                notFound = true;
                break;
            }
        } while (temp.data != value);

        if (notFound) {
            return -1;
        } else {
            return position -1;
        }
    }

    /**
     * Prints the numbers in the list to console
     */
    public void print() {
        System.out.print("List: ");
        DEntry result = header.next;
        while (result != header) {
            System.out.print(result.data + ", ");
            result = result.next;
        }
        System.out.println();
    }

    /**
     * A single list entry for double linking.
     */
    @SuppressWarnings("unused")
    class DEntry {
        /** the data element represented by this entry */
        private final int data;

        /** reference to the previous element in the list */
        private DEntry previous;

        /** reference to the next element in the list */
        private DEntry next;

        /**
         * @param data     the data object this entry represents
         * @param previous reference to the previous element in the list
         * @param next     reference to the next element in the list
         */
        public DEntry(int data, DEntry previous, DEntry next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }
    }
}
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Allein das Entfernen eines Elements an einer bestimmten Position will nicht klappen, zwar entferne ich ein Element, jedoch verliere ich immer das davor mit.

Bsp.:
Liste -> A / B / C
remove(Element 2);
Liste -> C

Kann ich nicht nachvollziehen, das scheint doch richtig. Bei A-B-C ist C an Position 2 und das gibst du doch aus oder nicht?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
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
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
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
T Klasse in Java für doppelt verkettete Listen Java Basics - Anfänger-Themen 4
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
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
V Methoden Verkettete Listen Index eines Elementes ausgeben Java Basics - Anfänger-Themen 10

Ähnliche Java Themen

Anzeige


Oben