使用我自制的 LinkedList 查找最终的错误

Question

我做了一个单向链表（LinkedList），里面有链表的测试代码class，我把我所有的代码都交给了我的老师，但是他不认可我自制的单向链表，因为他在我的单个 LinkedList 实现中发现了一些错误，因此，我被指派在 JUnit 测试的帮助下查找所有错误。他提到我 "missing" 测试代码中的一些测试用例，这将帮助我改进 LinkedList class 并消除最终的错误。

以下代码是LinkedList class中表示的代码：

/**
 * A singly linked list.
 * 
 * @author 
 * @version
 */
public class LinkedList<T> { 
    private ListElement<T> first;   // First element in list.
    private ListElement<T> last;    // Last element in list.
    private int size;               // Number of elements in list.

    /**
     * A list element.
     */
    private static class ListElement<T> {
        public T data;
        public ListElement<T> next;

        public ListElement(T data) {
            this.data = data;
            this.next = null;
        }
    }

        /**
     * Creates an empty list.
     */
    public LinkedList() {
        first = new ListElement<>(null);
        last = new ListElement<>(null);
        size = 0;
    }

    /**
     * This TEST METHOD returns true if the following invariants hold:
     * <ul>
     *   <li> size equals the number of list elements, </li>
     *   <li> if size == 0, first == null and last == null, </li>
     *   <li> if size > 0, first != null and last != null, </li>
     *   <li> if size == 1, first == last, </li>
     *   <li> last.next == null. </li>
     * </ul>
     */
    public boolean isHealthy() {
        boolean health = true;
        int numberOfListElements = 0;
        ListElement<T> anElement = first;

        for(int i=0;i<size;i++) {
            if(anElement != null) 
            numberOfListElements++;

            anElement = anElement.next;
        }

        if(size != numberOfListElements)
        health = false;

        if((size == 0) && (health != false)) {
            if((first.data == null) && (last.data == null)) {
            }
            else {
                health = false;
            }
        }
        if((size == 1) && (health != false)) {
            if((first == last) && (last == first)) {
            }
            else {
                health = false;
            }
        }
        else if((size > 1) && (health != false)) {
            if((first == null) || (last == null))
            health = false;
        }

        if(last.next != null)
        health = false;

        return health;
    }

    /**
     * Inserts the given element at the beginning of this list.
     */
    public void addFirst(T element) {
        if(size <= 0) {
            first = new ListElement<>(element);
            last = first;
        }
        else {
            ListElement<T> anElement = first;
            first = new ListElement<>(element);
            first.next = anElement;
        }
        size++;
    }

    /**
     * Inserts the given element at the end of this list.
     */
    public void addLast(T element) {
        if(size <= 0) {
            last = new ListElement<>(element);
            first = last;
        }
        else {
            ListElement<T> anElement = new ListElement<>(element);
            last.next = anElement;
            last = anElement;
        }
        size++;
    }

    /**
     * Returns the first element of this list.
     * Returns <code>null</code> if the list is empty.
     */
    public T getFirst() {
        if(size() == 0)
        return null;

        return first.data;
    }

    /**
     * Returns the last element of this list.
     * Returns <code>null</code> if the list is empty.
     */
    public T getLast() {
        if(size == 0)
            return null;

        return last.data;
    }

    /**
     * Returns the element at the specified position in this list.
     * Returns <code>null</code> if <code>index</code> is out of bounds.
     * @param Specify a value lying in the intervall 0-(size-1).
     */
    public T get(int index) {
        ListElement<T> anElement = first;

        if((index < 0) || (index >= size))
            return null;

        else {
            for(int i=0;i<index;i++) {
                anElement = anElement.next;
            }
        }

        return anElement.data;
    }

    /**
     * Removes and returns the first element from this list.
     * Returns <code>null</code> if the list is empty.
     */
    public T removeFirst() {
        ListElement<T> removedElement = first;
        first = first.next;

        if(size>0)
            size--;

        return removedElement.data;
    }

    /**
     * Removes all of the elements from this list.
     */
    public void clear() {
        first = new ListElement<>(null);
        last = new ListElement<>(null);
        last.next = null;
        size = 0;
    }

    /**
     * Returns the number of elements in this list.
     */
    public int size() {
        return size;
    }

    /**
     * Returns <code>true</code> if this list contains no elements.
     */
    public boolean isEmpty() {
        ListElement<T> anElement = first;

        for(int i=0;i<size;i++) {
            if(anElement != null)
            return false;

            anElement = anElement.next;
        }

        return true;
    }

    /**
     * Returns a string representation of this list. The string
     * representation consists of a list of the elements enclosed in
     * square brackets ("[]"). Adjacent elements are separated by the
     * characters ", " (comma and space). Elements are converted to
     * strings by the method toString() inherited from Object.
     */
    public String toString() {
        String representation = "[";
        ListElement<T> anElement = first;

        for(int i=1;i<=size;i++) {
            representation += "" + anElement.data;

            if(i<size) {
                representation += ", ";
                anElement = anElement.next;
            }
        }
        representation += "]";

        return representation;
    }
}

以下代码是目前借助JUnit测试的测试代码：

import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;

/**
 * The test class LinkedListTest.
 *
 * @author  (your name)
 * @version (a version number or a date)
 */
public class LinkedListTest
{
    LinkedList<Object> test;

    /**
     * Default constructor for test class LinkedListTest
     */
    public LinkedListTest()
    {
        test = new LinkedList<>();
    }

    /**
     * Sets up the test fixture.
     *
     * Called before every test case method.
     */
    @Before
    public void setUp()
    {
    }

    /**
     * Tears down the test fixture.
     *
     * Called after every test case method.
     */
    @After
    public void tearDown()
    {
        test = null;
    }

    /**
     * Checks if the method addFirst() works properly. BE AWARE: This test only checks when the input is a type of an String.
     */
    @Test
    public void testAddFirst()
    {
        // When size = 0, row 50
        assertEquals(null, test.getFirst());
        assertEquals(null, test.getLast());
        assertEquals(0, test.size());
        assertTrue(test.isHealthy());

        // When size = 1
        test.addFirst("Hejsan");
        assertEquals("Hejsan", test.getFirst());
        assertEquals(test.getLast(), test.getFirst());
        assertEquals(1, test.size());
        assertTrue(test.isHealthy());

        // When size = 2
        test.addFirst("Svejsan");
        assertEquals("Svejsan", test.getFirst());
        assertEquals("Hejsan", test.getLast());
        assertEquals(2, test.size());
        assertTrue(test.isHealthy());

        //When size = 3
        test.addFirst("Hej då");
        assertEquals("Hej då", test.getFirst());
        assertEquals("Hejsan", test.getLast());
        assertEquals(3, test.size());
        assertTrue(test.isHealthy());
    }

    /**
     * Checks if the method addLast() works properly. BE AWARE: This test only checks when the input is a type of an String.
     */
    @Test
    public void testAddLast()
    {
        // When size = 0
        assertEquals(null, test.getFirst());
        assertEquals(null, test.getLast());
        assertEquals(0, test.size());
        assertTrue(test.isHealthy());

        // When size = 1
        test.addLast("Hejsan");
        assertEquals("Hejsan", test.getFirst());
        assertEquals(test.getLast(), test.getFirst());
        assertEquals(1, test.size());
        assertTrue(test.isHealthy());

        // When size = 2
        test.addLast("Svejsan");
        assertEquals("Hejsan", test.getFirst());
        assertEquals("Svejsan", test.getLast());
        assertEquals(2, test.size());
        assertTrue(test.isHealthy());

        // When size = 3
        test.addLast("Hej då");
        assertEquals("Hejsan", test.getFirst());
        assertEquals("Hej då", test.getLast());
        assertEquals(3, test.size());
        assertTrue(test.isHealthy());
    }

    /**
     * Checks if the method getFirst() works properly. BE AWARE: This test only checks when the input is a type of an String.
     */
    @Test
    public void testGetFirst()
    {
        assertEquals(null, test.getFirst());

        test.addFirst("1");
        test.addLast("2");
        test.addFirst("3");
        test.addFirst("4");
        test.addLast("5");
        test.addLast("6");
        test.addLast("7");
        test.addFirst("8");
        test.addLast("9");
        test.addLast("10");

        assertEquals("8", test.getFirst());
    }

    /**
     * Checks if the method getLast() works properly.
     */
    @Test
    public void testGetLast()
    {
        assertEquals(null, test.getLast());

        test.addLast("1");
        test.addLast("2");
        test.addFirst("4");
        test.addLast("8");
        test.addFirst("16");
        test.addFirst("32");
        test.addLast("64");
        test.addFirst("128");
        test.addFirst("256");
        test.addLast("512");
        test.addFirst("1024");

        assertEquals("512", test.getLast());
    }

    /**
     * Checks if the method get() works properly.
     */
    @Test
    public void testGet()
    {
        assertEquals(null, test.get(-1));

        test.addLast("1");
        test.addLast("2");
        test.addLast("4");
        test.addLast("8");
        test.addLast("16");
        test.addLast("32");
        test.addLast("64");
        test.addLast("128");
        test.addLast("256");
        test.addLast("512");
        test.addLast("1024");
        test.addLast("1");
        test.addLast("2");
        test.addLast("3");
        test.addLast("4");
        test.addLast("5");
        test.addLast("6");
        test.addLast("7");
        test.addLast("8");
        test.addLast("9");
        test.addLast("10");

        assertEquals("1", test.get(0));
        assertEquals("32", test.get(5));
        assertEquals("128", test.get(7));
        assertEquals("1024", test.get(10));
        assertEquals("1", test.get(11));
        assertEquals("10", test.get(20));

        assertEquals(null, test.get(test.size()));
    }

    /**
     * Checks if the method removeFirst() works properly.
     */
    @Test
    public void testRemoveFirst()
    {
        test.removeFirst();
        assertTrue(test.isHealthy());
        assertEquals(0, test.size());

        test.addLast("1");
        test.addLast("2");
        test.addLast("4");
        test.addLast("8");
        test.addLast("16");
        test.addLast("32");
        test.addLast("64");
        test.addLast("128");
        test.addLast("256");
        test.addLast("512");
        test.addLast("1024");

        assertEquals(11, test.size());

        test.removeFirst();
        assertEquals("2", test.getFirst());
        assertEquals(10, test.size());
    }

    /**
     * Checks if the method removeFirst() works properly.
     */
    @Test
    public void testClear()
    {
        assertTrue(test.isEmpty());
        assertTrue(test.isHealthy());
        test.clear();
        assertTrue(test.isHealthy());
        assertTrue(test.isEmpty());

        test.addLast("1");
        test.addLast("2");
        test.addLast("4");
        test.addLast("8");
        test.addLast("16");
        test.addLast("32");
        test.addLast("64");
        test.addLast("128");
        test.addLast("256");
        test.addLast("512");
        test.addLast("1024");

        assertEquals(11, test.size());
        assertFalse(test.isEmpty());
        assertTrue(test.isHealthy());

        test.clear();
        assertTrue(test.isEmpty());
        assertEquals(0, test.size());
        assertTrue(test.isHealthy());
    }

    /**
     * Checks if the method size() works properly.
     */
    @Test
    public void testSize()
    {
        assertEquals(0, test.size());
        assertTrue(test.isEmpty());
        assertTrue(test.isHealthy());

        test.addLast("1");
        test.addLast("2");
        test.addLast("4");
        test.addLast("8");

        assertEquals(4, test.size());
        assertFalse(test.isEmpty());
        assertTrue(test.isHealthy());
    }

    /**
     * Checks if the method isEmpty() works properly.
     */
    @Test
    public void testIsEmpty()
    {
        assertTrue(test.isEmpty());
        assertTrue(test.isHealthy());
        assertEquals(0, test.size());

        test.addLast("1");
        test.addLast("2");
        test.addLast("3");
        test.addLast("4");

        assertFalse(test.isEmpty());
        assertTrue(test.isHealthy());
        assertEquals(4, test.size());

        test.clear();

        assertTrue(test.isEmpty());
        assertTrue(test.isHealthy());
        assertEquals(0, test.size());
    }

    /**
     * Checks if the method toString() works properly.
     */
    @Test
    public void testToString()
    {
        assertEquals("[]", test.toString());

        test.addFirst("1");
        test.addLast("2");
        test.addFirst("3");
        test.addFirst("4");
        test.addLast("5");

        assertTrue(test.isHealthy());
        assertEquals("[4, 3, 1, 2, 5]", test.toString());

        test.clear();

        assertTrue(test.isHealthy());
        assertEquals("[]", test.toString());
    }
}

早些时候我错过了一个测试用例，当链表的大小为零时调用 removeFirst() 方法时，不应更改大小并且该方法将 return null，但是大小只下降到-1、-2 等等。但是正如您所看到的，这已经是固定的。但就在那次发现之后，我在发现代码中的其他潜在错误时遇到了问题：/

但是你能在我的代码中看到其他潜在的错误吗？您能否提供一些线索，告诉我应该在测试代码中的哪个位置查看或类似的东西，以便我至少尝试自己思考？

最后，我也会得到一些关于如何编写好的测试代码的建议，也许根据您在借助测试代码或类似的帮助实现数据 classes 时可能拥有的一些规则。

感谢您的快速答复！

提前致谢！

/糊涂人:D

Answer 1

嗯，举个例子：

testGetFirst：它不仅应该检查列表是否为空和列表是否包含很多项，还应该检查列表是否只包含一个项。这同样适用于所有操作：我们通常要测试的 "fringe cases" 是：零项，一项，许多项。

testRemoveFirst：根据您的文档，当列表为空时删除第一个元素应该 return null，因此您应该断言 null 实际上是 returned.

testRemoveFirst：当列表包含很多项目时应该执行检查，当列表只包含一个项目时也应该执行检查。

您的列表不应该包含 removeLast 操作吗？

使用我自制的 LinkedList 查找最终的错误

Finding eventual bugs with my homemade LinkedList

java

debugging

junit

singly-linked-list