LinkedList Implementation in Java

Question

Please review my implementation. I know there is already an implementation in Java, but I just wanted to come up with my implementation. Let me know if I can improve this.

import java.util.NoSuchElementException;

public class LinkedListImplementation<T> {
    private int size;
    private ListNode<T> head;

    static class ListNode<T> {
        private T value;
        private ListNode<T> next;

        public ListNode(T val) {
            this.value = val;
            this.next = null;
        }

        public T getValue() {
            return value;
        }

        public ListNode<T> getNext() {
            return next;
        }

        public void setNext(ListNode<T> nextNode) {
            this.next = nextNode;
            return;
        }

        public String toString() {
            if(this.value == null) {
                return "null";
            }
            return this.value.toString();
        }
    }

    public LinkedListImplementation() {
        head = new ListNode(0);
        head.setNext(null);
        size = 0;
    }

    public void add(T val) {
        ListNode<T> cur = new ListNode<>(val);
        if(size == 0) {
            head.setNext(cur);
            size++;
            return;
        }

        ListNode<T> prev = head;
        while(prev.getNext() != null) {
            prev = prev.getNext();
        }

        prev.setNext(cur);
        size++;
        return;
    }

    public boolean remove(T val) {
        if(size == 0) {
            throw new NoSuchElementException();
        }

        ListNode<T> cur = head;
        ListNode<T> prev = null;
        while(cur.getNext() != null && cur.getNext().getValue() != val) {
            prev = cur;
            cur = cur.getNext();
        }

        if(cur.getNext() != null && cur.getNext().getValue() == val) {
            prev = cur;
            cur = cur.getNext();
            prev.setNext(cur.getNext());
            size--;
        }
        else {
            return false;
        }
        return true;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        head.setNext(null);
        size = 0;
        return;
    }

    public ListNode<T> get(int index) {
        if(index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        int curIndex = index;
        ListNode<T> cur = head;

        while(cur.getNext() != null && curIndex-- > 0) {
            cur = cur.getNext();
        }

        if(curIndex != -1) {
            throw new NoSuchElementException();
        }
        return cur.getNext();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode<T> cur = head;
        sb.append(cur.getValue() + "->");

        while(cur.getNext() != null) {
            sb.append(cur.getNext().getValue() + "->");
            cur = cur.getNext();
        }
        sb.append("null");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedListImplementation<Integer> list = new LinkedListImplementation<>();
        System.out.println(list.size());
        list.add(1);
        list.add(3);
        list.add(5);
        System.out.println(list.remove(3));
        System.out.println(list.size());
        System.out.println(list.get(1));
        System.out.println(list.remove(6));
        System.out.println(list.get(0));
        System.out.println(list.get(1));
        //System.out.println(list.get(20));// ArraysIndexOutOfBoundsException.
        System.out.println(list.remove(5));
        System.out.println(list.size());
        //System.out.println(list.get(1));// ArraysIndexOutOfBoundsException.
        System.out.println(list.get(0));
        list.clear();
        System.out.println(list.size());
        //System.out.println(list.remove(1));//NoSuchElementException.
    }
}

Answer 1

• The name LinkedListImplementation seems a little awkward, especially if someone else may try to use it. It's understandable that you want to avoid using the same name as the official class, in which case you can consider MyLinkedList as the class name.

• There's no need for that stray return at the end of clear() since it's a void function.

• I'm not sure why those statements in main() are commented out. Testing for exceptions is okay. But, perhaps this indicates that you should have actual unit testing using JUnit. main() would then initiate these tests without the need to comment out any of them.

Answer 2

API

It's ok to reimplement a known library class for practice. But when you do, it's good to try to imitate the same programming interface and behavior. There are several important unfortunate differences from the library:

• The get method returns a ListNode. The ListNode class is an implementation detail. Users of your linked list should be able to use it without knowing how you implemented the nodes. Exposing this detail makes users vulnerable to changes in your implementation. For the same reason, the nested ListNode class should be private, along with all its methods.

• The get method throws ArrayIndexOutOfBoundsException for indexes that don't exist. But a linked list has should have nothing to do with arrays. The appropriate exception would be IndexOutOfBoundsException.

Note that a get method to access arbitrary indexes of a linked list is not a common functionality, because it's typically not efficient by the nature of linked lists. A more common and anticipated method would be getting the head element.

Generics

It's good that you made the element type parameterized. But you violate that in the constructor:

    head = new ListNode(0);

One problem here is that ListNode is a raw type, another is that you're passing an integer as the value, which may be different from T. You should use null as the value, and use the diamond operator <> as the element type:

    head = new ListNode<>(null);

Unnecessary code

In the add method, you can simply delete these lines:

    if (size == 0) {
        head.setNext(cur);
        size++;
        return;
    }

The loop logic in the method naturally takes care of the size == 0 case.

Also, as the method is void, you should remove the pointless return statement at the end.

In the remove method, prev is initialized before the while loop and although it's assigned in the loop's body, it's not used. You should remove it from inside the loop, and declare it inside the if condition. Actually, you don't really need it in the if condition either. The remove method can be simplified to this:

public boolean remove(T val) {
    if (size == 0) {
        throw new NoSuchElementException();
    }

    ListNode<T> cur = head;
    while (cur.getNext() != null && cur.getNext().getValue() != val) {
        cur = cur.getNext();
    }

    if (cur.getNext() != null && cur.getNext().getValue() == val) {
        cur.setNext(cur.getNext().getNext());
        size--;
        return true;
    }
    return false;
}

Testing

The code you have in the main method is not a good way to test an implementation. I recommend to look into JUnit4 and writing proper test cases using assertions.