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
– RealSkeptic, Commented May 23, 2015 at 10:47
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
– user3889963, Commented May 23, 2015 at 10:52
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
– RealSkeptic, Commented May 23, 2015 at 10:53
@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
– RealSkeptic, Commented May 23, 2015 at 11:06

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

5

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.

answered May 23, 2015 at 10:48

M A

73.2k14 gold badges149 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

maraca · Accepted Answer · 2015-05-23 11:12:26Z

1

Yes you are right, but the code is exactly doing what you say (just one mistake), maybe if we use brackets it becomes clearer:

(head.next).prev = head;

We assign the node we just created to the next node. Or in other words: we update the prev reference of the old head to the new head which is necessairy because

head = new DLLNode(n, null, head);

creates a new head where previous points to null and next is the old head, but the reference of previous of the old head is still null.

You have the elements in the constructor in the wrong order (or in the call for creating the new head).

public DLLNode(int i, DLLNode p, DLLNode n) {

And it works.

edited May 23, 2015 at 11:12

answered May 23, 2015 at 10:50

maraca

9,5873 gold badges27 silver badges50 bronze badges

Collectives™ on Stack Overflow

java-Doubly Linked List logic

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related