CODEWITHSUNDEEP
javaobjectdoubly-linked-list
user3889963
user3889963

Reputation: 477

java-Doubly Linked List logic

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..

Upvotes: 4

Views: 838

Answers (2)

maraca
maraca

Reputation: 8773

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.

Upvotes: 1

M A
M A

Reputation: 72884

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:

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

Upvotes: 5

Related Questions