user18047251
user18047251

Reputation:

LinkedList junit test

Linked List junit testclass

I dont understand have i should write the testisEmptyIsTrueWhenAllElementsHaveBeenRemovedByRemoveFirst() test in the test class. I need help with the test that. I have wrote my Linked list class and done all but one test in the junit test class.

TODO: The test i in the junit class with header testisEmptyIsTrueWhenAllElementsHaveBeenRemovedByRemoveFirst().

Linked list class:

import java.util.NoSuchElementException;

/**
 * A singly linked list.
 * 
 */
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() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

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

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

    /**
     * @return The head of the list.
     * @throws NoSuchElementException if the list is empty.
     */
    public T getFirst() {
        if (this.first != null){
            return this.first.data;
        }
        else{
            throw new NoSuchElementException();
        }
    }

    /**
     * @return The tail of the list.
     * @throws NoSuchElementException if the list is empty.
     */
    public T getLast() {
       if(this.last != null){
           return this.last.data;
       }
       else{
           throw new NoSuchElementException();
       }
    }

    /**
     * Returns an element from a specified index.
     *
     * @param index A list index.
     * @return The element at the specified index.
     * @throws IndexOutOfBoundsException if the index is out of bounds.
     */
    public T get(int index) {
        if(index < 0|| index >= this.size){
            throw new IndexOutOfBoundsException();
        }
        else{
            ListElement<T>element = this.first;
            for(int i = 0; i < index; i++){
                element = element.next;
            }
                return element.data;
            }
    }

    /**
     * Removes the first element from the list.
     *
     * @return The removed element.
     * @throws NoSuchElementException if the list is empty.
     */
    public T removeFirst() {
        if(this.first != null || this.size != 0){
            ListElement<T> list = this.first;
            this.first = first.next;
            size --;
        return list.data;
        }
        else{
            throw new NoSuchElementException();
        }
    }

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

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

    /**
     * Note that by definition, the list is empty if both first and last
     * are null, regardless of what value the size field holds (it should
     * be 0, otherwise something is wrong).
     *
     * @return <code>true</code> if this list contains no elements.
     */
    public boolean isEmpty() {
        return first == null && last == null;
    }

    /**
     * Creates 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.
     *
     * Examples:
     *  "[1, 4, 2, 3, 44]"
     *  "[]"
     *
     * @return A string representing the list.
     */
    public String toString() {
        ListElement<T> listofelements = this.first;
        String returnString = "[";
        while(listofelements != null) {
            returnString += listofelements.data;
            if(listofelements.next != null){
                returnString += ", ";
            }
            listofelements = listofelements.next;
        }
        returnString += "]";
        return returnString;
    }
}

Test class

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

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * Test class for LinkedList
 *
 * The following invariants are checked for several different states and for
 * each of the methods that mutate the list.
 *
 *   1. size equals the number of list elements,
 *   2. if size == 0, first == null and last == null,
 *   3. if size > 0, first != null and last != null,
 *   4. if size == 1, first == last,
 *
 *   The 5th invariant is not tested, but keep it in mind ...
 *   5. last.next == null.
 */
public class LinkedListTest {

    /* A sequence of integers */
    private int[] elements;

    /* An empty linked list */
    private LinkedList<Integer> list;

    @Before
    public void setUp() {
        list = new LinkedList<Integer>();
        elements = new int[]{-919,  388,   67, -248, -309, -725,  904,   53,
                               90, -469, -559,  256,  612,  366, -412, -221,
                              347, -921, -978,  324, -858,  480, -443,  891,
                              329,   -5,  878, -538,  445, -366,  760,   52};
    }

    /**
     * Tests for size()
     */

    /**
     * Assert that the size of an empty list is exactly 0. TESSST
     */
    @Test
    public void sizeIsZeroWhenListIsEmpty() {
        LinkedList <String> list = new LinkedList<>();
        int size = list.size();
        assertThat(size,equalTo(0));
        assertTrue(list.isEmpty());
    }

    /**
     * Tests for addFirst(T)
     */

    /**
     * Assert that adding an element to the beginning
     * of the list increments the size of the list by 1.
     */
    @Test
    public void addFirstIncrementsSizeByOne() {
        for (int i = 0; i < elements.length; i++) {
            // Act
            list.addFirst(elements[i]);
            // Assert
            assertThat(list.size(), equalTo(i + 1));
        }
    }

    /**
     * Tests for addLast(T)
     */

    /**
     * Assert that adding an element to the end
     * of the list increments the size of the list by 1. TESSST
     */
  @Test public void addLastIncrementsSizeByOne() {
       for(int i = 0; i < elements.length; i ++){
           list.addLast(elements[i]);
           assertThat(list.size(), equalTo(i+1));
       }
    }

    /**
     * Tests for removeFirst()
     */

    /**
     * Assert that removing the first element of an empty
     * list throws an exception.
     */
    @Test (expected=NoSuchElementException.class)
    public void removeFirstThrowsExceptionWhenListIsEmpty() {

        list.removeFirst();
    }

    /**
     * Assert that removing the first element of a list
     * decrements the size by 1.
     */
    @Test
    public void removeFirstDecrementsSizeByOne() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        for (int i = 0; i < elements.length; i++) {
            // Act
            list.removeFirst();
            // Assert
            assertThat(list.size(), equalTo(elements.length - i - 1));
        }
    }

     /**
     * Assert that the correct element is returned when
     * removing the first element.
     */
    @Test
    public void removeFirstReturnsCorrectElement() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        for (int i = 0; i < elements.length; i++) {
            // Act
            int value = list.removeFirst();
            // Assert
            assertThat(value, equalTo(elements[i]));
        }
    }

    /**
     * Tests for getFirst()
     */

    /**
     * Assert that getting the first element of an empty
     * list throws an exception. TESTTTT
     */
    @Test (expected=NoSuchElementException.class)
    public void getFirstThrowsExceptionWhenListIsEmpty() {
        list.getFirst();
    }


    /**
     * Assert that getting the first element of a list
     * returns the correct element after adding an element
     * to the beginning of the list.
     */
    @Test
    public void getFirstIsCorrectAfterAddFirst() {
        for (int element : elements) {
            // Arrange
            list.addFirst(element);
            // Act, Assert
            assertThat(list.getFirst(), equalTo(element));
        }
    }

    /**
     * Assert that getting the first element of a list
     * returns the correct element after adding an element
     * to the end of the list.
     */
    @Test
    public void getFirstIsCorrectAfterAddLast() {
        for (int element : elements) {
            // Arrange
            list.addLast(element);
            // Act, Assert
            assertThat(list.getFirst(), equalTo(elements[0]));
        }
    }

    /**
     * Tests for getLast()
     */

    /**
     * Assert that getting the last element of an empty
     * list throws an exception.
     */
    @Test (expected=NoSuchElementException.class)
    public void getLastThrowsExceptionWhenListIsEmpty() {
        // Act
        list.getLast();
    }

    /**
     * Assert that getting the last element of a list
     * returns the correct element after adding an element
     * to the beginning of the list.
     */
    @Test
    public void getLastIsCorrectAfterAddFirst() {
        for (int element : elements) {
            // Arrange
            list.addFirst(element);
            // Act, Assert
            assertThat(list.getLast(), equalTo(elements[0]));
        }
    }

    /**
     * Assert that getting the last element of a list
     * returns the correct element after adding an element
     * to the end of the list.
     */
    @Test
    public void getLastIsCorrectAfterAddLast() {
        for (int element : elements) {
            // Arrange
            list.addLast(element);
            // Act, Assert
            assertThat(list.getLast(), equalTo(element));
        }
    }

    /**
     * Test for get(int)
     */

    /**
     * Assert that getting an element of an empty list
     * throws an exception.
     */
    @Test (expected=IndexOutOfBoundsException.class)
    public void getThrowsExceptionWhenListIsEmpty() {
        // Act
        list.get(0);
    }

    /**
     * Assert that getting any element of a list
     * returns the correct element after an element
     * is added to the end of the list.
     */
    @Test
    public void getIsCorrectAfterAddLast() {
        for (int i = 0; i < elements.length; i++) {
            // Arrange
            list.addLast(elements[i]);
            // Act, Assert
            for (int j = 0; j < i + 1; j++) {
                assertThat(list.get(j), equalTo(elements[j]));
            }
        }
    }

    /**
     * Assert that getting any element of a list
     * returns the correct element after an element
     * is added to the beginning of the list.
     */
    @Test
    public void getIsCorrectAfterAddFirst() {
        for (int i = 0; i < elements.length; i++) {
            // Arrange
            list.addFirst(elements[i]);
            // Act, Assert
            for (int j = 0; j < i + 1; j++) {
                assertThat(list.get(j), equalTo(elements[i-j]));
            }
        }
    }

    /**
     * Assert that getting the non existent element
     * with index -1 throws an exception.
     */
    @Test (expected=IndexOutOfBoundsException.class)
    public void getThrowsExceptionWhenIndexIsMinusOne() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        // Act
        list.get(-1);
    }

    /**
     * Assert that getting the non existent element
     * with index equal to the length of the list
     * throws an exception.
     */
    @Test (expected=IndexOutOfBoundsException.class)
    public void getThrowsExceptionWhenIndexIsLength() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        list.get(elements.length);
    }

    /**
     * Tests for isEmpty
     */

    /**
     * Assert that isEmpty returns true for
     * an empty list.
     */
    @Test
    public void isEmptyIsTrueForEmptyList() {
        // Act, Assert
        assertTrue(list.isEmpty());
    }

    /**
     * Assert that isEmpty returns false
     * after adding an element to the beginning
     * of the list.
     */
    @Test
    public void isEmptyIsFalseAfterAddFirst() {
        // Arrange
        list.addFirst(elements[0]);
        // Act, Assert
        assertFalse(list.isEmpty());
    }

    /**
     * Assert that isEmpty returns false
     * after adding an element to the end
     * of the list.
     */
    @Test
    public void isEmptyIsFalseAfterAddLast() {
        // Arrange
        list.addLast(elements[0]);
        // Act, Assert
        assertFalse(list.isEmpty());
    }

    /**
     * Assert that isEmpty returns true
     * after all elements of a non empty list
     * has been removed by the removeFirst method. TESTS
     */
    @Test
    public void isEmptyIsTrueWhenAllElementsHaveBeenRemovedByRemoveFirst(){
        //TODO
    }


    /**
     * Assert that isEmpty returns true
     * after all elements of a non empty list
     * has been removed by the clear method.
     */
    @Test
    public void isEmptyIsTrueWhenAllElementsHasBeenRemovedByClear() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        // Act
        list.clear();
        // Assert
        assertTrue(list.isEmpty());
    }

    /**
     * Tests for clear()
     */

    /**
     * Assert that clearing a non empty list sets the
     * size of the list to 0. TESTTTTTT
     */
    @Test
    public void clearSetsSizeToZero() {
    for(int element : elements){
        list.addLast(element);
    }
    list.clear();
    assertThat(list.size(), equalTo(0));
    assertTrue(list.isEmpty());
    }

    /**
     * Assert that clearing an empty list
     * has no effect.
     */
    @Test
    public void clearDoesNothingWhenListIsEmpty() {
        // Act
        list.clear();
        // Assert
        assertThat(list.size(), equalTo(0));
        assertTrue(list.isEmpty());
    }

    /**
     * Tests for toString()
     */

    /**
     * Assert that toString returns the correct
     * representation on an empty list.
     */
    @Test
    public void toStringIsCorrectWhenListIsEmpty() {
        // Act, Assert
        assertThat(list.toString(), equalTo("[]"));
    }

    /**
     * Assert that toString returns the correct
     * representation on a non empty list.
     */
    @Test
    public void toStringIsCorrectWhenListIsNonEmpty() {
        // Arrange
        for (int element : elements) {
            list.addLast(element);
        }
        // Act, Assert
        assertThat(list.toString(),
            equalTo(Arrays.toString(elements)));
    }

    /**
     * These tests only tests the speed of your implementation.
     * For a correct implementation they should be
     * passed with good margin on even to slowest of computers.
     */

    /**
     * Assert that the addFirst method runs reasonably fast.
     */
    @Test(timeout=100)
    public void addFirstTenThousandTimesIsReasonablyFast() {
        for (int i = 0; i < 10000; i++) {
            // Act
            list.addFirst(i);
        }
    }

    /**
     * Assert that the addLast method runs reasonably fast.
     */
    @Test(timeout=100)
    public void addLastTenThousandTimesIsReasonablyFast() {
        for (int i = 0; i < 10000; i++) {
            // Act
            list.addLast(i);
        }
    }

}

Upvotes: 1

Views: 1515

Answers (1)

Alexey Krasnopolsky
Alexey Krasnopolsky

Reputation: 51

After adding some elements to your list you have a size. Use it in a loop to remove elements with removeFirst method as many times as an amount of added elements, and then assert that list is empty

upd

In the end your test will look this, for example:

for (int element : elements) { 
  list.addLast(element);
}

int b = list.size();
for (int i = 0; i < b; i++) { 
  list.removeFirst(); 
} 
assertTrue(list.isEmpty());

Upvotes: 1

Related Questions