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

Question

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; 
} 

}

Answer 1

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

• user14307616: I absolutely got it. I actually understood it yesterday, but I look at it again today, and didn't. I mistakenly perceived 'head.prev' as an entire variable name itself, while the variable is the '.prev' that is under the current head node. Screw me. You've made it really clear to understand it further.

Answer 2

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.

Answer 3

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;
 }
 }
}