title: Java: LinkedList findnode() method and isEmpty() method
body: <p>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.</p>
  
  <p>Here is my LinkedListClass:</p>
  
  <pre><code>public class LinkedList&lt;T&gt; implements Iterable&lt;T&gt;
  {
      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 &amp;&amp; !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 &amp;&amp; !current.getValue().equals(currentElement))
          {
              current = current.getNext();
          }
          if (current == null)
          {
              throw new NodeNotFoundException("" + currentElement);
          }
          else
          {
              while(check != null &amp;&amp; !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 &amp;&amp; !current.getValue().equals(currentElement))
          {
              previous = current;
              current = current.getNext();
          }
          if (current == null)
          {
              throw new NodeNotFoundException("" + currentElement);
          }
          else
          {
              while (check != null &amp;&amp; !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 &amp;&amp; !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&lt;T&gt; removeAll() throws NodeNotFoundException
      {
          Node current = front;
          ArrayList&lt;T&gt; arrayList = new ArrayList&lt;T&gt;();
  
          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 &amp;&amp; !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 &amp;&amp; !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&lt;T&gt; convert()
      {
          Node current = front;
          ArrayList&lt;T&gt; arrayList = new ArrayList&lt;T&gt;();
  
          while (current != null)
          {
              arrayList.add(current.getValue());
              current = current.getNext();
          }
          return arrayList;
      }
  
      /**
       * Return the linked list as a string in the format element -&gt; element -&gt; element. For example
       * "first -&gt; second -&gt; 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() + "-&gt;";
              current = current.getNext();
          }
          s += "" + current.getValue();
          return s;
      }
      /*
       * (non-Javadoc)
       * 
       * @see java.lang.Iterable#iterator()
       */
      @Override
      public Iterator&lt;T&gt; iterator()
      {
          return new LinkedListIterator&lt;T&gt;(new LinkedList&lt;T&gt;());
      }
  }
  </code></pre>
  
  <p>This is my LinkedListIterator class:</p>
  
  <pre><code>public class  LinkedListIterator&lt;T&gt; implements Iterator&lt;T&gt;
  {
      LinkedList&lt;T&gt;.Node previous;
      LinkedList&lt;T&gt;.Node current;
      public LinkedListIterator(LinkedList&lt;T&gt; 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());
      }
  }
  </code></pre>
  
  <p>Here is my TestLinkedList class:</p>
  
  <pre><code>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-&gt;Second-&gt;Third-&gt;Fourth";
      private static String TEST_ARRAY = "[First,Second,Third,Fourth]";
      private LinkedList&lt;String&gt; testList;
  
      @Before
      public void setUp() throws NodeNotFoundException
      {
          testList = new LinkedList&lt;String&gt;();
      }
  
      @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&lt;String&gt; 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&lt;String&gt; control = testList.convert();
          ArrayList&lt;String&gt; result = testList.removeAll();
          Iterator&lt;String&gt; 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 &lt;T&gt; boolean compareListToStrings(LinkedList&lt;T&gt; list, T... values)
      {
          int index = 0;
          Iterator&lt;T&gt; iter = list.iterator();
          while (iter.hasNext())
          {
              if (!values[index].equals(iter.next()))
              {
                  return false;
              }
              index++;
          }
  
          return true;
      }
  
      private static &lt;T&gt; boolean findNode(LinkedList&lt;T&gt; list, LinkedList&lt;T&gt;.Node n)
      {
          Iterator&lt;T&gt; iter = list.iterator();
          while (iter.hasNext())
          {
              if (n.getValue().equals(iter.next()))
              {
                  return true;
              }
          }
          return false;
      }
  
      private static void insertAll(LinkedList&lt;String&gt; list) throws NodeNotFoundException
      {
          list.removeAll();
          list.insertFront(FOURTH);
          list.insertFront(THIRD);
          list.insertFront(SECOND);
          list.insertFront(FIRST);
      }
  
      private static &lt;T&gt; void removeViaIterator(LinkedList&lt;T&gt; list) throws NodeNotFoundException
      {
          Iterator&lt;T&gt; iter = list.iterator();
          while (iter.hasNext())
          {
              iter.next();
              iter.remove();
          }
      }
  }
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>assertTrue("isEmpty Failed after emptying", testList.isEmpty());
  </code></pre>
  
  <p>The testFind failed because of this assert:</p>
  
  <pre><code>assertTrue("Find failed", findNode(testList, testList.findNode(SECOND)));
  </code></pre>
  
  <p>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.</p>
  
  <p>It would be great if someone can check my code.</p>