Doubly linked list in Java

Question

I did not add generics to my code because I am new to Java. I am on my way in learning data structures and algorithms. I just want to make sure that my code is clean and efficient.

package Double_LinkedList;

class Node{
    int data;
    Node prev;
    Node next;

    void setData(int data){
        this.data = data;
    }

    int getData(){
        return data;
    }

    void setPrev(Node prev){
        this.prev = prev;
    }

    void setNext(Node next){
        this.next = next;
    }

    Node getPrev(){
        return prev;
    }

    Node getNext(){
        return next;
    }

    Node(int data, Node prev, Node next){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    Node(int data){
        this.data = data;
    }

    Node(){    }
}

public class DoubleLinkedList{

    private Node head = null;
    private Node tail;

    private int length;

    public Node getHead(){
        return head;
    }

    public Node getTail(){
        return tail;
    }

    public int getData(Node node){
        return node.getData();
    }
    public int getLength(){
        return length;
    }
    public void insertFront(int data){

        Node newNode = new Node(data, null, head);

        if(head != null){
            head.setPrev(newNode);
        }
        head = newNode;
        if(tail == null){
            tail = newNode;
        }
        length++;
    }

    public void insertEnd(int data){

        Node newNode = new Node(data);
        newNode.setNext(null);

        if(tail != null){
            tail.setNext(newNode);
            newNode.setPrev(tail);
            tail = newNode;
        }
        if(head == null){
            head = newNode;
        }

        length++;
    }

    public void removeFront(){

        if(head != null){

            head.getNext().setPrev(null);
            head = head.getNext();

        }else if(head == null){

            System.out.println("List is empty");
            return ;

        }
        length--;
    }

    public void removeEnd(){

        if(tail != null){

            System.out.println("Tail not null");
            Node temp = tail.getPrev();
            temp.setNext(null);
            tail = temp;

        }else{
            System.out.println("Tail is null");
        }
        length--;
    }

    public void printList(){
        Node temp = head;

        while(temp != null){
            System.out.print(temp.getData()+" ");
            temp = temp.getNext();
        }
        System.out.println("");
    }
}

Answer 1

Bug

    public void insertEnd(int data){

        Node newNode = new Node(data);
        newNode.setNext(null);

        if(tail != null){
            tail.setNext(newNode);
            newNode.setPrev(tail);
            tail = newNode;
        }
        if(head == null){
            head = newNode;
        }

        length++;
    }

If tail is null at the beginning, it will stay null. Like with head in insertFront, you should always set tail in insertEnd. As is, if you call insertEnd and then insertFront, it will point tail at the one inserted at the front.

    public void insertEnd(int data){
        Node newNode = new Node(data, tail, null);

        if (tail != null) {
            tail.setNext(newNode);
        }
        tail = newNode;
        if (head == null) {
            head = newNode;
        }

        length++;
    }

This way, it always sets tail to newNode.

You also never set the previous node if tail is null. But you explicitly set the next node to null. This version always sets both. It would also work to never set the next node and only set the previous node if there is one. But please don't mix the two notions. Either set everything or let everything that can default, default. Either is readable on its own. Mixed, it gets a bit confusing.

I tend to favor explicitly setting everything.

I also prefer more whitespace, so that keywords like if are separated from things like parenthetical expressions. The exception being method calls. That way if I see foo(, I know immediately that foo is a method and not some language construct.

Don't overcomplicate things

    public void removeFront(){

        if(head != null){

            head.getNext().setPrev(null);
            head = head.getNext();

        }else if(head == null){

            System.out.println("List is empty");
            return ;

        }
        length--;
    }

You check both if head is not null and if it is null. You can check just one. Further, since you return if it is null, you can do that first.

    public void removeFront() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        head = head.getNext();
        head.setPrev(null);
        length--;
    }

Now we take care of the exceptional case first, and we don't have to gate the rest of the method. Note that it would usually make more sense to throw an exception here. A Deque would throw a NoSuchElementException in that situation.

If we switch the order of the statements, we don't have to write head.getNext() twice.

It's no longer confusing that we decrement length outside the if structure but only actually reach that code in one branch.

Bug 2

    public void removeEnd(){

        if(tail != null){

            System.out.println("Tail not null");
            Node temp = tail.getPrev();
            temp.setNext(null);
            tail = temp;

        }else{
            System.out.println("Tail is null");
        }
        length--;
    }

You decrement length even if there's nothing there.

    public void removeEnd() {
        if (tail == null) {
            System.out.println("Tail is null");
            return;
        }

        System.out.println("Tail not null");

        tail = tail.getPrev();
        tail.setNext(null);
        length--;
    }

This should follow the same pattern as removeFront.

Implement an interface

Note that a Deque has a similar API to this. Consider implementing that interface for compatibility reasons. Of course, you may find that that is unnecessary for what you need.

Answer 2

Code organisation

In class Node the constructos are at the end of the class. Since the code they contain is executed before any other (non static) code in the class they should be placed on top of the class, right after the member variables declarations.

Constructors

Your class Node has 3 Constructors with different Arguments.
One of the Constructors (Node(){ }) creates an invalid node object (it is invalid because the node object has an random value, which is 0 for a reason the user of this constructor cannot see.
There is one constructor where you can set other nodes as previous/next, but your LinkedList class is not using them. Also there are setter methods for previous/next, so that this constructor is somehow "duplicated" feature.

IMHO the Node class should have only one constructor Node(int data).

insertEnd

This method will never set tail.
tail = newNode; should be moved out of the if block right before length++; since the new node added by this method will always be the tail.

This problem may have been avoided by writing unittest...

removeFront

   if(head != null){
      //...
    }else if(head == null){

the additional if after else is useless, since it is exactly the contition the else will be executed, so it cannot be false here.

 if(head != null){
   }else /* removed */{
        return ;
   }
   length--;

length--; should be inside the if block.
This is because it should be executed under the same condition and it would avoid the additional exit using the explicit return statement within the else block.

IMHO there should be no if at all here. if there is no head, then this is an unexpected condition and this justifies to use try/catch here:

    try{
        head.getNext().setPrev(null);
        head = head.getNext();
        length--;
    }catch(NullPointerException npe){
        System.out.println("List is empty");
    }

Answer 3

I have added my comments directly in the code:

// package names are advised to be written in lower case. Plus, they are
// supposed to reflect the domain name of your organization: something like
// com.yourdomain.util
package Double_LinkedList;

// Even if you declare 'Node' as package private, it is exposed outside the 
// package through public methods of 'DoubleLinkedList'.
class Node{

    // Since you use getters and setters for these three fields, it would make
    // sense to declare all three as 'private':
    int data;
    Node prev;
    Node next;

    void setData(int data){
        this.data = data;
    }

    int getData(){
        return data;
    }

    void setPrev(Node prev){
        this.prev = prev;
    }

    void setNext(Node next){
        this.next = next;
    }

    Node getPrev(){
        return prev;
    }

    Node getNext(){
        return next;
    }

    Node(int data, Node prev, Node next){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    Node(int data){
        this.data = data;
    }

    Node() {}
}

public class DoubleLinkedList{

    // Pointless. Reference members of an object are assigned 'null' by default.
    private Node head = null;
    private Node tail;

    private int length;

    // Wrong. The better approach would be 'getFirst' returning the DATUM of the
    // head node.
    public Node getHead(){
        return head;
    }

    // Same as above. Better return the datum of the tail node.
    public Node getTail(){
        return tail;
    }

    // Once again, do not expose the internals of a class.
    public int getData(Node node){
        return node.getData();
    }

    public int getLength(){
        return length;
    }

    public void insertFront(int data){

        Node newNode = new Node(data, null, head);

        if(head != null){
            head.setPrev(newNode);
        }
        head = newNode;
        if(tail == null){
            tail = newNode;
        }
        length++;
    }

    public void insertEnd(int data){

        Node newNode = new Node(data);
        // Pointless:
        newNode.setNext(null);

        if(tail != null){
            tail.setNext(newNode);
            newNode.setPrev(tail);
            tail = newNode;
        }
        if(head == null){
            head = newNode;
        }

        length++;
    }

    public void removeFront(){

        if(head != null){

            head.getNext().setPrev(null);
            head = head.getNext();

        }else if(head == null){
            // Throwing 'NoSuchElementException' would be in order. Plus, 
            // Do NOT output text in algorithms/data structures. It makes them
            // pretty much abusive for the client programmer.
            System.out.println("List is empty");
            return ;

        }
        length--;
    }

    public void removeEnd(){

        if(tail != null){

            System.out.println("Tail not null");
            Node temp = tail.getPrev();
            temp.setNext(null);
            tail = temp;

        }else{
            System.out.println("Tail is null");
        }
        length--;
    }

    // Override toString() instead here:
    public void printList(){
        Node temp = head;

        while(temp != null){
            System.out.print(temp.getData()+" ");
            temp = temp.getNext();
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        // Throws 'NullPointerException' which proves that your implementation
        // is not correct.
        DoubleLinkedList list = new DoubleLinkedList();
        list.insertEnd(0);
        list.removeFront();
    }
}

Alternative implementation

You may consider the following:

package com.stackexchange.codereview.util;

import java.util.NoSuchElementException;

public final class IntLinkedList {

    private static final class Node {

        int datum;
        Node prev;
        Node next;

        Node(int datum) {
            this.datum = datum;
        }
    }

    private Node head;
    private Node tail;
    private int size; 

    public void addFirst(int datum) {
        Node newNode = new Node(datum);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }

        ++size;
    }

    public void addLast(int datum) {
        Node newNode = new Node(datum);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }

        ++size;
    }

    public int removeFirst() {
        checkListNotEmpty();
        Node removed = head;
        Node newHead = head.next;
        head = newHead;

        if (newHead != null) {
            newHead.prev = null;
        } else {
            tail = null;
        }

        --size;
        return removed.datum;
    }

    public int removeLast() {
        checkListNotEmpty();
        Node removed = tail;
        Node newTail = tail.prev;
        tail = newTail;

        if (newTail != null) {
            newTail.next = null;
        } else {
            head = null;
        }

        --size;
        return removed.datum;
    }

    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        String separator = "";
        Node node = head;

        while (node != null) {
            sb.append(separator).append(node.datum);
            separator = ", ";
            node = node.next;
        }
        return sb.append("]").toString();
    }

    private void checkListNotEmpty() {
        if (size == 0) {
            throw new NoSuchElementException("Removing from an empty list.");
        }
    }

    public static void main(String[] args) {
        IntLinkedList list = new IntLinkedList();

        System.out.println("Adding to the tail...");

        for (int i = 0; i < 5; ++i) {
            System.out.println(list);
            list.addLast(i);
        }

        System.out.println(list);
        System.out.println("Clearing the list...");

        list.clear();

        System.out.println("Adding to the head...");

        for (int i = 0; i < 5; ++i) {
            System.out.println(list);
            list.addFirst(i);
        }

        System.out.println(list);
        System.out.println("Done adding to the head.");
        System.out.println("Remove 2 elements from the head...");

        for (int i = 0; i < 2; ++i) {
            list.removeFirst();
            System.out.println(list);
        }

        System.out.println("Remove the rest from the tail...");

        while (list.size() > 0) {
            list.removeLast();
            System.out.println(list);
        }
    }
}

Note that your implementation has a bug; just run the main() in the code I annotated with comments.

Hope that helps.