Einfügen in eine doppelt verkettete Liste

[yachty66]

Ich komme im Code nicht mehr weiter, ich versuche ein Element in eine doppelt verkettete Liste einzufügen.

public class DoublyLinkedList<T> implements Listable<T> {

    private Node head = null;
    private Node tail = null;

    private class Node {
        T data = null;
        Node next = null;
        Node prev = null;
    }
    
    
    public void addTwo(T item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = null;
        newNode.prev = null;
        
        if (head == null && tail == null) {
            head = newNode;
            tail = newNode;
        }else {
            
        }
    }

Wenn der tail und head == 0 sind dann ist die Liste leer, soweit bin ich, allerdings, weiß ich nicht wie ich den Code schreiben sollte, wenn der tail und head != null sind.

 

[kneitzel]

Hast du es einmal aufgezeichnet? Was hast du und was muss geändert werden?
Dabei sind dann auch so Dinge wichtig wie: wo soll denn eingefügt werden? Am Anfang? Am Ende?

Das kannst du aufzeichnen und dann erst mal in Worte packen: was muss alles geändert werden?

 

[yachty66]

Ich habe einen Knoten A der in beide Richtungen verweist prev<--A-->next - in diesem Fall ist prev und next == null, weil es nur ein Element gibt was sich in der Liste befindet. prev<--A <-->B-->next - in diesem Fall ist prev von B != null, weil auf das Element A gezeigt wird. Wenn ich jetzt etwas einfügen möchte muss ich die Liste iterieren bis B next == null ist und dort muss dann das neue Element eingefügt werden. Oder? @kneitzel

 

[kneitzel]

Also willst du am Ende einfügen. Du könntest durch die Liste iterieren um ans Ende zu kommen. Aber schau einfach noch einmal Deine Liste an. Evtl. gibt es ja noch eine andere Möglichkeit.

 

[yachty66]

Muss von der Uni aus in einer doppelt verketteten Liste implementieren. @kneitzel
Ja, möchte gerne am Ende einfügen.

 

[yachty66]

Folgend ist mein Code, bin mir allerdings unsicher, ob dies seinen Zweck erfüllt.

public void addTwo(T item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = null;
        newNode.prev = null;
        
        if (head == null && tail == null) {
            head = newNode;
            tail = newNode;
        }else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

 

[kneitzel]

Schau einfach einmal alle Instanzvariablen an:
- Haben alle Instanzvariablen der Liste den richtigen Wert?
- Haben alle Instanzvariablen der Beteiligten Nodes den richtigen Wert?

Das ist ja etwas, das du durchgehen kannst ...

 

[yachty66]

Okay. Habe den Code noch einmal etwas umgeschrieben und er läuft auch, aber ich weiß nicht ob er korrekt ist;D
@kneitzel

public void add(T item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = null;
        newNode.prev = null;
      
        if (head == null) {
            newNode.prev = null;
            head = newNode;
            return;
      
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
            newNode.prev = last;
        }
    }

 

[thecain]

Was ist wohl 'tail'?