Java: Когда я вставляю в свой круговой двусвязный список фиктивный узел заголовка, мой фиктивный узел перемешивается.Зачем?

Question

Я написал круговой двусвязный список с фиктивным узлом спереди.Во время инициализации моего класса DLL я создаю фиктивный узел.Когда я использую отладчик в jGrasp и использую инструмент визуализации, после вставки нескольких чисел, мой фиктивный узел перетасовывается и не остается впереди.Я не понимаю, как я изменяю свой связанный список.В качестве предисловия мой класс узла имеет целочисленное значение val и два указателя с именами prev и next.Я заметил одну вещь: после оператора присваивания curr = dummy, фиктивный узел перетаскивается на curr из предыдущей вставки.

public class DLL {

    Node curr;
    Node help;
    Node dummy = new Node(null, null, -1);

    public DLL() {
        this.curr = curr;
        this.help = help;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public boolean isEmpty() {
        if (dummy.next == dummy && dummy.prev == dummy) {
            return true;
        }
        return false;
    }

    public void push(int elem) {
        if (isEmpty()) {
            Node sec = new Node(dummy, dummy, elem);
            dummy.next = sec;
            dummy.prev = sec;
        } else {
            curr = dummy;
            while (curr.next != dummy) {
                curr = curr.next;
            }
            Node n = new Node(curr, dummy, elem);
            curr.next = n;
            dummy.prev = n;
        }
    }

    public void reverse() {
        curr = dummy;
        help = dummy;
        while (curr.next != help || curr != help) {
            curr = curr.next; // increment curr
            help = help.prev; // decrement help    
            swap(curr, help); // swap
        }
    }
    public void swap(Node curr, Node help) {
        int temp = curr.val;
        curr.val = help.val;
        help.val = temp;
    }
    public boolean contains(int elem) {
        curr = dummy.next;
        while (curr != dummy && elem != curr.val) {
            curr = curr.next;
            if (curr == dummy) {
                return false;
            }
        }

        return true;
    }
}

Вот небольшой тестовый класс, который я использовал:

public class testDLL {
    public static void main(String[] args) {
        DLL dlink = new DLL();
        dlink.push(4);
        dlink.push(6);
        dlink.push(3);
        dlink.push(2);
        assert dlink.contains(4) == true;
        assert dlink.contains(6) == true;
        assert dlink.contains(3) == true;
        assert dlink.contains(2) == true;
        dlink.reverse();

    }
}

Answer 1

Я решил эту проблему, я верю.Вместо того, чтобы устанавливать curr = dummy, я устанавливаю curr = head.Сразу после инициализации dummy в верхней части DLL я установил head = dummy.Таким образом, я не изменяю голову, как я иду вперед.

Answer 2

Добро пожаловать на SO.Вместо того, чтобы найти проблему для вас, я предложу, как вы могли бы решить ее самостоятельно.

Ваш тест пытается проверить слишком много за один раз.Чтобы ваш тест работал, все методы должны работать.Лучше протестировать каждый метод по отдельности (насколько это возможно), а затем перейти к тестированию более сложных сценариев.

Поэтому постарайтесь сначала запустить этот тест:

DLL list = new DLL();
assertTrue(list.isEmpty());

Затем

DLL list = new DLL();
list.push(5);
assertTrue(list.contains(5));

Довольно скоро вы обнаружите, что вам нужен метод, чтобы получить список в другом формате для тестирования.Это довольно типично.

DLL list = new DLL();
list.push(5);
list.push(7);
list.push(5);
assertEquals(list.asList(), List.of(5, 7, 5));

DLL list = new DLL();
list.push(5);
list.push(7);
list.reverse();
assertEquals(list.asList(), List.of(7, 5));

И т. Д.

Таким образом, вы можете проверить, что каждый метод работает с базовыми значениями, прежде чем двигаться дальше.

Теперь пара дизайнерских указателей: использование фиктивного узла для хранения головы и хвоста необычно.Было бы легко испортить значения (как вы сделали).Лучше хранить голову и хвост как отдельные переменные, которые равны null (или, что лучше, Optional.empty), если список пуст и указывает на один и тот же узел для одного элемента.