Problem with LinkedList extra space is added when Assert. assertEquals()

I have my own LinkedList implementation, I'm trying to test it using junit, but I get an error due to the fact that an extra space is added:

java.lang.AssertionError:
Expected :impl.LinkedListOwnImpl<B; A; >*в этом месте пробел* 
Actual :impl.LinkedListOwnImpl<B; A; >

I had the same problem with my ArrayList implementation, the problem was that I forgot to redefine equals. But in LinkedList and the internal Node class, the equals methods are overridden. Everything seems to be correct. Am I missing something? What could be the problem?

public class LinkedListOwnImpl<T> implements LinkedListOwn<T> {


    private Node<T> firstNode;
    private Node<T> lastNode;
    private int size;

    public LinkedListOwnImpl() {
        lastNode = new Node<>(null, firstNode, null);
        firstNode = new Node<>(null, null, lastNode);
    }

    @Override
    public void addFirst(T element) {
        Node<T> newNext = firstNode;
        newNext.value = element;
        firstNode = new Node<>(null, null, newNext);
        newNext.prev = firstNode;
        while (getNextNode(newNext) != lastNode) {
            newNext = getNextNode(newNext);
        }
        lastNode.prev = newNext;
        size++;
    }



    @Override
    public void addLast(T element) {
        Node<T> newPrev = lastNode;
        newPrev.value = element;
        lastNode = new Node<>(null, newPrev, null);
        newPrev.next = lastNode;
        size++;
    }

   private Node<T> getNextNode(Node<T> element) {
        return element.next;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof LinkedListOwnImpl)) return false;
        LinkedListOwnImpl<?> that = (LinkedListOwnImpl<?>) o;
        return size == that.size &&
                Objects.equals(firstNode, that.firstNode) &&
                Objects.equals(lastNode, that.lastNode);
    }

    @Override
    public int hashCode() {
        return Objects.hash(firstNode, lastNode, size);
    }

    @Override
    public String toString() {
        String str = "";
        Node<T> node = firstNode;
        while (getNextNode(node) != lastNode) {
            str += getNextNode(node).value.toString() + "; ";
            node = getNextNode(node);
        }
        return str;
    }

    private static class Node<T> {
        private T value;
        private Node<T> prev;
        private Node<T> next;

        Node(T value, Node<T> prev, Node<T> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(value, node.value) &&
                    Objects.equals(prev, node.prev) &&
                    Objects.equals(next, node.next);
        }

        @Override
        public int hashCode() {
            return Objects.hash(value, prev, next);
        }
    }
}

Test:

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

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.is;

public class LinkedListOwnImplTest {

    LinkedListOwn<String> linkedListOwn;

    @Before
    public void setUp() {
        linkedListOwn = new LinkedListOwnImpl<>();
        linkedListOwn.addLast("A");
    }

    @Test
    public void addFirst() {
        LinkedListOwn<String> expected = new LinkedListOwnImpl<>();
        expected.addLast("B");
        expected.addLast("A");

        linkedListOwn.addFirst("B");

        Assert.assertEquals(expected, linkedListOwn);
    }
Author: Artem, 2019-05-27

1 answers

Your problem is not an extra space, because the unit test does not compare string representations of objects at all.

To compare 2 lists, you need to go from the beginning to the end of both lists at the same time and compare the values of the elements. Your current algorithm is recursive and results in a stack overflow.

I have slightly corrected your code (please note, I am not a Java professional, so there may be errors here):

public class LinkedListOwnImpl<T> implements LinkedListOwn<T> {
    private Node<T> firstNode;
    private Node<T> lastNode;
    private int size;

    public LinkedListOwnImpl() {
    }

    @Override
    public void addFirst(T element) {
        Node<T> newNode = new Node<>(element, null, firstNode);
        if (firstNode != null) {
            firstNode.prev = newNode;
        }
        if (lastNode == null) {
            lastNode = newNode;
        }
        firstNode = newNode;
        size++;
    }

    @Override
    public void addLast(T element) {
        Node<T> newNode = new Node<>(element, lastNode, null);
        if (lastNode != null) {
            lastNode.next = newNode;
        }
        if (firstNode == null) {
            firstNode = newNode;
        }
        lastNode = newNode;
        size++;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof LinkedListOwnImpl)) return false;
        LinkedListOwnImpl<?> that = (LinkedListOwnImpl<?>) o;
        if( size != that.size) {
            return false;
        }

        Node<T> node = firstNode;
        Node<?> nodeThat = that.firstNode;

        while (node != null) {
            if (!Objects.equals(node, nodeThat)) {
               return false;
            }
            node = node.next;
            nodeThat = nodeThat.next;
        }
        return true;
    }

    @Override
    public int hashCode() {
        return Objects.hash(firstNode, lastNode, size);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node<T> node = firstNode;
        while (node != null) {
            builder.append(node.value.toString());
            builder.append("; ");
            node = node.next;
        }
        return builder.toString();
    }

    public Node<T> getNextNode(Node<T> node) {
        return node.next;
    }

    private static class Node<T> {
        private T value;
        private Node<T> prev;
        private Node<T> next;

        Node(T value, Node<T> prev, Node<T> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(value, node.value);
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }
    }
}
 1
Author: zenden2k, 2019-05-27 13:45:32