Java:LinkedList findnode() 方法和 isEmpty() 方法

Question

我有一个实现可迭代接口(interface)的 LinkedList 类，在 LinkedList 类中我有一个内部节点类。我有另一个运行 JUnit 4 的 TestLinkedList 类。该测试类将检查链表类中的所有函数。

这是我的 LinkedListClass:

public class LinkedList<T> implements Iterable<T>
{
    public class Node
    {
        private T value;
        private Node next;

        public Node(Node next, T value)
        {
            this.next = next;
            this.value = value;
        }

        /**
         * Returns the next node in the linked list.
         * 
         * @return The next node in the linked list.
         */
        public Node getNext()
        {
            return this.next;
        }

        /**
         * Set the next node in the linked list.
         * 
         * @param next
         *            The node to be added to the LinkedList.
         */
        public void setNext(Node next)
        {
            this.next = next;
        }

        /**
         * Return the value contained in the node.
         * 
         * @return the value contained in the node.
         */
        public T getValue()
        {
            return this.value;
        }

        /**
         * Set the node with the value given.
         * 
         * @param value
         *            The value to be placed in the node.
         */
        public void setValue(T value)
        {
            this.value = value;
        }

        public String toString()
        {
            return "Node " + this.value;
        }
    }
    public Node front;
    public LinkedList()
    {
        front = null;
    }


    /**
     * Return the number of elements in the LinkedList
     * 
     * @return The size of the LinkedList
     */
    public int getSize()
    {
        Node current = front;
        int count = 0;
        while (current != null)
        {
            count++;
            current = current.getNext();
        }
        return count;
    }

    /**
     * Return true if the LinkedList is empty, false otherwise
     * 
     * @return true if the LinkedList is empty, false otherwise
     */
    public boolean isEmpty()
    {
        return front == null;
    }

    /**
     * Insert a node at the front of the linked list. The first variable should now point to this node. Wrap it in a
     * node and add it to the list. Do not add the Node if it already exists in the list.
     * 
     * @param node
     *            The node to be inserted into the linked list.
     * @return true if inserted, false if already in list and cannot be inserted.
     */
    public boolean insertFront(T element)
    {
            Node current = front;
            boolean isExist = false;
            while (current != null)
            {
                if (current.getValue().equals(element))
                {
                    isExist = true;
                }
                current = current.getNext();
            }
            if (isExist == true)
            {
                return false;
            }
            else
            {
                front = new Node(front, element);
                return true;    
            }
    }

    /**
     * Insert a node at the back of the linked list. Wrap it in a node and add it to the list. Do not add the Node if it
     * already exists in the list.
     * 
     * @param node
     *            The node to be inserted into the linked list.
     * @return true if inserted, false if already in list and cannot be inserted.
     */

    public boolean insertBack(T element)
    {
        if (front == null)
        {
            insertFront(element);
            return true;
        }
        else
        {
            Node current = front;
            Node temp = current;
            while (current!= null && !current.getValue().equals(element))
            {
                current = current.getNext();
            }
            if (current != null)
            {
                return false;
            }
            else
            {
                while(temp.getNext() != null)
                {
                    temp = temp.getNext();
                }
                temp.setNext(new Node(null, element));
                return true;
            }
        }
    }

    /**
     * Insert the given node after the currentNode given. Wrap it in a node and add it in a position after the node
     * specified by the variable {@code currentNode}. Throws a NodeNotFoundException if it can't found the node given.
     * Do not add the Node if it already exists in the list.
     * 
     * @param currentNode
     *            The node to look for to add the given node behind.
     * @param node
     *            The element to be inserted into the linked list.
     * @throws NodeNotFoundException
     *             Thrown if the element given is not found
     * @return true if inserted, false if already in list and cannot be inserted.
     */

    public boolean insertAfter(T currentElement, T element) throws NodeNotFoundException
    {
        Node current = front;
        Node check = current;
        while (current != null && !current.getValue().equals(currentElement))
        {
            current = current.getNext();
        }
        if (current == null)
        {
            throw new NodeNotFoundException("" + currentElement);
        }
        else
        {
            while(check != null && !check.getValue().equals(element))
            {
                check = check.getNext();
            }
            if (check != null)
            {
                return false;
            }
            else
            {
                current.setNext(new Node(current, element));
                return true;
            }
        }
    }

    /**
     * Insert the given node before the currentNode given. Wrap it in a node and add it in a position after the node
     * specified by the variable {@code currentNode}. Throws a NodeNotFoundException if it can't found the node given.
     * Do not add the Node if it already exists in the list.
     * 
     * @param currentNode
     *            The node to look for to add the given node in front of.
     * @param node
     *            The element to be inserted into the linked list.
     * 
     * @throws NodeNotFoundException
     *             Thrown if the element given is not found
     * @return true if inserted, false if already in list and cannot be inserted.
     */

    public boolean insertBefore(T currentElement, T element) throws NodeNotFoundException
    {
        if (front == null)
        {
            throw new NodeNotFoundException("" + currentElement);
        }
        if (front.getValue().equals(currentElement))
        {
            insertFront(element);
            return true;
        }
        Node previous = null;
        Node current = front;
        Node check = current;
        while (current != null && !current.getValue().equals(currentElement))
        {
            previous = current;
            current = current.getNext();
        }
        if (current == null)
        {
            throw new NodeNotFoundException("" + currentElement);
        }
        else
        {
            while (check != null && !check.getValue().equals(element))
            {
                check = check.getNext();
            }
            if (check != null)
            {
                return false;
            }
            previous.setNext(new Node(current, element));
            return true;
        }
    }

    /**
     * Remove the node matches the given element. Return the element that is removed. Throws NodeNotFoundException if
     * the element is not found.
     * 
     * @param element
     *            The element to find and remove.
     * @return Return the node that contains the element that was removed.
     * @throws NodeNotFoundException
     *             Thrown if the element to be found can't be found.
     */
    public T remove(T element) throws NodeNotFoundException
    {
        if(front == null)
        {
            throw new NodeNotFoundException(element.toString());
        }

           if( front.getValue().equals(element) )
           {
              front = front.getNext();
              return element;
           }

           Node current  = front;
           Node previous = null;

           while(current != null && !current.getValue().equals(element) )
           {
              previous = current;
              current = current.getNext();
           }

           if(current == null)
           {
               throw new NodeNotFoundException(element.toString());
           }

           previous.setNext(current.getNext());
           return element;
    }

    /**
     * Remove all nodes in the LinkedList, return all nodes in an ArrayList.
     * 
     * 
     * @return Returns all nodes in an ArrayList.
     */

    public ArrayList<T> removeAll() throws NodeNotFoundException
    {
        Node current = front;
        ArrayList<T> arrayList = new ArrayList<T>();

        while (current != null)
        {
            arrayList.add(current.getValue());
            current = current.getNext();
        }
        front = null;
        return arrayList;
    }

    /**
     * Return true if the element passed in is in the linked list.
     * 
     * @param element
     *            The element to check for.
     * @return true if the element exists in the linked list, false otherwise.
     */
    public boolean contains(T element)
    {
        Node current = front;
        while (current != null)
        {
            if (current.value.equals(element))
            {
                return true;
            }
            current = current.getNext();
        }
        return false;
    }

    /**
     * Find an element and return it if it is found, otherwise return null
     * 
     * @param element
     *            The element to look for.
     * @return The element if found, null if not.
     */
    public T findElement(T element)
    {
        Node check = front;
        while (check != null && !check.getValue().equals(element))
        {
            check = check.getNext();
        }
        if (check == null)
        {
            return null;
        }
        else
        {
            return check.getValue();
        }
    }

    /**
     * Find an element and return it if it is found, otherwise return null
     * 
     * @param element
     *            The element to look for.
     * @return The element if found, null if not.
     */
    public Node findNode(T element)
    {
        if(contains(element) == false)
        {
            return null;
        }
        else
        {
            Node check = front;
            while (check != null && !check.getValue().equals(element))
            {
                check = check.getNext();
            }
            return check;
        }
    }

    /**
     * Converts the LinkedList to an ArrayList.
     * 
     * @return An ArrayList containing all elements that are contained within the linked list.
     */
    public ArrayList<T> convert()
    {
        Node current = front;
        ArrayList<T> arrayList = new ArrayList<T>();

        while (current != null)
        {
            arrayList.add(current.getValue());
            current = current.getNext();
        }
        return arrayList;
    }

    /**
     * Return the linked list as a string in the format element -> element -> element. For example
     * "first -> second -> third"
     * 
     * @return This linked list in the form of a string.
     */
    @Override
    public String toString()
    {
        Node current = front;
        String s = "";

        while (current.getNext() != null)
        {
            s += current.getValue() + "->";
            current = current.getNext();
        }
        s += "" + current.getValue();
        return s;
    }
    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Iterable#iterator()
     */
    @Override
    public Iterator<T> iterator()
    {
        return new LinkedListIterator<T>(new LinkedList<T>());
    }
}

这是我的 LinkedListIterator 类:

public class  LinkedListIterator<T> implements Iterator<T>
{
    LinkedList<T>.Node previous;
    LinkedList<T>.Node current;
    public LinkedListIterator(LinkedList<T> list)
    {
        current = list.front;
    }
    /*
     * (non-Javadoc)
     *
     * @see java.util.Iterator#hasNext()
     */
    @Override
    public boolean hasNext()
    {
        return current != null;
    }

    /*
     * (non-Javadoc)
     *
     * @see java.util.Iterator#next()
     */
    @Override
    public T next()
    {
        if (!hasNext())
        {
            return null;
        }
        T temp = current.getValue();
        previous = current;
        current = current.getNext();
        return temp;
    }

    /*
     * (non-Javadoc)
     *
     * @see java.util.Iterator#remove()
     */
    @Override
    public void remove()
    {
        previous.setNext(current.getNext());
    }
}

这是我的 TestLinkedList 类:

public class TestLinkedList
{
    private static String FIRST = "First";
    private static String SECOND = "Second";
    private static String THIRD = "Third";
    private static String FOURTH = "Fourth";
    private static String MISSING = "Missing";
    private static String TEST_STRING = "First->Second->Third->Fourth";
    private static String TEST_ARRAY = "[First,Second,Third,Fourth]";
    private LinkedList<String> testList;

    @Before
    public void setUp() throws NodeNotFoundException
    {
        testList = new LinkedList<String>();
    }

    @Test
    public void testNextAndHasNext() throws NodeNotFoundException
    {
        insertAll(testList);
        assertTrue("Next/HasNext failed", compareListToStrings(testList, FIRST, SECOND, THIRD, FOURTH));
    }

    @Test
    public void testIsEmpty() throws NodeNotFoundException
    {
        insertAll(testList);
        assertFalse("isEmpty Failed", testList.isEmpty());
        removeViaIterator(testList);
        assertTrue("isEmpty Failed after emptying", testList.isEmpty());
    }

    @Test
    public void testIteratorRemove() throws NodeNotFoundException
    {
        insertAll(testList);
        removeViaIterator(testList);
        Iterator<String> iter = testList.iterator();
        assertFalse("Iterator remove failed", iter.hasNext());
    }

    @Test
    public void testInsertFrontAndBack()
    {
        assertTrue("insertFront failed on first insert", testList.insertFront(FIRST));
        assertTrue("insertFront failed, list has too many elements", compareListToStrings(testList, FIRST));
        assertFalse("insertFront failed, same element added to list", testList.insertFront(FIRST));
        assertTrue("insertBack failed when inserting element not in list", testList.insertBack(FOURTH));
        assertTrue("insertBack failed, list has wrong elements", compareListToStrings(testList, FIRST, FOURTH));
        assertFalse("insertBack failed, same element already added to list", testList.insertBack(FOURTH));
    }

    @Test(expected = NodeNotFoundException.class)
    public void testNodeNotFound() throws NodeNotFoundException
    {
        testList.insertBefore(MISSING, MISSING);
    }

    @Test
    public void testInsertBeforeAndAfter() throws NodeNotFoundException
    {
        testList.insertFront(FOURTH);
        testList.insertFront(FIRST);
        assertTrue("insertBefore failed", testList.insertBefore(FOURTH, THIRD));
        assertTrue("insertBefore failed, list does not have right elements",
                compareListToStrings(testList, FIRST, THIRD, FOURTH));
        assertFalse("insertBeforeFailed on inserting duplicate elements", testList.insertBefore(FOURTH, THIRD));
        assertTrue("insertAfter failed", testList.insertAfter(FIRST, SECOND));
        assertTrue("insertAfter failed, list does not have right elements",
                compareListToStrings(testList, FIRST, SECOND, THIRD, FOURTH));
        assertFalse("insertAfter failed on inserting duplicate elements", testList.insertAfter(FIRST, SECOND));
    }

    @Test
    public void testToStringAndToArray()
    {
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        String listString = testList.toString();
        assertTrue("toString failed", listString.replaceAll("\\s+", "").equals(TEST_STRING));
        String arrayString = testList.convert().toString();
        assertTrue("convert failed", arrayString.replaceAll("\\s+", "").equals(TEST_ARRAY));
    }

    @Test
    public void testContains()
    {
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        assertTrue("Contains failed", testList.contains(FIRST));
    }

    @Test
    public void testFind()
    {
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        String element = testList.findElement(SECOND);
        assertNotNull("find failed, element null", element);
        assertEquals(SECOND, element);
        assertTrue("Find failed", findNode(testList, testList.findNode(SECOND)));
    }

    @Test
    public void testRemove() throws NodeNotFoundException
    {
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        String second = testList.remove(SECOND);
        assertNull("Found Second in list after removal", testList.findNode(SECOND));
        assertEquals(SECOND, second);
    }

    @Test
    public void testRemoveAll() throws NodeNotFoundException
    {
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        ArrayList<String> control = testList.convert();
        ArrayList<String> result = testList.removeAll();
        Iterator<String> iter = testList.iterator();
        assertEquals(control, result);
        assertFalse("RemoveAll Failed", iter.hasNext());
    }

    @Test
    public void testSize()
    {
        assertEquals(0, testList.getSize());
        testList.insertFront(FOURTH);
        testList.insertFront(THIRD);
        testList.insertFront(SECOND);
        testList.insertFront(FIRST);
        assertEquals(4, testList.getSize());
    }

    private static <T> boolean compareListToStrings(LinkedList<T> list, T... values)
    {
        int index = 0;
        Iterator<T> iter = list.iterator();
        while (iter.hasNext())
        {
            if (!values[index].equals(iter.next()))
            {
                return false;
            }
            index++;
        }

        return true;
    }

    private static <T> boolean findNode(LinkedList<T> list, LinkedList<T>.Node n)
    {
        Iterator<T> iter = list.iterator();
        while (iter.hasNext())
        {
            if (n.getValue().equals(iter.next()))
            {
                return true;
            }
        }
        return false;
    }

    private static void insertAll(LinkedList<String> list) throws NodeNotFoundException
    {
        list.removeAll();
        list.insertFront(FOURTH);
        list.insertFront(THIRD);
        list.insertFront(SECOND);
        list.insertFront(FIRST);
    }

    private static <T> void removeViaIterator(LinkedList<T> list) throws NodeNotFoundException
    {
        Iterator<T> iter = list.iterator();
        while (iter.hasNext())
        {
            iter.next();
            iter.remove();
        }
    }
}

测试类有12个测试，其中有testIsEmpty和testFind。当我进行测试时，我没有通过这两个测试。由于最后一个断言，我的 testIsEmpty 失败了:

assertTrue("isEmpty Failed after emptying", testList.isEmpty());

由于此断言，testFind 失败:

assertTrue("Find failed", findNode(testList, testList.findNode(SECOND)));

在TestIsEmpty中，我认为我在迭代器类中错误地实现了remove()函数，但我不知道为什么。 testFind 我查看了函数findNode()，我非常确定它没有任何问题。

如果有人可以检查我的代码，那就太好了。

Answer 1

当您在 LinkedList 中定义 iterator() 时，您似乎正在创建一个新的 LinkedList 对象，而不是使用要迭代的列表。因此，当您在removeViaIterator()方法中调用Iterator iter = list.iterator()时，它不会返回任何数据，并且while循环不会在该方法中执行。