如何正确删除双圆链表中的元素？

Question

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

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

带有header元素的构造函数

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

listEntrys的内部类

    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方法。实际上，链接代码中的新节点存在很大问题，这是我通过阅读代码检测到的唯一问题。因此，你的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将是临时节点之后的下一个节点。然后它的前一个指针应该指向temp。
2. 在temp节点之后放置新节点不需要在temp的前一个链接中进行任何更改。因此，您在代码中的最后一个链接存在问题。

Answer 2

我可以在此期间解决这个问题。确实是我的add方法阻止了我的remove方法正常工作。

部分出现问题的是我的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;
}