How to implement Generic Singly Linked List in Java - Part 2

In part 1: Implement a Generic Singly Linked List in Java - Part 1 we have discussed on implementing singly linked list. For reference here is the complete code for it.

package com.velocitybytes.list.impl;

import com.velocitybytes.list.IList;
import org.jetbrains.annotations.Contract;
import org.jetbrains.annotations.NotNull;
import org.springframework.lang.Nullable;

import java.util.Objects;

/**
 * Implementation of a general purpose SinglyLinkedList class.
 *
 * @author Srivastava Bodakunti
 * @version 2020.10.20.001
 */
public class SinglyLinkedList<T> implements IList<T> {
    // *************************************************************************
    // Invariant of SinglyLinkedList:
    // (1) If the list is empty (size = 0), head.data refers to null.
    // (2) If the list is not empty, head.data refers to a null node, and
    // head.next refers to the first non-empty node in the list.
    // *************************************************************************
    private Node<T> head;
    private int size;

    /**
     * Default constructor for the SinglyLinkedList class.
     * It creates an empty list.
     */
    public SinglyLinkedList() {
        this.size = 0;
    }

    /**
     * Adds an element at the end of the list
     *
     * @param data the value to be added at the end of the list
     */
    @Override
    public void add(T data) {
        // if data is null
        if (data == null)
            return;
        // if empty linked list
        if (head == null) {
            head = new Node<>(data);
        } else {
            // create a new node
            Node<T> newNode = new Node<>(data);
            // get the last node in linked list
            Node<T> lastNode = getLastNode(head);
            lastNode.setNext(newNode);
        }
        size++;
    }

    /**
     * Adds an element at the beginning of the list
     * @param data the value to be added at the beginning of the list
     */
    @Override
    public void addFirst(T data) {
        if (data == null)
            return;

        Node<T> newNode = new Node<>(data);

        if (head != null)
            newNode.setNext(head);

        head = newNode;
        size++;
    }

    /**
     * Adds an element at the given index position.
     *
     * @param data the value to be stored in the SinglyLinkedList
     * @param index desired location
     * @throws IndexOutOfBoundsException indicates that the index is not valid.
     */
    @Override
    public void add(T data, int index) {
        if (data == null)
            return;

        if (index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        // if first position
        if (index == 0) {
            addFirst(data);
            return;
        }

        // if last position
        if (index == size()) {
            add(data);
        } else if (index < size()) {
            Node<T> newNode = new Node<>(data);
            Node<T> beforeNode = getNode(index - 1);
            Node<T> afterNode = getNode(index);
            newNode.setNext(afterNode);
            assert beforeNode != null;
            beforeNode.setNext(newNode);
            size++;
        } else {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    /**
     * Retrieves the element at a given index position.
     *
     * @param index location of the desired item
     * @return the element at the desired index position
     * @throws IndexOutOfBoundsException indicates that the index is not valid.
     */
    @Override
    public T get(int index) {
        if (isNotElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        } else {
            Node<T> cursorNode = head;
            for (int i = 0; i < index; i++) {
                cursorNode = cursorNode.getNext();
            }
            return cursorNode.getData();
        }
    }

    /**
     * Method that finds the middle element of the list
     * @return returns the middle element of the list
     */
    @Override
    public T getMiddle() {
        Node<T> slowPtr = head;
        Node<T> fastPtr = head;

        if (head != null) {
            while (fastPtr != null && fastPtr.getNext() != null) {
                fastPtr = fastPtr.getNext().getNext();
                slowPtr = slowPtr.getNext();
            }
            return slowPtr.getData();
        } else {
            return null;
        }
    }

    /**
     * Checks whether the given element exists in the list
     * @param data the value to be checked
     * @return boolean value: {@code true} if exists else {@code false}
     */
    @Override
    public boolean exists(T data) {
        boolean dataExists = false;

        if (data == null)
            return false;

        Node<T> cursorNode = head;
        while (cursorNode != null) {
            if (cursorNode.getData() == data || cursorNode.getData().equals(data)) {
                dataExists = true;
                break;
            }
            cursorNode = cursorNode.getNext();
        }
        return dataExists;
    }

    /**
     * Changes the value of the element at a given index position.
     *
     * @param data the value to substitute the current one
     * @param index location of the desired item
     * @throws IndexOutOfBoundsException indicates that the index is not valid.
     */
    @Override
    public void set(T data, int index) {
        if (data == null)
            return;

        if (isNotElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        } else {
            Node<T> cursorNode = head;
            for (int i = 0; i < index; i++) {
                cursorNode = cursorNode.getNext();
            }
            cursorNode.setData(data);
        }
    }

    /**
     * Reverses the list
     */
    @Override
    public void reverse() {
        Node<T> prevNode = null;
        Node<T> nextNode = head, cursorNode = head;

        while (nextNode != null) {
            nextNode = nextNode.getNext();
            cursorNode.next = prevNode;
            prevNode = cursorNode;
            cursorNode = nextNode;
        }
        head = prevNode;
    }

    /**
     * Obtains the number of elements in the list
     * @return size: number of elements in the list
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Finds whether the list is empty
     * @return {@code true} if list is empty, {@code false} otherwise
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Removes the element at the given index position.
     *
     * @param index integer that represents the position of the item to be removed
     * @throws IndexOutOfBoundsException indicates that the index is not valid.
     */
    @Override
    public T remove(int index) {
        if (isNotElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        } else {
            Node<T> cursorNode = head;
            for (int i = 0; i < index - 1; i++) {
                cursorNode = cursorNode.getNext();
            }
            T removed = cursorNode.getNext().data;
            cursorNode.next = cursorNode.getNext().getNext();
            size--;
            return removed;
        }
    }

    /**
     * Deletes the first occurrence of given data
     * @param data data item to be deleted
     */
    @Override
    public void delete(T data) {
        if (head != null) {
            Node<T> currentNode = head;
            Node<T> previousNode = head;

            while (currentNode != null) {
                if (currentNode.getData() == data) {
                    previousNode.setNext(currentNode.getNext());
                    size--;
                    break;
                } else {
                    previousNode = currentNode;
                    currentNode = currentNode.getNext();
                }
            }
        }
    }

    /**
     * Clear the list
     */
    @Override
    public void clear() {
        removeAllElements();
    }

    private synchronized void removeAllElements() {
        if (head != null) {
            for (Node<T> cursorNode = head; cursorNode != null;) {
                Node<T> nextNode = cursorNode.getNext();
                cursorNode.data = null;
                cursorNode.next = null;
                size--;
                cursorNode = nextNode;
            }
        }
    }

    private boolean isNotElementIndex(int index) {
        return index < 0 || index > size - 1;
    }

    @NotNull
    @Contract(pure = true)
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    private Node<T> getLastNode(Node<T> node) {
        return node.getNext() != null ? getLastNode(node.getNext()) : node;
    }

    @Nullable
    private Node<T> getNode(int index) {
        if (isNotElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        if (index == 0)
            return head;

        if (index == size() - 1)
            return getLastNode(head);

        int cursor = 0;
        Node<T> cursorNode = head;

        while (cursor <= index) {
            if (cursor == index) {
                return cursorNode;
            } else {
                if (cursorNode != null) {
                    cursorNode = cursorNode.getNext();
                }
                cursor++;
            }
        }
        return null;
    }

    public boolean loopExists() {

        boolean loopExists = false;

        if (head != null) {
            Node<T> slowPtr = head, fastPtr = head;

            while (slowPtr != null && fastPtr != null && fastPtr.getNext() != null) {
                slowPtr = slowPtr.getNext();
                fastPtr = fastPtr.getNext().getNext();

                if (slowPtr == fastPtr) {
                    loopExists = true;
                    break;
                }
            }
        }
        return loopExists;
    }

    /**
     * Custom toString implementation
     * @return returns list in format [x, y, z]
     */
    @Override
    public String toString() {
        StringBuilder format = new StringBuilder("[");
        Node<T> cursorNode = head;

        while (cursorNode != null) {
            format.append(cursorNode.toString());
            cursorNode = cursorNode.getNext();

            if (cursorNode != null) {
                format.append(", ");
            }
        }
        format.append("]");
        return format.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof SinglyLinkedList))
            return false;

        SinglyLinkedList<?> that = (SinglyLinkedList<?>) obj;

        if (size != that.size)
            return false;

        return Objects.equals(head, that.head);
    }

    @Override
    public int hashCode() {
        int result = head != null ? head.hashCode() : 0;
        result = 31 * result + size;
        return result;
    }
}

Now that our linked list implementation is ready, let's test it. I have used Spring Boot while writing the code for it. For testing, I have used JUnit. JUnit is unit testing framework for Java. Here is the complete code for it. The code is self explanatory. I have tested only for integers and string when I was working on it and here I kept only for integers, but it is same for strings or other types.

/*
 * Copyright (c) 2020.
 * @author: Srivastava Bodakunti
 */

package com.velocitybytes.list;

import com.velocitybytes.list.impl.SinglyLinkedList;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.jupiter.api.Assertions.assertEquals;

@RunWith(SpringRunner.class)
@SpringBootTest
public class SinglyLinkedListTest {

    @Test(expected = IndexOutOfBoundsException.class)
    public void testSinglyLinkedListGet() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        // no data added, should produce IndexOutOfBoundsException
        assertEquals(3, (long) linkedList.get(2));
    }

    @Test
    public void testSinglyLinkedListIntegerAdd() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        assertEquals(1, (long) linkedList.get(0));
        linkedList.add(2);
        linkedList.add(3);
        assertEquals(1, (long) linkedList.get(0));
        assertEquals(2, (long) linkedList.get(1));
        assertEquals(3, (long) linkedList.get(2));
        linkedList.addFirst(0);
        assertEquals(0, (long) linkedList.get(0));
    }

    @Test
    public void testSinglyLinkedListIntegerSet() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.addFirst(0);
        linkedList.add(2);
        linkedList.add(1, 1);
        linkedList.add(3);
        linkedList.add(5);
        linkedList.set(4, 4);
        assertEquals("[0, 1, 2, 3, 4]", linkedList.toString());
        linkedList.set(7, 3);
        assertEquals("[0, 1, 2, 7, 4]", linkedList.toString());
        linkedList.set(8, 0);
        assertEquals("[8, 1, 2, 7, 4]", linkedList.toString());
    }

    @Test
    public void testSinglyLinkedListIntegerRemove() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertEquals(4, linkedList.size());
        assertEquals(2, (long) linkedList.remove(1));
        assertEquals(3, linkedList.size());
        assertEquals(3, (long) linkedList.remove(1));
    }

    @Test
    public void testSinglyLinkedListIntegerDelete() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.delete(2);
        assertEquals("[1, 3, 4]", linkedList.toString());
        assertEquals(3, linkedList.size());
    }

    @Test
    public void testSinglyLinkedListIntegerSize() {
        SinglyLinkedList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertEquals(4, linkedList.size());
        linkedList.add(5, 2);
        assertEquals(5, linkedList.size());
    }

    @Test
    public void testSinglyLinkedListIntegerClear() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.clear();
        assertEquals("[]", linkedList.toString());
        assertEquals(0, linkedList.size());
    }

    @Test
    public void testSinglyLinkedListIntegerIsEmpty() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertFalse(linkedList.isEmpty());
        linkedList.clear();
        assertTrue(linkedList.isEmpty());
    }

    @Test
    public void testSinglyLinkedListIntegerExists() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertFalse(linkedList.exists(7));
        assertTrue(linkedList.exists(3));
    }

    @Test
    public void testSinglyLinkedListIntegerGetMiddle() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertEquals(3, linkedList.getMiddle());
    }

    @Test
    public void testSinglyLinkedListIntegerReverse() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.reverse();
        assertEquals("[4, 3, 2, 1]", linkedList.toString());
    }

    @Test
    public void testSinglyLinkedListIntegerLoop() {
        SinglyLinkedList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertFalse(linkedList.loopExists());
    }

    @Test
    public void testSinglyLinkedListIntegerToString() {
        IList<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        assertEquals("[1, 2, 3, 4]", linkedList.toString());
        linkedList.add(5, 2);
        assertEquals("[1, 2, 5, 3, 4]", linkedList.toString());
    }
}

You can see the below screenshot for the test cases passed.