如何正确地从双向循环链表中删除元素？

Question

我必须使用自己的构造函数实现一个双向循环链表，我已经差不多完成了，但无法弄清楚为什么 remove 方法不起作用。

我做了很多研究，但很难找到符合我需要的东西。问题是我没有永久的头指针和尾指针，就像通常在双向链表中一样，但必须使用 "header" 作为起点和终点。

带有头元素的构造函数

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

列表条目的内部 class

    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

看来你的主要问题来源是添加方法。实际上，在您的代码中 linking 新节点存在一个很大的问题，这是我通过阅读您的代码检测到的唯一问题。因此，您的添加方法应该是这样的：

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

listEntry 将是临时节点之后的下一个节点。那么它的前一个指针应该指向温度。
将新节点放在临时节点之后不需要对之前的 link 临时节点进行任何更改。因此，您代码中的最后一个 linking 是有问题的。

Answer 2

我可以同时解决这个问题。确实是我的添加方法导致我的删除方法无法正常工作。

部分错误是我的 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;
}

如何正确地从双向循环链表中删除元素？

How do I remove an element from a doubly circular linked list properly?

java

linked-list

circular-list

doubly-linked-list