3
\$\begingroup\$

Purpose

I wanted to try and implement a very basic Singly Linked List as a data structure exercise.

Implementation Discussion

I know that the Java LinkedList API is quite extensive. However, in this basic implementation, I just wanted to implement the addAtIndex, removeAtIndex, and get methods (with the add and remove methods delegating to the addAtIndex and removeAtIndex methods).

Things that I could improve

  • For the addAtIndex and removeAtIndex methods I special-case when the index is 0 - is there a more elegant solution?
  • Do the exceptions make sense?
    • For the remove method should I check to see if the list is empty and then throw an IllegalStateException before calling the removeAtIndex method? Same thing for the get method?
    • Should I replace the IllegalArgumentExceptions with IndexOutOfBoundExceptions?

Implementation

import java.util.Objects;

public class SinglyLinkedList<T> {

    public static class Node<E> {
        private final E data;
        private Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }

        public E getData() {
            return this.data;
        }

        public Node<E> getNext() {
            return this.next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }

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

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }

            if (!(obj instanceof Node)) {
                return false;
            }

            Node node = (Node) obj;

            return Objects.equals(this.data, node.data) &&
                    Objects.equals(this.next, node.next);
        }
    }

    private Node<T> head = null;
    private int size = 0;

    public SinglyLinkedList() {
    }

    public int getSize() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.getSize() == 0;
    }

    public Node<T> getHead() {
        return this.head;
    }

    public void add(T data) {
        this.addAtIndex(data, this.size);
    }

    public void remove() {
        this.removeAtIndex(this.size - 1);
    }

    public void addAtIndex(T data, int index) {
        if (index > this.size || index < 0) {
            throw new IllegalArgumentException("Invalid index value");
        }

        Node<T> currentNode = this.head;

        if (index == 0) {
            this.head = new Node<>(data, currentNode);
        } else {
            for (int i = 0; i < index - 1; i++) {
                currentNode = currentNode.getNext();
            }

            Node<T> nextNode = new Node<>(data, currentNode.getNext());
            currentNode.setNext(nextNode);
        }

        this.size++;
    }

    public void removeAtIndex(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Invalid index value");
        }

        Node<T> currentNode = this.head;

        if (index == 0) {
            this.head = currentNode.getNext();
        } else {
            for (int i = 0; i < index - 1; i++) {
                currentNode = currentNode.getNext();
            }

            currentNode.setNext(currentNode.getNext().getNext());
        }

        this.size--;
    }

    public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Invalid index value");
        }

        Node<T> currentNode = this.head;

        int count = 0;
        while (count < index) {
            currentNode = currentNode.getNext();
            count++;
        }

        return currentNode.getData();
    }

}
\$\endgroup\$
3
\$\begingroup\$

I think it's looking pretty good so far!

A few things,

I would make the Node class private. This is an implementation detail and nobody using your list should need to know or worry about it. I would also remove any public facing methods that return a Node over a T. If you want them internally you can make them private. (The built in Java LinkedList uses a private Node class but we don't need to worry about it)

You could remove a lot of boiler plate getters and setters by making the Node class private. You can access the fields directly within your SinglyLinkedList class.

When someone passes in a bad index, I would prefer and IndexOutOfBoundsException over IllegalArgumentException. (this is what java.util.Lists do afterall)

As well as this, I'd also like to see a more descriptive exception message. Maybe say which index was used, and what the current size is of the list.

You've overridden equals and hashCode in your node class which is usually a good thing to do in general, but here you don't really need it. However you may like to keep it if you end up adding additional functionality that may rely on it.

I think special casing index 0 is perfectly fine. 2 distinct things happen depending on it being the first element or any subsequent one.

A nice toString method would also be good here, you could just use a StringBuilder or StringJoiner to do this easily.

\$\endgroup\$
  • \$\begingroup\$ Implementing Node.equals() can be useful when you want to implement SinglyLinkedList.equals(). You simply call Objects.equals(Object, Object) on the two head nodes and you're done. \$\endgroup\$ – Stingy Jul 27 '17 at 3:58
1
\$\begingroup\$

Chatton has already explained the general unnecessity of making Node public, but I would like to point out a specific problem in your code: By making both Node.setNext(Node) and SinglyLinkedList.getHead() public, you are putting your list in danger of being corrupted, because with a reference to head, one has almost complete control over your object, more than you would probably like (only size remains inaccessible directly). So even if the class Node is public, you should still make at least one of these two methods private.

I also agree with chatton that, if you pass 0 as an index to addAtIndex(int) or removeAtIndex(int), this is simply a special case and there is no more elegant solution for this. If the index is 0, the new node must be set by changing the reference of a SinglyLinkedList's instance field (head). If the index is greater than 0, however, the new node must be set by changing the reference of a Node's instance field (next). The classes SinglyLinkedList and Node are unrelated to each other, so using a common method to change that field is not an option. The most "elegant" way I could think of that does not handle both cases separately is by determining the field whose reference to change at runtime using reflection, and I doubt you would call this "more elegant" (at least I wouldn't).

I look at your addAtIndex(T, int) and removeAtIndex(int) methods and see duplicate code. Alarm bells ring. Even if it's just 3 lines. You could make a private method that returns the Node at a given index and call this method instead:

private Node<T> getNodeAt(int index) {
    Node<T> currentNode = this.head;
    for (int i = 0; i < index && currentNode != null; i++) {
        currentNode = currentNode.getNext();
    }
    if (currentNode == null) {
        throw new IndexOutOfBoundsException("Nice try");
    } else {
        return currentNode;
    }
}

A final remark about the field size. Technically, the size of your SinglyLinkedList is not really a state of the object per se, but rather a value that depends on another field, namely head. So you represent the same property of your object in different fields, which is basically an invitation for bugs. You might forget to update size when you add or remove an element, or you might make another mistake that causes size to contain an incorrect value. The problem I mentioned at the beginning of this answer is an example of this. Even if the exposure of the list's head node and its setNext(Node) method is intentional, your object can still become corrupted because size will not be updated if someone simply modifies the list's head node. If I were you, I would remove this field and instead make the method getSize() calculate the list size based on the field head. True, this might make a call to getSize() more expensive than if the size were cached in a field, but this is not your problem but that of the caller. And if that caller is you because you want to ensure that the index parameter passed to addAtIndex(T, int), removeAtIndex(int) and get(int) is valid, you can instead rely on getNodeAt(int) to throw an exception if the index is out of bounds, so you don't have to traverse the node tree multiple times.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.