我的 DoubleLinkedList 的实现有什么问题？

Question

我目前正在学习数据结构和算法，其中一项练习是从头开始实现 DoublyLinkedList。不幸的是，当我尝试对我的列表执行 "listDelete" 操作时，我的代码适用于某些整数值而不适用于某些整数值。当我尝试删除 23、45、100、5、15 时，它工作正常。当我尝试从列表中删除 400 时出现 Exception。

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * Created on 13-Aug-16.
 */
public class DoublyLinkedList<Item> implements Iterable<Item>{
    private Node<Item> head ;

    private class Node<Item>{
        private Item key;
        private Node<Item> prev;
        private Node<Item> next;
    }

    public Node<Item> listSearch(Item key)
    {
        Node<Item> currentNode = head ;

        while (currentNode != null && currentNode.key != key)
                currentNode = currentNode.next ;

        return currentNode ;
    }

    public void listInsert(Item item)
    {
        Node<Item> newNode = new Node<>();  //create an object of incoming item
        newNode.next = head ;
        newNode.prev = null ;
        newNode.key = item ;

        if (head != null)
            head.prev = newNode ;

        head = newNode;
    }

    public void listDelete(Item item){
        Node<Item> nodeToDelete = listSearch(item);

        if (nodeToDelete == null)
            throw new NoSuchElementException("Cant find element");

        if(nodeToDelete.prev != null)
            nodeToDelete.prev.next = nodeToDelete.next ;
        else
            head = nodeToDelete.next;

        if (nodeToDelete.next != null)
            nodeToDelete.next.prev = nodeToDelete.prev ;
    }

    public Iterator<Item> iterator(){
        return new DoublyLinkedListIterator();
    }

    private class DoublyLinkedListIterator implements Iterator<Item>{
        private Node<Item> nextNode;

        public DoublyLinkedListIterator(){
            nextNode = head;
        }

        public boolean hasNext(){
            return nextNode != null ;
        }

        public Item next(){
            if (!hasNext())
                throw new NoSuchElementException();

            Item key = nextNode.key;

            nextNode = nextNode.next ;

            return key;
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }
    } //end of Iterator class

    public String toString(){
        StringBuilder sb = new StringBuilder();

        for(Item item : this)
            sb.append(item + ", ");

        return sb.toString();
    }

    public static void main(String[] args) {
        DoublyLinkedList<Integer> numbers = new DoublyLinkedList<>();

        Random random = new Random();

        numbers.listInsert(23);
        for (int i=1; i <=5; i++)
            numbers.listInsert(random.nextInt(100));
        numbers.listInsert(45);
        numbers.listInsert(100);
        numbers.listInsert(400);
        numbers.listInsert(5);

       for (int i=1; i <=10; i++)
            numbers.listInsert(random.nextInt(100));
        numbers.listInsert(15);

        System.out.println("Before");
        System.out.println("LIST: " + numbers);

        System.out.println("Deleting......................");
        numbers.listDelete(100); //doesnot work for some set of integers
        System.out.println("After");
        System.out.println("LIST: " + numbers);
    }
} //end of class

Answer 1

您在这里使用的是通用数据类型 (Item)，因此在比较两个元素时您应该使用 equals 方法而不是使用引用 (==)

public Node<Item> listSearch(Item key)
    {
        Node<Item> currentNode = head ;   
        while (currentNode != null && !currentNode.key.equals(key))
                currentNode = currentNode.next ;
        return currentNode ;
    }

我的 DoubleLinkedList 的实现有什么问题？

What is wrong with the implementation of my DoubleLinkedList?

java

data-structures

doubly-linked-list