时间戳

首页 > 解决方案 > 如何正确地从双循环链表中删除元素？

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

问题描述

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

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

带有标题元素的构造函数

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。

标签： javalinked-listdoubly-linked-listcircular-list

解决方案

看来您的主要问题的根源是 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. 在临时节点之后放置新节点不需要对临时链接的先前链接进行任何更改。因此，您在代码中的最后一个链接是有问题的。

推荐阅读