Как правильно удалить элемент из дважды кругового связанного списка?

Question

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

Я провел много исследований, но мне было трудно найти что-то, что соответствует моим потребностям Проблема в том, что у меня нет постоянного указателя головы и хвоста, как обычно в двусвязном списке, но я должен работать с «заголовком» в качестве начальной и конечной точки.

Конструктор с элементом заголовка

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

Внутренний класс для списка Энтрис

    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;
        }
    }

Способ добавления в список:

    /**
     * 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

    DEntry toBeDeleted = header;

        if(position < 0 || position > size) {
            return -1;
        }
        if(getEntry(position) == null) {
            return -1;
        } else {
        toBeDeleted = getEntry(position);
        }

        int dataOfDeletedNode = toBeDeleted.data;

        if(position == 0) {
            header.previous.next = toBeDeleted.next;
            header.next.previous = toBeDeleted.previous;
        } else if(position == size){
            toBeDeleted.previous.next = header.next;
            toBeDeleted.next.previous = toBeDeleted.previous;
        } else {
            toBeDeleted.previous.next = toBeDeleted.next;
            toBeDeleted.next.previous = toBeDeleted.previous;
        }



        size--;
        System.out.println(dataOfDeletedNode);
        return dataOfDeletedNode;
    }

Если я запускаю код

list.add(0, 10);
list.add(1, 20);
list.add(0, 30);
remove(1); // 10 should be deleted

Вместо 30, 20 я получаю только 20.

Answer 1

Я мог бы решить эту проблему в то же время.Это был действительно мой метод add, который мешал моему методу удаления работать должным образом.

Частично ошибкой был мой цикл while, который остановился на (i

) Вот что я придумал в методе add, и всенормально работает.

public int add(int position, int value) {

    // Creates a new listEntry 
    DEntry listEntry = new DEntry(value, null, null);
    DEntry temp = header;

    int i = 0;

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

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

    // setting the elements neighbours
    listEntry.next = temp;
    listEntry.previous = temp.previous;

    // placing the new element between last and next
    temp.previous.next = listEntry;
    temp.previous = listEntry;

    // places the new entry in the list
    temp = listEntry;
    size++;

    return 0;
}

Answer 2

Похоже, что источником вашей основной проблемы является метод add.На самом деле, существует большая проблема в связывании новых узлов в вашем коде, и это была единственная проблема, которую я обнаружил, читая ваш код.Таким образом, ваш метод add должен выглядеть примерно так:

public int add(int position, int value) {
    DEntry listEntry = new DEntry(value, null, null);

    DEntry temp = header;

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

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

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

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

    return 0;
}

1. listEntry будет следующим узлом после временного.Тогда его предыдущий указатель должен указывать на темп.
2. установка нового узла после временного узла не требует каких-либо изменений в предыдущей ссылке временного узла.Итак, последняя ссылка в вашем коде была проблематичной.