双链表java从后面删除

Question

每次我运行我的双链接列表时，除了从列表后面删除外，所有方法都有效。我有一张4，3，9的单子。我从前面拆下（这拿走了4个）。然后，我调用了这个方法，它应该只删除9。相反，当我调用DL列表时，它返回null（这也删除了3）。请帮忙。

    public Object removeLast() {
    Object result = null;

    if (!isEmpty()) {
        result = lastNode.getData();
        lastNode = lastNode.getPreviousNode();

        if (lastNode == null)
            firstNode = null;
        else
            lastNode.setNextNode(null);
    }
    return result;
}

下面是代码的其余部分（它扩展了一个接口；生成的代码对于这个问题不是必需的，所以我们没有填写它。也就是说，节点后面的内容无关紧要）正确的代码：

    public class DList implements DoubleEndedListInterface {

    public Node lastNode;
    public Node firstNode; // reference to first node
    public int numberOfEntries;

    @Override
    public String toString() {
        return "" + firstNode;

    }

    public Node getNodeAt(int givenPosition) {
        assert !isEmpty() && (1 <= givenPosition)
                && (givenPosition <= numberOfEntries);
        Node currentNode = firstNode;

        // traverse the list to locate the desired node
        for (int counter = 1; counter < givenPosition; counter++)
            currentNode = currentNode.getNextNode();

        assert currentNode != null;

        return currentNode;
    } // end getNodeAt

    public void addFirst(Object newEntry) {
        Node newNode = new Node(newEntry);

        if (firstNode == null)
        {
            firstNode = newNode;
            lastNode = newNode;
            numberOfEntries++;
        }
        else 
        {
            newNode.setNextNode(firstNode);
            firstNode.setPreviousNode(newNode);
            firstNode = newNode;
            numberOfEntries++;
        } // end if
    } // end add


    public void addLast(Object newEntry) {
        Node newNode = new Node(newEntry);

        if (firstNode == null)
        {
            firstNode = newNode;
            //lastNode = newNode;
            numberOfEntries++;
        }
        else 
        {
            lastNode.setNextNode(newNode);
            lastNode = newNode;
            numberOfEntries++;
        } // end if
    } // end add

    @Override
    public Object removeFirst() {
        Object result =  firstNode.getData();
        firstNode = firstNode.getNextNode();
        if (numberOfEntries == 1)
            lastNode = null; // solitary entry was removed

        numberOfEntries--;

        return result; // return removed entry, or
                        // null if operation fails
    } // end remove

    @Override
    public Object removeLast() {
        Object result = null;

        if (!isEmpty()) {
            result = lastNode.getData();
            lastNode = lastNode.getPreviousNode();

            if (lastNode == null)
                firstNode = null;
            else
                lastNode.setNextNode(null);
        }
        return result;
    }

    @Override
    public Object getFirst() {
        // TODO Auto-generated method stub
        return firstNode.getData();
    }

    @Override
    public Object getLast() {
        // TODO Auto-generated method stub
        return lastNode.getData();
    }

    @SuppressWarnings("unchecked")
    @Override
    public void moveToEnd() {
        Object temp = (Object) remove(1);
        add(numberOfEntries + 1, temp);

    }

    public class Node {
        public Object data; // entry in bag
        public Node next; // link to next node
        public Node previous;

        public Node(Object dataPortion) {
            this(dataPortion, null, null);
        } // end constructor

        public Node(Object dataPortion, Node nextNode, Node previousNode) {
            data = dataPortion;
            next = nextNode;
            previous = previousNode;
        } // end constructor

        public Object getData() {
            return data;
        } // end getData

        public void setData(Object newData) {
            data = newData;
        } // end setData

        public Node getNextNode() {
            return next;
        } // end getNextNode

        public Node getPreviousNode() {
            return previous;
        }

        public void setPreviousNode(Node previous) {
            this.previous = previous;
        }

        public void setNextNode(Node nextNode) {
            next = nextNode;
        } // end setNextNode

        @Override
        public String toString() {
            return "Node [data=" + data + ", next=" + next + "]";
        }

    } // end Node

    @Override
    public void add(Object newEntry) {
        // TODO Auto-generated method stub

    }

    @Override
    public boolean add(int newPosition, Object newEntry) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Object remove(int givenPosition) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void clear() {
        // TODO Auto-generated method stub

    }

    @Override
    public boolean replace(int givenPosition, Object newEntry) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Object getEntry(int givenPosition) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean contains(Object anEntry) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int getLength() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public boolean isEmpty() {
        boolean result;

        if (numberOfEntries == 0) // or getLength() == 0
        {
            assert firstNode == null;
            result = true;
        } else {
            assert firstNode != null;
            result = false;
        } // end if

        return result;
    } // end isEmpty

    @Override
    public void swap(int i, int j) {
        // TODO Auto-generated method stub

    }

    @Override
    public boolean isTooBig() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public void reduceArray() {
        // TODO Auto-generated method stub

    }

    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void makeRoom(int newPosition) {
        // TODO Auto-generated method stub

    }

    @Override
    public void removeGap(int givenPosition) {
        // TODO Auto-generated method stub

    }

    @Override
    public boolean removeObject(Object anObject) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int getPosition(Object anObject) {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public void append(ListInterface bList) {
        // TODO Auto-generated method stub

    }
}

Answer 1

我看到的是：

addFirst看起来不错，似乎此方法应该可以正常运行。

addLast似乎不正确。特别是，如果通过addLast将节点添加到空列表中，lastNode成员变量将没有有效值。

然后RemveFirst和RemveLast都需要帮助，特别是在处理NumberOfEntry成员和检查空列表时。

对于“list begins empty”条件，还应将“next”和“previous”指针设置为null，这样就不会有杂散数据干扰。

Answer 2

removeLast非常合理，尽管可能缺少一个——numberOfEntries。其余的代码我没有读，因为它有点太多了。

但是add很奇怪：它似乎使用了一个局部变量lastNode对一些字段lastNode什么也不做。