Implementing a Singly Linked List

Question

I am implementing, in my SinglyLinkedList class, an interface where I redefined linked list. I am trying to learn data structures. Please, let me know what I can approve upon in my code.

public class SinglyLinkedList<E> implements LinkedList<E> {

    private class Node<E> {

        public Node<E> next;
        public E element;

        public Node(E element) {

            this.element = element;
        }

        public Node (E element, Node<E> next) {

            this.element = element;
            this.next = next;
        }

        public E getElement() {

            return element;
        }

        public Node<E> getNext() {

            return next;
        }

        public void setElement(E element) {

            this.element = element;
        }

        public void setNext(Node<E> next) {

            this.next = next;
        }

        public String toString() {

            return ("[" + element + "] ");
        }
    }

    public Node<E> head;
    public Node<E> tail;
    public int total;      

    public SinglyLinkedList() {

        this.head = null;
        this.tail = null; 
        this.total = 0;
    }

    public E get(int index) {

        if (index < 0 || index > size()) {
            return null;
        }

        if (index == 0) {
            return head.getElement();
        }

        Node<E> singly = head.getNext();

        for (int i = 1; i < index; i ++) {

            if (singly.getNext() == null) {
              return null;
            }       

            singly = singly.getNext();      
        }

        System.out.println("\n" + singly.getElement());

        return singly.getElement(); 
    }

    public void add(E element) {
        Node<E> singlyAdd = new Node<E>(element);

        if (tail == null) {
            head = singlyAdd;
            tail = singlyAdd;
        } else {
            tail.setNext(singlyAdd);
            tail = singlyAdd;
        }     

        total++;
    }

    public boolean add(int index, E data) {

        if (index < 0 || index > size()) {
            return false;      
        } else {
            Node<E> singlyAdd = new Node<E>(data);
            Node<E> singly = head;

            for (int i = 1; i < index && singly.getNext() != null; i++) {
                singly = singly.getNext();
            }

            singlyAdd.setNext(singly.getNext());

            singly.setNext(singlyAdd);
            total++;
            return true;
        }   
    }       

    public void display() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            Node<E> current = head;
            while (current != null) {
                System.out.print(current.toString());
                current = current.getNext();
            }
        }

    }

    public boolean contains(E data) {

        if (head == null) {
            return false;
        }

        if (head.getElement() == data) {
            System.out.println(head);
            return true;                                
        }

        while (head.getNext() != null) {
            head = head.getNext();

            if (head.getElement() == data) {
                System.out.println(head);                
                return true;                               
            }             

        } 

        return false;         
    }       

    private Node<E> removeFirst() {
        if (head == null) {
            System.out.println("We cant delete an empty list");
        }    

        Node<E> singly = head;            
        head = head.getNext();
        singly.setNext(null);
        total--;

        return singly;     
    } 

    private Node<E> removeLast() {

        Node<E> nodeBefore;
        Node<E> nodeToRemove;     

        if (size() == 0) {
            System.out.println("Empty list");
        }    

        nodeBefore = head;

        for (int i = 0; i < size() - 2; i++) {
          nodeBefore = nodeBefore.getNext();
        }    

        nodeToRemove = tail;    

        nodeBefore.setNext(null);
        tail = nodeBefore;
        total--;

        return nodeToRemove;
    }       

    public E remove(int index) {      

        E hold = get(index);     

        if (index < 0 || index >= size()) {
            return null;
        } else if (index == 0) { 

            removeFirst();    
            return hold;
        } else {

            Node<E> current = head;
            for (int i = 1; i < index; i++) {                
                current = current.getNext();
            }  

            current.setNext(current.getNext().getNext());
            total--; 
            return hold;
        }       
    }       

    public int size() {
        return getTotal();
    }             

    public void clear() {

        while (head.getNext() != null) {    
            remove(head.getElement());    
        }

        remove(head.getElement());    
    }

    public int getTotal() {
        return total;
    } 
}

Interface:

public interface LinkedList<E> {    

    E get(int index);    

    void add(E data);        

    boolean add(int index, E data);      

    boolean contains(E data);    

    E remove(int index);        

    int size();    

    void clear();

}

Answer 1

Your code is pretty good, you use generics as an adult programmer should do whenever dealing with data structures. There is, however, room for improvement (I have added the comments in the code below near every point where I have something to comment):

public class SinglyLinkedList<E> implements LinkedList<E> {

    /*
    Use keyword static in order to strip the implicit reference to an instance
    of SinglyLinkedList and save space.
    */
    private static class Node<E> {

        public Node<E> next;
        public E element;

        public Node(final E element) {
            this.element = element;
        }

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

        public E getElement() {
            return element;
        }

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

        public void setElement(final E element) {
            this.element = element;
        }

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

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /*
     * Don't you ever reveal the implementation details. ;-)
     */
    private Node<E> head;
    private Node<E> tail;
    private int size;    

    @Override
    public E get(final int index) {
        if (index < 0 || index >= size()) {
            return null;
        }

        Node<E> singly = head;

        for (int i = 0; i < index; i ++) {
            singly = singly.getNext();      
        }

        return singly.getElement(); 
    }

    @Override
    public void add(final E element) {
        Node<E> singlyAdd = new Node<>(element);

        if (tail == null) {
            head = singlyAdd;
            tail = singlyAdd;
        } else {
            tail.setNext(singlyAdd);
            tail = singlyAdd;
        }     

        size++;
    }

    /*
     * Your add(int, E) was broken. Not anymore.
     */
    @Override
    public boolean add(final int index, final E data) {
        if (index < 0 || index > size()) {
            return false;      
        } 

        Node<E> newNode = new Node<>(data);
        Node<E> prev = null;
        Node<E> singly = head;

        for (int i = 0; i < index; i++) {
            prev = singly;
            singly = singly.getNext();
        }

        if (singly == null) {
            // Append to the tail.
            tail.setNext(newNode);
            tail = newNode;
        } else {
            if (singly == head) {
                newNode.setNext(head);
                head = newNode;
            } else {
                prev.setNext(newNode);
                newNode.setNext(singly);
            }
        }

        ++size;
        return true;
    }   

    public void display() {
        System.out.print("[");

        int i = 0;
        Node<E> current = head;

        while (current != null) {
            System.out.print(current.toString() + (i < size - 1 ? ", " : ""));
            current = current.getNext();
            ++i;
        }

        System.out.println("]");
    }

    @Override
    public boolean contains(E data) {
        if (head == null) {
            return false;
        }

        Node<E> node = head;

        while (node != null) {
            if (node.getElement().equals(data)) {
                return true;
            }

            node = node.getNext();
        }

        return false;         
    }       

    /*
     This is a really good idea to handle the special case of the removal 
     routine.
    */
    private Node<E> removeFirst() {
        if (size() == 0) {
            throw new IllegalStateException("Removing from an empty list.");
        }    

        Node<E> singly = head;            
        head = head.getNext();
        singly.setNext(null);
        --size;
        return singly;     
    } 

    /*
    This one is cool also.
    */
    private Node<E> removeLast() {
        if (size() == 0) {
            throw new IllegalStateException("Removing from an empty list.");
        }    

        if (size() == 1) {
            final Node<E> last = tail;
            size = 0;
            head = null;
            tail = null;
            return last;
        }

        Node<E> target = head;
        Node<E> prev = null;

        for (int i = 0; i < size() - 1; ++i) {
            prev = target;
            target = target.getNext();
        }

        prev.setNext(null);
        tail = prev;
        return target;
    }       

    @Override
    public E remove(int index) {      
        E hold = get(index);     

        if (index < 0 || index >= size()) {
            return null;
        }

        if (index == 0) {
            return removeFirst().getElement();
        }

        if (index == size() - 1) {
            return removeLast().getElement();
        }

        Node<E> prev = null;
        Node<E> current = head;

        for (int i = 0; i < index; i++) {   
            prev = current;
            current = current.getNext();
        }  

        prev.setNext(current.getNext());
        --size; 
        return hold;     
    }       

    /*
    What's the point to delegate to getTotal?
    */
    @Override
    public int size() {
        return size;
    }             

    /*
    Just nullify all the references and the garbage collector will do its work.
    */
    @Override
    public void clear() {
        size = 0;
        head = null;
        tail = null;
    }

    public static void main(final String... args) {
        // Your list.
        SinglyLinkedList2<Integer> list2 = new SinglyLinkedList2<>();
        // The new reimplementation.
        SinglyLinkedList<Integer> list1 = new SinglyLinkedList<>();

        for (int i = 0; i < 4; ++i) {
            list1.add(i);
            list2.add(i);
        }

        list1.display();
        list2.display();

        System.out.println("add(int, E) fails here: ");

        list1.add(0, 10);
        list2.add(0, 10);

        list1.display();
        list2.display();

        list1.add(5, 11);
        list2.add(5, 11);

        list1.display();
        list2.display();
    }
}

Answer 2

Interface

Your interface differs from the standard LinkedList interface in a couple of points:

• add(E) returns nothing: The standard function returns true if the list changed, but I think your way is fine as well.
• add(int, E): Your function returns false, while the standard throws an exception. This is an exceptional case, so the standard interface handles this better than your solution.
• you never throw any exceptions when things are out of bounds. Eg, I can remove a node at an index that doesn't exist, and your code does this without notifying me that it doesn't do anything. I would have to check what your method returned to find out. Exceptions are the better solution here.

So I would replace all your

    if (index < 0 || index > size()) {
        return <Something>;
    }

with

    if (index < 0 || index > size()) {
        throw new IndexOutOfBoundsException(index + " is not a valid index. List length is only " + size());
    }

Misc

• fields should be private, and the access methods should be used to access them.
• do not print in a class. If you were to actually use this list in projects, you don't want it to print anything.
• you don't need the null checks (singly.getNext() != null, if (singly.getNext() == null)) in your loops, as you already checked the bounds at the beginning.
• use @Override to show which methods implement the interface, and which don't.