Java: LinkedList findnode() method and isEmpty() method

Question

I have a LinkedList class that implements iterable interface, in the LinkedList class i have an inner node class. I have another TestLinkedList class that runs JUnit 4. The test class will check all of my functions in the linkedlist class.

Here is my 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>());
    }
}

This is my LinkedListIterator class:

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());
    }
}

Here is my TestLinkedList class:

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();
        }
    }
}

the test class has 12 tests, and among them are the testIsEmpty and testFind. When i ran the test, I failed these two tests. i failed the testIsEmpty because of the last assert:

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

The testFind failed because of this assert:

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

in the TestIsEmpty, I was thinking that I implemented the remove() function in the iterator class wrong, but I had no idea why. The testFind I looked at the function findNode() and I was pretty sure that there was nothing wrong with it.

It would be great if someone can check my code.

Answer 1

Problems with findNode (actually, the iterator)

Sambaran spotted this one while I was typing...

LinkedList.iterator creates a new LinkedList every time it's called, and passes that to the LinkedListIterator constructor:

return new LinkedListIterator<T>(new LinkedList<T>());

The LinkedListIterator will always report (correctly) that the LinkedList is empty. That line should instead be:

return new LinkedListIterator<T>(this);

Problems with isEmpty (also the iterator)

The test is correct --- the list is not empty. LinkedListIterator.remove will never remove the first Node, so TestLinkedList.removeViaIterator will never completely empty a list.

Consider a LinkedListIterator traversing a LinkedList of only one Node: current points to the one and only Node, and previous points (by default) to null. After the iterator's next method is called once, current will point to the end-of-list null, while previous will point to the one and only Node... and it's now too late to remove the once-current Node.

current should not start at front, but in some illegal "pre-front" state; it should advance to front the first time next is called. Consider initializing it with a bogus Node that exists "before" the real list:

public class LinkedListIterator<T> implements Iterator<T>
{
    final LinkedList<T> list;
    LinkedList<T>.Node previous;
    LinkedList<T>.Node current;
    boolean canRemove;

    public LinkedListIterator(LinkedList<T> list) {
        // Required by remove.
        this.list = list;
        // Required by remove.
        this.canRemove = false;
        // No change, just making it explicit.
        this.previous = null;
        // Bogus "pre-front" Node, for before first call to next.
        this.current = this.list.new Node(this.list.front, null);
    }

    // etc...

}

I added the list field so remove can handle the special case of removing front --- it has to update LinkedList.front instead of previous.next.

The canRemove is there to solve several other problems...

Problems with the Iterator contract

Your LinkedListIterator.next method should throw a NoSuchElementException when there is no next element. It should not return null, especially when null is a legal element value.

The remove method should raise an IllegalStateException in two situations:

[...] if the next method has not yet been called, or the remove method has already been called after the last call to the next method

That's from the Iterator interface's docs. You should (re-)read them carefully, because it's very easy to write an "Iteratorish" that works just well enough to make debugging everything else a nightmare.

The canRemove field can handle all of these cases. Initialize it to false. It is set to true by the next method (even if already true --- next doesn't care), and set to false again by the remove method. The only code that reads this is the remove method:

@Override
public void remove() {
    if (!this.canRemove) {
        throw new IllegalStateException("Helpful error message.");
    }
    // Remove current Node.
    this.canRemove = false;
    return;
}

Other Observations

1. Your JavaDocs are often outright wrong. For example, many of them claim the user can insert a Node into the list, when really the user inserts a type-T element. findNode, ironically, has the opposite problem: claiming that it returns an element, when it really returns a Node. (It doesn't help that there's a completely different findNode method in your test class.) I stopped reading your comments because they were so often misleading.

2. Your LinkedList can store null elements. This is OK, if awkward. What's not OK is that you often do something like if (someNode.getValue().equals(someElement)) { ... }, which will throw a NullPointerException if that node is storing a null.

3. findElement indicates success by returning the element found, and failure by returning null. But null is a legal element value, so findElement(null) will always return null. Does that mean you found it, or you didn't? Consider throwing a NodeNotFoundException (or ElementNotFoundException?) to indicate failure, like you do elsewhere. (As an aside, how is findElement different from contains?)

4. You often iterate through the whole list when you don't have to... and you duplicate much of the Iterator's code to do so. So use the Iterator! (...once it's fixed.)

5. You can just maintain a private int size field for use with getSize (and isEmpty), instead of counting all the elements in your list.

6. LinkedList.front should be private (with all the edits that implies).

7. That whole "Do not add the Node if it already exists in the list." thing is... not how lists usually behave. It's much more like a set, and a linked list is a terribly inefficient way to make a set.

8. Don't Repeat Yourself! Count the places you start at LinkedList.front and walk down the linked Nodes. Why not just call findNode or contains? Count the places you compare two Node elements, or (slightly different) determine if a could-be-null Node reference contains a known element. Replace that code with a private method or two, then use them. (That method would then handle the null elements I mentioned above, so you wouldn't have "if-null-else" sprinkled all over your code.)

Answer 2

It seems when you are defining the iterator() in LinkedList you are creating a new LinkedList object instead of using the list you want to iterate on. So when you call Iterator iter = list.iterator() in removeViaIterator() method it is not returning any data and the while loop is not getting executed in the method.