Java: LinkedList метод findnode() и метод isEmpty()

Question

У меня есть класс LinkedList, который реализует итеративный интерфейс, в классе LinkedList у меня есть класс внутреннего узла. У меня есть еще один класс TestLinkedList, который запускает JUnit 4. Тест-класс проверяет все мои функции в классе связанных списков.

Вот мой 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, я думал, что я реализовал функцию удаления() в класс итератора неправильный, но я понятия не имел, почему. TestFind я посмотрел на функцию findNode(), и я был уверен, что в этом нет ничего плохого.

Было бы здорово, если бы кто-то мог проверить мой код.

Answer 1

Кажется, что когда вы определяете итератор() в LinkedList, вы создаете новый объект LinkedList вместо того, чтобы использовать список, в который хотите выполнить итерацию. Поэтому, когда вы вызываете Iterator iter = list.iterator() в методе removeViaIterator(), он не возвращает никаких данных, и цикл while не выполняется в методе.

Answer 2

Проблемы с findNode (фактически итератора)

Sambaran spotted this one в то время как я печатал ...

LinkedList.iteratorсоздает новыйLinkedList каждый раз, когда она называется, и передает что к LinkedListIterator конструктор:

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

LinkedListIterator всегда будет сообщать (правильно), что LinkedList пуст. Эта линия должна быть вместо этого:

return new LinkedListIterator<T>(this); 

Проблемы с isEmpty (также Итератор)

тест является правильным --- список не пустым. LinkedListIterator.remove никогда не удалит первый Node, поэтому TestLinkedList.removeViaIterator никогда не будет полностью пустым списком.

LinkedListIterator Рассмотрим обходе LinkedList только одного Node: current указывает на один и только Node и previous точек (по умолчанию) на null. После того, как метод итератора next вызывается один раз, current будет указывать на конец списка null, а previous укажет на один и только Node ... и теперь уже слишком поздно снимать один раз ток Node.

current не следует начинать в front, но в какой-то нелегальный "предварительно front" состояние; он должен перейти на front в первый раз, когда вызывается next. Рассмотрим его инициализации с поддельной Node, что существует «до» реального списка:

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... 

} 

Я добавил list поле так remove может обрабатывать особый случай удаления front --- он должен обновить LinkedList.front вместо previous.next.

canRemove есть решить ряд других проблем ...

Проблемы с Iterator контракта

Ваш метод LinkedListIterator.next должен бросить NoSuchElementException, когда нет следующего элемента. Он должен не возвращение null, особенно, когда null является значением юридического элемента.

Метод remove должен поднять IllegalStateException в двух ситуациях:

[...] если метод next еще не был назван, или метод remove уже был вызван после последнего вызова к next

Это от Iterator interface's docs. Вы должны (повторно) внимательно их прочитать, потому что очень легко написать «Итератор», который работает достаточно хорошо, чтобы отлаживать все, что угодно, но кошмар.

Поле canRemove может обрабатывать все эти случаи. Инициализируйте его до false. Он установлен в true методом next (даже если уже true --- next не имеет значения), и снова установите false методом remove. Единственный код, который читает это является remove метод:

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

Другие наблюдения

1. Ваши JavaDocs часто прямо не так.Например, многие из них утверждают, что пользователь может вставить в список Node, когда пользователь вставляет тип Tэлемент. findNode, по иронии судьбы, имеет противоположную проблему: утверждая, что он возвращает элемент, когда он действительно возвращает Node. (Это не помогает, что есть совершенно другой методfindNode в вашем тестовом классе.) Я перестала читать ваши комментарии, потому что они так часто вводили в заблуждение.

2. LinkedList может хранить null элементы. Это нормально, если неловко. Что такое не ОК, так это то, что вы часто делаете что-то вроде if (someNode.getValue().equals(someElement)) { ... }, которое выкинет NullPointerException, если этот узел хранит null.

3. findElement указывает на успех, возвращая найденный элемент, и сбой, возвращая null. Но null является значением юридического элемента, поэтому findElement(null) будет всегда возвращение null. Значит ли это, что вы его нашли, или нет? Подумайте о том, чтобы указать NodeNotFoundException (или ElementNotFoundException?), Чтобы указать отказ, как и в других местах. (Кстати, как это findElement отличается от contains?)

4. Вы часто перебирать весь список, когда вы не должны ... и дублировать много коды Iterator «s, чтобы сделать это. Поэтому используйте Iterator! (... как только это исправлено.)

5. Вы можете просто сохранить private int size поле для использования с getSize (и isEmpty), вместо того чтобы считать все элементы в списке.

6. LinkedList.front должно быть private (со всеми внесенными изменениями).

7. Все это «Не добавляйте узел, если он уже существует в списке». вещь ... не так, как обычно ведут себя списки. Это больше похоже на набор, и связанный список - это ужасно неэффективный способ создания набора.

8. Don't Repeat Yourself! Подсчитайте места, где вы начинаете LinkedList.front, и сходите по связанным Node. Почему бы просто не позвонить findNode или contains? Подсчитайте места, которые вы сравниваете, два элемента Node, или (немного другое), определите, содержит ли ссылка can-be-null Node известный элемент. Замените этот код частным методом или двумя, затем используйте им. (Этот метод будет затем обрабатывать null элементов я уже упоминал выше, так что вы не имели бы «если-нуль-то еще» посыпает весь код.)