Singly linked list implementation

Question

I am new to studying data structures although I have been programming in Java/Android since October. I feel it's time to advance, so I am starting data structures / algorithms this month. Since linked lists are a big topic in interviews and I knew nothing about them (I spent the past 3 days learning about it), hopefully my code is mostly correct, but please let me know if I am missing anything or not catching something, or if there's any way to improve it.

public class MyLinkedList<T> {

    private LinkNode<T> head;
    private int size;

    public MyLinkedList() {
        this.head = null;
        this.size = 0;
    }

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

    }

    public void addEnd(T data) {
        if (head == null) {
            head = new LinkNode<T>(data, head);
        } else {
            LinkNode<T> current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            LinkNode<T> newNode = new LinkNode<T>(data, null);
            current.setNext(newNode);
            size++;
        }
    }

    public void addFront(T data) {
        head = new LinkNode<T>(data, head);
        size++;
    }

    public void removeEnd() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            LinkNode<T> current = head;
            LinkNode<T> previous = head;
            while (current.getNext() != null) {
                previous = current;
                current = current.getNext();
            }
            previous.setNext(null);
            size--;
        }
    }

    public void removeFront() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            head = head.getNext();
        }
        size--;
    }

    public void removeNode(T data) {
        if (head == null) {
            System.out.println("empty list");

        } else {
            LinkNode<T> current = head;
            LinkNode<T> previous = head;
            while (current.getData() != data) {
                previous = current;
                current = current.getNext();
            }
            if (current == head) {
                head = head.getNext();
            }
            previous.setNext(current.getNext());
        }
        size--;
    }

    public LinkNode<T> getNode(T data) {
        LinkNode<T> current = head;
        if (head == null) {
            System.out.println("empty list");
            return null;
        } else {
            while (current.getData() != data) {
                if (current.getNext() == null) {
                    System.out.println("not found");
                    return null;
                }
            }
        }
        return current;
    }

    private static class LinkNode<T> {
        T data;
        LinkNode<T> next;

        private LinkNode(T data, LinkNode<T> next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

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

        public void setNext(LinkNode<T> node) {
            this.next = node;
        }

        public String toString() {
            return ("\nData: " + data);

        }

    }

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<String>();
        list.addEnd("a");
        list.addEnd("aaa");
        list.addEnd("aaaaaa");
        list.removeNode("aaa");
        list.display();
    }

}

My main concern is how differently every one writes these implementations.

Answer 1

This is a great first attempt with a consistent coding style and good variable names. Bravo!

• Consider implementing the java.util.List interface so you could use it with existing methods. You already have most of the methods and would just need to change some names. For example, addEnd becomes append, getNode becomes indexOf (with some changes), etc. It defines quite a few more methods entailing more work, but it would make for a great exercise.

• You can remove the constructor since it has no effect. Unlike C, Java initializes all local variables and fields to default values determined by their types, unless the declaration provides a value. References are initialized to null, numeric types to 0, booleans to false, etc.

• Never expose private inner classes publicly. Instead of returning a LinkNode, getNode should return the index of the found node. If you want to allow clients to change the data held by a node, provide set(int index, T data) and optionally replaceFirst(T data, T replacement) to avoid seeking the node twice.

• Instead of passing null for next to the LinkNode constructor, create a second constructor that accepts just the data value. Optionally, the existing constructor may pass data to this new constructor so all fields are initialized it at most one place.

  private LinkNode(T data) {
      this.data = data;
  }
  
  private LinkNode(T data, LinkNode next) {
      this(data);
      this.next = next;
  }
  

Finally, you're treating LinkNode as a pure data-holder a la C structs which gives the list class two responsibilities. While this centralizes the logic maintaining the structure in the list, it makes the full list responsible for managing both the list itself (the head) and each node's internal state. Classes that have a single responsibility are much easier to understand, write, and test.

Moving the node-specific logic from the list to the node class would simplify many of the methods, increase DRY, and make each class responsible for one thing. I'll provide one example for addEnd to demonstrate the technique.

public void addEnd(T data) {
    if (head == null) {
        head = new LinkNode(data);
    } else {
        head.addEnd(data);
    }
}

private static class LinkNode<T> {
    ...
    void addEnd(T data) {
        if (next == null) {
            next = new LinkNode(data);
        } else {
            next.addEnd(data);
        }
    }
}

One thing to note is that this turns many of the algorithms into recursive methods which requires more stack space (memory) since Java doesn't have tail recursion.

Answer 2

Here are a few comments I would make:

• You can keep a permanent reference to the tail, which makes appending at the end o(1) operation rather than o(n)
• You can make a double-link list, by keeping reference to next and previous links. Deletion of the last link becomes o(1) instead of o(n)
• Your removeNode methods crashes if the node is not in the list

Apart from that, I think David Harkness said it all.