Doubly Linked List implementation not working

0
votes

I have a doubly linked list implementation as below : 

public class DoublyLinkedList<T> {
    DoublyLinkedListNode<T> head;

    public DoublyLinkedListNode<T> getHead() {
        return head;
    }

    public void setHead(DoublyLinkedListNode<T> head) {
        this.head = head;
    }

    public void addNode(DoublyLinkedListNode<T> node) {
        if(null == head) {
            head = new DoublyLinkedListNode<>(node.getData());
        }else{
            traverseAndAdd(node);
        }
    }

    private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {
         boolean isAdded = false;
    DoublyLinkedListNode<T> tempHead = head;
  do{
        if(tempHead.getNext() == null) {
            head.setNext(node);
            node.setPrev(head);
            isAdded = true;
            break;
        }

         tempHead = tempHead.getNext();
    }while(null != tempHead);

    return isAdded;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        while(null != head) {
            sb.append(head.getData());
            head = head.getNext();
        }

        return sb.toString();
    }

}

Below is my DoublyLinkedListNode class: 

public class DoublyLinkedListNode<T> {

    T data;
    DoublyLinkedListNode<T> prev;
    DoublyLinkedListNode<T> next;

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

    public T getData() {
        return data;
    }

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

    public DoublyLinkedListNode<T> getPrev() {
        return prev;
    }

    public void setPrev(DoublyLinkedListNode<T> prev) {
        this.prev = prev;
    }

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

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

Now when I create an instance of DoublyLinkedList and try to add a node to it somehow my head instance variable is always null.

Even though i am initializing it in addNode method its always null when i am trying to add the next node.

Could someone please let me know if there is any problem with this implementation.

Below is how i am adding nodes to my list: 

DoublyLinkedList<Integer> mylist = new DoublyLinkedList<>();
DoublyLinkedListNode<Integer> node1 = new DoublyLinkedListNode<>(10);
DoublyLinkedListNode<Integer> node2= new DoublyLinkedListNode<>(20);
DoublyLinkedListNode<Integer> node3 = new DoublyLinkedListNode<>(30);
DoublyLinkedListNode<Integer> node4 = new DoublyLinkedListNode<>(40);
DoublyLinkedListNode<Integer> node5 = new DoublyLinkedListNode<>(50);
DoublyLinkedListNode<Integer> node6 = new DoublyLinkedListNode<>(60);
mylist.addNode(node1);
mylist.addNode(node2);
mylist.addNode(node3);
mylist.addNode(node4);
mylist.addNode(node5);
mylist.addNode(node6);
System.out.println(mylist.toString());
2
javadoubly-linked-list
The problem that I think is that you are changing the pointer of the "head" cursor each time you "add the node" or print the list. Therefore, the header cursor lost the reference to the first item in the list. Try using a new variable cloning head. - Luis Daniel
@LuisDaniel The pointer of head cursor is not changing. Every time i add a new node head turns out to be null always. On debugging i noticed every time i do head = new DoublyLinkedListNode<>() on the very next line as well value of head shows as null. - ANKIT SRIVASTAVA
If it's null why didn't you throw null pointer exception? - Roman C
@RomanC I didnt throw null pointer because i have a explicit check to initialize it if its null. This would never throw a null pointer - ANKIT SRIVASTAVA
No, you didn't check in initialize nor in implementation. Also, don't change the value of head if it's not null. If something inside the code is going to be null when it shouldn't then you should declare null pointer exception and document it. - Roman C

2 Answers

0
votes

This works

class DoublyLinkedList <T> {

    DoublyLinkedListNode<T> head;

    public DoublyLinkedListNode<T> getHead() {
        return head;
    }

    public void setHead(DoublyLinkedListNode<T> head) {
        this.head = head;
    }

    public void addNode(DoublyLinkedListNode<T> node) {
        if (null == head) {
            head = new DoublyLinkedListNode<>(node.getData());
        } else {
            traverseAndAdd(node);
        }
    }

    private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {

        boolean isAdded = false;

        for (DoublyLinkedListNode<T> it = head; it != null; it = it.getNext()) {
            if(null == it.getNext()) {
                it.setNext(node);
                node.setPrev(it);
                isAdded = true;
                break;
            }
        }

        return isAdded;
    }

    @Override
    public String toString() {

        StringBuffer sb = new StringBuffer();

        for (DoublyLinkedListNode<T> it = head; it != null; it = it.getNext()) {
            sb.append(it.getData() + "\n");
        }

        return sb.toString();

    }
}

class DoublyLinkedListNode <T> {

    T data;
    DoublyLinkedListNode<T> prev;
    DoublyLinkedListNode<T> next;

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

    public T getData() {
        return data;
    }

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

    public DoublyLinkedListNode<T> getPrev() {
        return prev;
    }

    public void setPrev(DoublyLinkedListNode<T> prev) {
        this.prev = prev;
    }

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

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

public class Main {

    public static void main(String []args) {
        DoublyLinkedList<Integer> mylist = new DoublyLinkedList<>();

        DoublyLinkedListNode<Integer> node1 = new DoublyLinkedListNode<>(10);
        DoublyLinkedListNode<Integer> node2 = new DoublyLinkedListNode<>(20);
        DoublyLinkedListNode<Integer> node3 = new DoublyLinkedListNode<>(30);
        DoublyLinkedListNode<Integer> node4 = new DoublyLinkedListNode<>(40);
        DoublyLinkedListNode<Integer> node5 = new DoublyLinkedListNode<>(50);
        DoublyLinkedListNode<Integer> node6 = new DoublyLinkedListNode<>(60);
        mylist.addNode(node1);
        mylist.addNode(node2);
        mylist.addNode(node3);
        mylist.addNode(node4);
        mylist.addNode(node5);
        mylist.addNode(node6);

        System.out.println(mylist.toString());
        System.out.println(mylist.toString());
    }
}
0
votes

Your head reference is not always null, it does get initialized for adding the first node, the problem in your code in traverseAndAdd() method.

private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {
    boolean isAdded = false;
    while(null != head.getNext()) {
        if(head.getNext() == null) {
            //this code is unreachable
        }
        //why are u changing the head value
        head = head.getNext();
    }
    return isAdded;
}

so replace the function with

private void traverseAndAdd(DoublyLinkedListNode<T> node) {
    DoublyLinkedListNode<T>temp=head;
    while(null != temp.getNext()) {
        temp=temp.getNext();
    }
    temp.setNext(node);
    node.setPrev(temp);
}

another mistake, in toString() method you are assigning null value to head. head value first gets initialized but becomes null every time you call toString(). Replace the method with

public String toString() {
    StringBuffer sb = new StringBuffer();
    DoublyLinkedListNode<T>temp=head;
    while(null != temp) {
        sb.append(temp.getData());
        temp = temp.getNext();
    }
    return sb.toString();
}