Implementation of a doubly linked list in Java

Question

I'd like to improve this code.

DoublyLinkList.java

public class DoublyLinkList<T> {

    private static class Node<T> {
        private T data;
        private Node next;
        private Node prev;

        public Node(T data) {
            this.data = data;
        }

        public void displayNode() {
            System.out.print(data + " ");
        }

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

    public Node first = null;
    public Node last = null;

    public void addFirst(T data) {
        Node newNode = new Node(data);

        if (isEmpty()) {
            newNode.next = null;
            newNode.prev = null;
            first = newNode;
            last = newNode;

        } else {
            first.prev = newNode;
            newNode.next = first;
            newNode.prev = null;
            first = newNode;
        }
    }

    public boolean isEmpty() {
        return (first == null);
    }

    public void displayList() {
        Node current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }

    public void removeFirst() {
        if (!isEmpty()) {
            Node temp = first;

            if (first.next == null) {
                first = null;
                last = null;
            } else {
                first = first.next;
                first.prev = null;
            }
            System.out.println(temp.toString() + " is popped from the list");
        }
    }

    public void removeLast() {
        Node temp = last;

        if (!isEmpty()) {

            if (first.next == null) {
                first = null;
                last = null;
            } else {
                last = last.prev;
                last.next = null;
            }
        }
        System.out.println(temp.toString() + " is popped from the list");
    }
}

DoublyLinkListDemo.java

public class DoublyLinkListDemo {

    public static void main(String[] args) {
        DoublyLinkList newList = new DoublyLinkList();
        newList.addFirst("arun");
        newList.addFirst("prakash");
        newList.addFirst(70);
        newList.addFirst(80);
        newList.addFirst(30);
        newList.displayList();
        newList.removeFirst();
        newList.removeFirst();
        newList.removeFirst();
        newList.removeLast();

        newList.displayList();
    }
}

Answer 1

I think your code looks good, I just have a couple of thoughts:

Implementing Interfaces

As you are creating a list, it would make sense to implement the Java List interface. It would mean implementing more methods than you have right now, but you can always throw an UnsupportedOperationException if you don't need a specific method (although some more methods wouldn't hurt, like add(int i), etc).

If you don't want to do that, I would at least implement Iterable, that way you could simplify your displayList method, and it would generally be easier to work with your list.

Displaying Code

I wouldn't add methods to the list that outputs the list directly. Overriding toString is good, but printing shouldn't be the job of a list. So instead of having displayList, I would override toString in the list as well, and then just change newList.displayList(); to System.out.println(list.toString()), and remove all display methods.

Reporting that an element is removed also shouldn't happen in the list.

Exceptions

Right now, if a node is removed that doesn't exist, nothing happens. You might want to throw an IndexOutOfBoundsException or similar.

Style

• simple return statements don't need parentheses (return (first == null); -> return first == null;)
• for naming, see @carls comment (although I wouldn't use pop (or push), because it implies that an element is returned, which it isn't).

Answer 2

removeLast() assigns last to temp, which may be null. If the list is empty, you will call toString() on null.

Otherwise, it is a pretty well made list.

I would change the names of your functions/class.

• DoublyLinkList becomes DoublyLinkedList
• addFirst becomes pushFront
• removeFirst becomes popFront
• removeLast becomes popBack
• displayList becomes display ( because we know a list is calling it )
• displayNode becomes display

As general advise about naming, the words you are using to describe what is happening are good hints at what names the functions/class should be. For example, you use Doubly Linked List in the title of this post, and you use the word "popped" as output to the remove functions.

Answer 3

My comments (style and functionality) are in the code. Good job overall, and especially with your variable and method names.

// implement Iterable at least, but List would be even better
public class DoublyLinkList<T> {

    // private classes should be at the end of the file
    private static class Node<T> {
        private T data;
        private Node next;
        private Node prev;

        public Node(T data) {
            this.data = data;
        }

        // no need for this method
        public void displayNode() {
            System.out.print(data + " ");
        }

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

    // both should be private, nobody outside should see the node class
    public Node first = null;
    public Node last = null;

    public void addFirst(T data) {
        Node newNode = new Node(data);

        if (isEmpty()) {
            newNode.next = null; // no need for this line, it is null by default
            newNode.prev = null; // no need for this line, it is null by default
            first = newNode;
            last = newNode;

        } else {
            first.prev = newNode;
            newNode.next = first;
            newNode.prev = null; // no need for this line, it is null by default
            first = newNode;
        }
    }

    // what about an addLast method?

    public boolean isEmpty() {
        return (first == null); // no need for parenthesis
    }

    // no need for this method (use toString)
    public void displayList() {
        Node current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }

    // it is helpful for remove to return the element removed
    public void removeFirst() {
        // if (isEmpty()) {
        //     throw new NoSuchElementException();
        // }
        // ...
        if (!isEmpty()) {
            Node temp = first;

            if (first.next == null) {
                first = null;
                last = null;
            } else {
                first = first.next;
                first.prev = null;
            }
            // should not really be printing in these methods
            System.out.println(temp.toString() + " is popped from the list"); // ...was removed from...
        }
    }

    // it is helpful for remove to return the element removed
    public void removeLast() {
        // if (isEmpty()) {
        //     throw new NoSuchElementException();
        // }
        // ...
        Node temp = last;

        if (!isEmpty()) {

            if (first.next == null) {
                first = null;
                last = null;
            } else {
                last = last.prev;
                last.next = null;
            }
        }
        // should not really be printing in these methods
        System.out.println(temp.toString() + " is popped from the list"); // ...was removed from...
    }
}

The reason you don't want to print things to stdout is because people using the class don't necessarily want to print to there. Usually there will be a logger where you want that info to go, so if you really want to have debug messages check out java's logger class. However if you are just doing this for fun, the extra messages can be fast and convenient, but I wanted to make sure you are aware of these facts.