java-Doubly Linked List logic

Question

I am trying to understand a java implementation for doubly linked list. I have the following code:

public class DLLNode{
    //define variables
    public int info;
    public DLLNode next;
    public DLLNode prev;


    //Passing constructors
    public DLLNode(int i){
        info = i;
        next = prev = null;
    }

    public DLLNode(int i, DLLNode n, DLLNode p){
        info = i;
        next = n;
        prev = p;
    }
}

And the following:

public class DLL {
    DLLNode head;
    DLLNode tail;

    public DLL(){
        head = tail = null;
    }

    //Check whether list is empty or not
    public boolean isEmpty(){
        return head == null;
    }

//Insert element to head
    public void insertHead(int n){
        if(isEmpty()){
            head = tail = new DLLNode(n);
        }
        else{
            head = new DLLNode(n, null, head);
            head.next.prev = head;
        }
    }

Only the insertHead() method is show here for clarity.

Now I understand that if someone runs insertHead(10) in the main method, if the list is empty; a new object forms and both head and tail reference variables points to that object.

What I don't understand is if list is NOT empty; the code piece is very confusing.

head = new DLLNode(n, null, head);
head.next.prev = head; //really confusing, what does this mean??

1)What I understand is n=10, null and head are passed to constructor: public DLLNode(int i, DLLNode n, DLLNode p).Then the assignment info=10, next=null and prev=head occurs. One problem is that, if at least one item is available on the list, and I add another item to HEAD position, shouldn't "next" point to the previous head, while "prev" point to null?? Faulty code perhaps??

2)What does the code

head.next.prev = head;

mean?? And why is it necessary?? I really don't get that logic...:(

Any help would be appreciated..

It seems that you are right, and that it should have been new DLLNode(n, head, null) instead. Did you try to run it? — RealSkeptic
It compiles for sure, but the logic was confusing with the method name used. That/s what worried me, I was afraid I was missing something trivial. — user3889963
Compiles, yes. Runs - not for more than one element. This kind of thing is a good place for experimentation. Play around with it in a debugger and you'll be more confident about whether or not it's good code. — RealSkeptic
@maraca - because you pass null in the second parameter and the head in the third parameter. The second parameter goes to the next - so next becomes null, and the third parameter goes to the prev, which will become the old head. Since next is null, head.next.prev will throw an NPE. — RealSkeptic

M A M A · Accepted Answer · 2015-05-23T10:48:54

This implementation is wrong. The insertHead would throw a NullPointerException if called more than once:

 head = new DLLNode(n, null, head);
 head.next.prev = head;  // head.next is null because of the above call

Instead, the implementation of the insert should be:

public void insertHead(int n) {
    if (isEmpty()) {
        head = tail = new DLLNode(n);
    } else {
        head = new DLLNode(n, head, null);
        head.next.prev = head;
    }
}

Inserting the node at head is a two-step action:

Create the node, set its next pointer to point to the current head and assign it to be the new head of the list.
Set the previous pointer of the old head to the new head. That's what the statement head.next.prev = head does.

java-Doubly Linked List logic

2 Answers