CODEWITHSUNDEEP
javadoubly-linked-list
user14307616
user14307616

Reputation:

Doubly linked list: adding a node at front. From geeksforgeeks (java code)

This is a code that adds a node at the front of the doubly linked list. What I don't understand here is step 4. Right here, it appears to me that it's storing the address of the new_Node into the variable head.prev. The variable head.prev will now hold new-node. This doesn't even make sense because the variable 'head' will also hold new_node. So now we have two variables pointing to the same address.

Even if, in any case, this code was meant to say, new_node = head.prev, that also does not make sense, because the head.prev will be null at this point, and new_node will then point to a null.

// Class for Doubly Linked List public class DLL { Node head; // head of list

/* Doubly Linked list Node*/
class Node { 
    int data; 
    Node prev; 
    Node next; 

    // Constructor to create a new node 
    // next and prev is by default initialized as null 
    Node(int d) { data = d; } 
} 
// Adding a node at the front of the list 
public void push(int new_data) 
{ 
/* 1. allocate node  
* 2. put in the data */
    Node new_Node = new Node(new_data); 

/* 3. Make next of new node as head and previous as NULL */
new_Node.next = head; 
new_Node.prev = null; 

/* 4. change prev of head node to new node */
    if (head != null) 
        head.prev = new_Node; 

/* 5. move the head to point to the new node */
    head = new_Node; 
}

}

Upvotes: 3

Views: 3696

Answers (3)

Loris Securo
Loris Securo

Reputation: 7638

The step 4 is needed to connect the prev of the old head to the new head.

This is the situation after step 3:

after step 3

Then after step 4 the prev of the old head (which was null) is set to point to the new head:

after step 4

And then step 5 makes head point to the new node (the new head):

after step 5

Upvotes: 3

Oleg Cherednik
Oleg Cherednik

Reputation: 18245

public class DLL {

    private Node head;
    private Node tail;

    public void addFirst(int val) {
        Node node = new Node(val);

        if (head == null)
            tail = node;
        else {
            node.next = head;
            head.prev = node;
        }

        head = node;
    }

    public void addLast(int val) {
        Node node = new Node(val);

        if (tail == null)
            head = node;
        else {
            tail.next = node;
            node.prev = tail;
        }

        tail = node;
    }

    private static final class Node {

        private final int val;
        private Node prev;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}

Upvotes: 0

Christian H. Kuhn
Christian H. Kuhn

Reputation: 355

If head.prev != null then head is not the first element of the list. This should be checked as a pre-condition, and an IllegalStateException should be thrown. Further processing of the insertion is senseless as the pointer to the first position must be restored.

After step 3, the new_node setup is complete, and the new_node is linked unidirectional by new_node.next to the former first, now second element head. To make the double-link complete, head.prev must be set to the new predecessor head. That is what step 4 does if you omit the if.

Upvotes: 0

Related Questions