Java：链表的findnode()方法和isEmpty()方法
Java: LinkedList findnode() method and isEmpty() method
我有一个实现可迭代接口的链表class，在链表class中我有一个内部节点class。我有另一个运行 JUnit 4 的 TestLinkedList class。测试 class 将检查我在链表 class.
中的所有函数
这是我的 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 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());
}
}
这是我的 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();
}
}
}
测试class有12个测试，其中有testIsEmpty和testFind。
当我 运行 测试时，我没有通过这两个测试。
由于最后一个断言，我没有通过 testIsEmpty：
assertTrue("isEmpty Failed after emptying", testList.isEmpty());
由于此断言，testFind 失败：
assertTrue("Find failed", findNode(testList, testList.findNode(SECOND)));
在TestIsEmpty中，我以为我在迭代器class中实现了remove()函数是错误的，但我不知道为什么。 testFind 我查看了 findNode() 函数，我很确定它没有任何问题。
如果有人能检查我的代码就太好了。
当您在 LinkedList 中定义 iterator() 时，您似乎正在创建一个新的 LinkedList 对象，而不是使用您想要迭代的列表。因此，当您在 removeViaIterator() 方法中调用 Iterator iter = list.iterator() 时，它不会返回任何数据，并且 while 循环不会在该方法中执行。
findNode（实际上是迭代器）有问题
在我打字时...
LinkedList.iterator 每次调用时都会创建一个 new LinkedList，并将 that 传递给 LinkedListIterator构造函数：
return new LinkedListIterator<T>(new LinkedList<T>());
LinkedListIterator 将始终（正确）报告 LinkedList 为空。该行应该改为：
return new LinkedListIterator<T>(this);
isEmpty有问题（也是迭代器）
测试正确 --- 列表不为空。 LinkedListIterator.remove 永远不会删除第一个 Node，因此 TestLinkedList.removeViaIterator 永远不会完全清空列表。
考虑 LinkedListIterator 遍历只有一个 Node 的 LinkedList：current 指向唯一的 Node，并且 previous 指向（默认情况下）到 null。迭代器的next方法调用一次后，current会指向表尾null，而previous会指向唯一的Node ]...现在删除曾经流行的 Node.
已经太晚了
current不应该开始于front，而是处于一些非法的"pre-front"状态；它应该在第一次调用 next 时前进到 front。考虑用存在 "before" 的虚假 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。它应该不 return null, 尤其是当null是一个合法的元素值时[=106] =]
remove 方法应该在两种情况下引发 IllegalStateException：
[...] 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
来自 Iterator interface's docs。您应该（重新）仔细阅读它们，因为很容易编写一个 "Iteratorish" 并且工作得很好，使调试所有 else 成为一场噩梦。
canRemove 字段可以处理所有这些情况。将其初始化为 false。它通过 next 方法设置为 true（即使已经 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;
}
其他观察结果
您的 JavaDocs 通常是完全错误的。例如，他们中的许多人声称用户可以将 Node 插入到列表中，而实际上用户插入的是类型 T 元素 。具有讽刺意味的是，findNode 有相反的问题：声称它 return 是一个元素，而实际上它 return 是 Node。 （在你的测试 完全不同的 findNode 方法 class 中没有帮助。）我不再阅读你的评论，因为它们经常具有误导性。
您的 LinkedList 可以存储 null 个元素。这没关系，如果尴尬。 不 好的是你经常做类似 if (someNode.getValue().equals(someElement)) { ... } 的事情，如果该节点正在存储 null.[=106，它会抛出 NullPointerException =]
findElement 通过 return 找到的元素表示成功，通过 returning null 表示失败。但是null是一个合法的元素值，所以findElement(null)将总是returnnull。这是否意味着您找到了它，或者您没有找到它？考虑抛出 NodeNotFoundException（或 ElementNotFoundException？）来指示失败，就像您在其他地方所做的那样。 （顺便说一句，findElement 与 contains 有何不同？）
您经常在不需要时遍历整个列表...并且为此复制了很多 Iterator 的代码。所以使用Iterator！ （...一旦修复。）
您可以只维护一个 private int size 字段用于 getSize（和 isEmpty），而不是计算列表中的所有元素。
LinkedList.front 应该是 private（包含所有暗示的编辑）。
整个 "Do not add the Node if it already exists in the list." 事情...不是列表通常的行为方式。它更像是一个集合，链表是一种非常低效的集合方式。
Don't Repeat Yourself！计算您从 LinkedList.front 开始并沿着链接的 Node 走下去的地方。为什么不直接调用 findNode 或 contains？计算比较两个 Node 元素的位置，或（略有不同）确定可能为空的 Node 引用是否包含已知元素。用一两个私有方法替换该代码，然后 使用 它们。 （然后该方法将处理我上面提到的 null 元素，因此您不会在代码中到处都是 "if-null-else"。）
我有一个实现可迭代接口的链表class，在链表class中我有一个内部节点class。我有另一个运行 JUnit 4 的 TestLinkedList class。测试 class 将检查我在链表 class.
中的所有函数这是我的 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 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());
}
}
这是我的 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();
}
}
}
测试class有12个测试，其中有testIsEmpty和testFind。 当我 运行 测试时，我没有通过这两个测试。 由于最后一个断言，我没有通过 testIsEmpty：
assertTrue("isEmpty Failed after emptying", testList.isEmpty());
由于此断言，testFind 失败：
assertTrue("Find failed", findNode(testList, testList.findNode(SECOND)));
在TestIsEmpty中，我以为我在迭代器class中实现了remove()函数是错误的，但我不知道为什么。 testFind 我查看了 findNode() 函数，我很确定它没有任何问题。
如果有人能检查我的代码就太好了。
当您在 LinkedList 中定义 iterator() 时，您似乎正在创建一个新的 LinkedList 对象，而不是使用您想要迭代的列表。因此，当您在 removeViaIterator() 方法中调用 Iterator iter = list.iterator() 时，它不会返回任何数据，并且 while 循环不会在该方法中执行。
findNode（实际上是迭代器）有问题
LinkedList.iterator 每次调用时都会创建一个 new LinkedList，并将 that 传递给 LinkedListIterator构造函数：
return new LinkedListIterator<T>(new LinkedList<T>());
LinkedListIterator 将始终（正确）报告 LinkedList 为空。该行应该改为：
return new LinkedListIterator<T>(this);
isEmpty有问题（也是迭代器）
测试正确 --- 列表不为空。 LinkedListIterator.remove 永远不会删除第一个 Node，因此 TestLinkedList.removeViaIterator 永远不会完全清空列表。
考虑 LinkedListIterator 遍历只有一个 Node 的 LinkedList：current 指向唯一的 Node，并且 previous 指向（默认情况下）到 null。迭代器的next方法调用一次后，current会指向表尾null，而previous会指向唯一的Node ]...现在删除曾经流行的 Node.
current不应该开始于front，而是处于一些非法的"pre-front"状态；它应该在第一次调用 next 时前进到 front。考虑用存在 "before" 的虚假 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。它应该不 return null, 尤其是当null是一个合法的元素值时[=106] =]
remove 方法应该在两种情况下引发 IllegalStateException：
[...] if the
nextmethod has not yet been called, or theremovemethod has already been called after the last call to thenextmethod
来自 Iterator interface's docs。您应该（重新）仔细阅读它们，因为很容易编写一个 "Iteratorish" 并且工作得很好，使调试所有 else 成为一场噩梦。
canRemove 字段可以处理所有这些情况。将其初始化为 false。它通过 next 方法设置为 true（即使已经 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;
}
其他观察结果
您的 JavaDocs 通常是完全错误的。例如，他们中的许多人声称用户可以将
Node插入到列表中，而实际上用户插入的是类型T元素 。具有讽刺意味的是，findNode有相反的问题：声称它 return 是一个元素，而实际上它 return 是Node。 （在你的测试 完全不同的findNode方法 class 中没有帮助。）我不再阅读你的评论，因为它们经常具有误导性。您的
LinkedList可以存储null个元素。这没关系，如果尴尬。 不 好的是你经常做类似if (someNode.getValue().equals(someElement)) { ... }的事情，如果该节点正在存储null.[=106，它会抛出NullPointerException=]findElement通过 return 找到的元素表示成功，通过 returningnull表示失败。但是null是一个合法的元素值，所以findElement(null)将总是returnnull。这是否意味着您找到了它，或者您没有找到它？考虑抛出NodeNotFoundException（或ElementNotFoundException？）来指示失败，就像您在其他地方所做的那样。 （顺便说一句，findElement与contains有何不同？）您经常在不需要时遍历整个列表...并且为此复制了很多
Iterator的代码。所以使用Iterator！ （...一旦修复。）您可以只维护一个
private int size字段用于getSize（和isEmpty），而不是计算列表中的所有元素。LinkedList.front应该是private（包含所有暗示的编辑）。整个 "Do not add the Node if it already exists in the list." 事情...不是列表通常的行为方式。它更像是一个集合，链表是一种非常低效的集合方式。
Don't Repeat Yourself！计算您从
LinkedList.front开始并沿着链接的Node走下去的地方。为什么不直接调用findNode或contains？计算比较两个Node元素的位置，或（略有不同）确定可能为空的Node引用是否包含已知元素。用一两个私有方法替换该代码，然后 使用 它们。 （然后该方法将处理我上面提到的null元素，因此您不会在代码中到处都是 "if-null-else"。）