My implementation of a doubly linked list

Question

Here is my implementation of a doubly linked list. Basic functionality seems to be working fine. Please let me know your comments on the coding style and algo.

DoublyLinkedListNode.java

public class DoublyLinkedListNode<T>
{
    private T DataItem;
    private DoublyLinkedListNode<T> nextNode;
    private DoublyLinkedListNode<T> prevNode;

    public DoublyLinkedListNode(DoublyLinkedListNode<T> prevNode, T DataItem, DoublyLinkedListNode<T> nextNode)
    {
        this.DataItem=DataItem;
        this.nextNode=nextNode;
        this.prevNode=prevNode;
    }

    public void setNextNode(DoublyLinkedListNode<T> nextNode)
    {
        this.nextNode=nextNode;
    }

    public DoublyLinkedListNode<T> getNextNode()
    {
        return nextNode;
    }

    public void setDataItem(T DataItem){
        this.DataItem=DataItem;
    }

    public T getDataItem()
    {
        return DataItem;
    }

    public void setPrevNode(DoublyLinkedListNode<T> prevNode)
    {
        this.prevNode=prevNode;
    }

    public DoublyLinkedListNode<T> getPrevNode()
    {
        return prevNode;
    }
}

MyDoublyLinkedList.java

public class MyDoublyLinkedList<T>{
    private DoublyLinkedListNode<T> head;
    private int size;

    public MyDoublyLinkedList(){
        head=new DoublyLinkedListNode<T>(null,null,null);
    }

    public void prependElement(T data){
        addElementAtIndex(0,data);
    }

    public void addElementAtIndex(int index, T data){
        if(index == 0){
            DoublyLinkedListNode<T> newNode=new DoublyLinkedListNode<T>(head,data,head.getNextNode());
            head.setNextNode(newNode);
            size++;
        }else{
            DoublyLinkedListNode<T> prevNode=nodeAtIndex(index-1);
            if(prevNode != null){
                DoublyLinkedListNode<T> nextNode=prevNode.getNextNode();
                DoublyLinkedListNode<T> newNode=new DoublyLinkedListNode<T>(prevNode,data,nextNode);
                prevNode.setNextNode(newNode);
                nextNode.setPrevNode(newNode);
                size++;
            }else{
                System.err.println("Index greater than the size of the list");
            }
        }
    }

    // delete node at the beginning of the list
    public void removeElement(){
        removeElementAtIndex(0);
    }

    // delete a node at index
    public void removeElementAtIndex(int index){
        if(index == 0)
        {
            DoublyLinkedListNode<T> toBeDeletedNode=head.getNextNode();
            if(toBeDeletedNode != null){
                DoublyLinkedListNode<T> nextNode=toBeDeletedNode.getNextNode();
                head.setNextNode(nextNode);
                nextNode.setPrevNode(head);
                toBeDeletedNode.setNextNode(null);
                toBeDeletedNode.setPrevNode(null);
                size--;
            }else{
                System.out.println("No nodes to be deleted");
            }
        }else{
            DoublyLinkedListNode<T> prevNode=nodeAtIndex(index-1);
            if(prevNode != null){
                DoublyLinkedListNode<T> targetNode=prevNode.getNextNode();
                DoublyLinkedListNode<T> nextNode=targetNode.getNextNode();
                targetNode.setNextNode(null);
                targetNode.setPrevNode(null);
                prevNode.setNextNode(nextNode);
                nextNode.setPrevNode(prevNode);
                size--;
            }else{
                System.err.println("Index greater than the size of the list");
            }
        }
    }

    // display all nodes data
    public void displayAllElements(){
        DoublyLinkedListNode<T> nodes=head.getNextNode();
        int i=0;
        while(nodes != null){
            System.out.println("Node "+i+" : "+nodes.getDataItem().toString());
            nodes=nodes.getNextNode();
            i++;
        }
    }

    // reverse order of linked list
    public void reverse(){
        DoublyLinkedListNode<T> currentNode=head.getNextNode();
        DoublyLinkedListNode<T> prevNode;
        DoublyLinkedListNode<T> nextNode;
        while(currentNode != null){
            nextNode=currentNode.getNextNode();
            prevNode=currentNode.getPrevNode();
            currentNode.setNextNode(prevNode);
            currentNode.setPrevNode(nextNode);
            if(currentNode.getNextNode() == head){
                currentNode.setNextNode(null);
            }
            if(currentNode.getPrevNode() == null){
                currentNode.setPrevNode(head);
                head.setNextNode(currentNode);
                currentNode=null;
            }else{
            currentNode=currentNode.getPrevNode();
            }
        }
    }

    public int searchKey(T key){
        T data=null;
        int i=0;
        DoublyLinkedListNode<T> node=head.getNextNode();
        Boolean foundFlag=false;
        while(node != null){
            data=node.getDataItem();
            if(data.equals(key)){
                return i;
            }
            i++;
            node=node.getNextNode();
        }
        return -1;
    }

    // return data item at particular node
    public T dataAtIndex(int index)
    {
        DoublyLinkedListNode<T> nodes=nodeAtIndex(index);
        if(nodes != null){
            return nodes.getDataItem();
        }else{
            return null;
        }
    }

    // return node at particular index
    private DoublyLinkedListNode<T> nodeAtIndex(int index){
        if(index<0){
            return null;
        }else{
            DoublyLinkedListNode<T> nodes=head.getNextNode();
            int i=0;
            while(i < index && nodes != null){
                nodes=nodes.getNextNode();
                i++;
            }
            return nodes;
        }
    }

    public int size(){
        return size;
    }

}

Answer 1

Advice 1

I suggest you hide the node implementation as an private static inner class. After all, making it a public class does not buy you much.

Advice 2

Add the tail field referencing the very last node in the list. This will allow more straightforward implementation of the reversal method, which will just swap the elements instead of restructuring the entire list. Also, it will allow more efficient access and search by index: if the input index is closer to zero than it is to size, start counting from the head forwards; otherwise, start counting from the tail backwards. This allows a speed up by the factor of two, since you reach the nodes via shorter "paths."

Advice 3

System.out.println() is a no-no in algorithmic methods. Think what happens to the standard output on large lists.

Advice 4

displayAllElements; consider implementing toString() instead.

Advice 5

The clear won't hurt either and is easy to implement.

Summa summarum

All in all, I had this in mind:

import java.util.Objects;
import java.util.Scanner;

public class MyDoublyLinkedList<T>{

    // I would hide the node implementation as an inner static private class:
    // Keyword 'static' buys you more space as the objects of an inner static 
    // class do not hold an implicit reference to the object of enclosing class.
    private static final class DoublyLinkedListNode<T> {
        // I am not 100% sure that accessing the fields of a node is more 
        // efficient than via getters/setters, but I am sure that this is not 
        // slower than using getters/setters.
        T element;
        DoublyLinkedListNode<T> prev;
        DoublyLinkedListNode<T> next;

        DoublyLinkedListNode(T element) {
            this.element = element;
        }
    }

    private DoublyLinkedListNode<T> head;
    // Having a tail reference will simplify the reversal operation, and will
    // making the access by indices more efficient:
    private DoublyLinkedListNode<T> tail;
    private int size;

    public MyDoublyLinkedList(){
        // Using a sentinel node will make life harder; remove it.
        //head=new DoublyLinkedListNode<T>(null,null,null);
    }

    public void prependElement(T data){
        addElementAtIndex(0, data);
    }

    public void addElementAtIndex(int index, T data){
        // Checking the validity of the access index allows for more 
        // straightforward code:
        checkInsertionIndexWithinBounds(index);
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(data);

        if (index == 0) {
            newNode.next = head;

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

            head = newNode;
        } else {
            DoublyLinkedListNode<T> beforeNode;

            if (index < size / 2) {
                beforeNode = head;

                for (int i = 1; i < index; ++i) {
                    beforeNode = beforeNode.next;
                }
            } else {
                beforeNode = tail;

                for (int i = size - index - 1; i > 0; --i) {
                    beforeNode = beforeNode.prev;
                }
            }

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

        if (size == 0) {
            tail = newNode;
        }

        ++size;
    }

    private void checkInsertionIndexWithinBounds(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The input index is negative: " + index);
        }

        if (index > size) {
            throw new IndexOutOfBoundsException(
                    "The input index is too large: " + index + ". Should be " +
                    "at most " + size + ".");
        }
    }

    // delete node at the beginning of the list
    public void removeElement(){
        removeElementAtIndex(0);
    }

    // delete a node at index
    public void removeElementAtIndex(int index){
        checkListNotEmpty();
        checkRemovalIndexWithinBounds(index);
        DoublyLinkedListNode<T> targetNode = nodeAtIndex(index);

        // Unlink the node:
        if (targetNode.prev != null) {
            targetNode.prev.next = targetNode.next;
        } else {
            head = targetNode.next;
        }

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

        --size;
    }

    private void checkRemovalIndexWithinBounds(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The input index is negative: " + index + ".");
        }

        if (index >= size) {
            throw new IndexOutOfBoundsException(
                    "The input index is too large: " + index + ". Must be at " +
                    "least " + (size - 1) + ".");
        }
    }

    private void checkAccessIndexWithinBounds(int index) {
        checkRemovalIndexWithinBounds(index);
    }

    private void checkListNotEmpty() {
        if (size == 0) {
            throw new IllegalStateException("The list is empty.");
        }
    }

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

        for (DoublyLinkedListNode<T> node = head; 
                node != null; 
                node = node.next) {
            sb.append(separator).append(node.element);
            separator = ", ";
        }

        return sb.append("]").toString();
    }

    public void reverse() {
        DoublyLinkedListNode<T> left = head;
        DoublyLinkedListNode<T> right = tail;

        while (left != right) {
            T tmp = left.element;
            left.element = right.element;
            right.element = tmp;

            left = left.next;

            if (left == right) {
                return;
            }

            right = right.prev;
        }
    }

    public int searchKey(T key) {
        DoublyLinkedListNode<T> node = head;
        int index = 0;

        while (node != null) {
            if (Objects.equals(key, node.element)) {
                return index;
            }

            index++;
            node = node.next;
        }

        return -1;
    }

    public T get(int index)
    {
        checkListNotEmpty();
        checkAccessIndexWithinBounds(index);
        return nodeAtIndex(index).element;
    }

    // return node at particular index
    private DoublyLinkedListNode<T> nodeAtIndex(int index){
        DoublyLinkedListNode<T> targetNode;

        // Find the node to remove:
        if (index < size / 2) {
            targetNode = head;

            for (int i = 0; i < index; ++i) {
                targetNode = targetNode.next;
            }
        } else {
            targetNode = tail;

            for (int i = size - 1; i > index; --i) {
                targetNode = targetNode.prev;
            }
        }

        return targetNode;
    }

    public int size(){
        return size;
    }

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        MyDoublyLinkedList<Integer> list = new MyDoublyLinkedList<>();

        while (true) {
            System.out.print("> ");
            String cmd = scanner.next().trim().toLowerCase();

            try {
                switch (cmd) {
                    case "quit":
                        System.exit(0);
                        break;

                    case "reverse":
                        list.reverse();
                        break;

                    case "print":
                        System.out.println(list);
                        break;

                    case "get":
                        int index = scanner.nextInt();
                        System.out.println(list.get(index));
                        break;

                    case "remove":
                        index = scanner.nextInt();
                        list.removeElementAtIndex(index);
                        break;

                    case "remove_front":
                        list.removeElement();
                        break;

                    case "prepend":
                        list.prependElement(scanner.nextInt());
                        break;

                    case "add":
                        list.addElementAtIndex(scanner.nextInt(),
                                               scanner.nextInt());
                        break;

                    case "search":
                        System.out.println(list.searchKey(scanner.nextInt()));
                        break;

                    case "size":
                        System.out.println(list.size());
                        break;

                    case "clear":
                        list.clear();
                        break;

                    default:
                        System.out.println("Unknown command: " + cmd);
                }
            } catch (Exception ex) {
                System.out.println("Oops! " + ex.getMessage());
            }
        } 
    }
}

Hope that helps.