我有一个实现可迭代接口(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()，我非常确定它没有任何问题。
如果有人可以检查我的代码，那就太好了。
最佳答案
当您在 LinkedList 中定义 iterator() 时，您似乎正在创建一个新的 LinkedList 对象，而不是使用要迭代的列表。因此，当您在removeViaIterator()方法中调用Iterator iter = list.iterator()时，它不会返回任何数据，并且while循环不会在该方法中执行。
关于Java:LinkedList findnode() 方法和 isEmpty() 方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30836143/