Doubly Linked List, Insert Before A Given Node in Java

Question

The method not working:

public void insert_before_node(Node givenNode, int data) {
 Node newNode = new Node(data);
 newNode.prev = givenNode.prev;
 givenNode.prev = newNode;
 newNode.next = givenNode;
 if(newNode.prev != null)
 newNode.prev.next = newNode;
}

Another add method which is working:

public void insert_front(int data) {
 Node newNode = new Node(data);
 newNode.next = head;
 newNode.prev = null;
 if(head != null)
 head.prev = newNode;
 head = newNode;
}

A print method to debug:

public void print() {
 Node n = head;
 while(n != null){
 System.out.println(n.data);
 n = n.next;
 }
}

DoublyLinkedList class:

public class DoublyLinkedList {
 static class Node {
 int data;
 Node next;
 Node prev;
 Node(int data) {
 this.data = data;
 this.next = null;
 this.prev = null;
 }
 }
 Node head;
 DoublyLinkedList() {
 this.head = null;
 }
public static void main(String[] args) {
 DoublyLinkedList ll = new DoublyLinkedList();
 ll.insert_front(0);
 ll.insert_before_node(ll.head, 100);
 ll.print();
}
}

LinkedList and Node implementations are very straightforward. Find here: https://www.geeksforgeeks.org/doubly-linked-list/

I first create a linkedlist, insert_front() a value to make the head not null, then use the method above to insert something else. Insertion to front, end, after a node are working, however, this insert_before_node() is not working. What I have inserted with this method is not appears on my print.

I draw on a paper too, still couldn't find the problem.

The geeksforgeeks link also has no java implementation for this method.

• Robert Kock: Are you sure your insert_front() is working? How does the caller know about the new head of the list?
• StephaneM: The last line of insert_front is useless (head = newNode;) This method should return the new head, otherwise how do you keep track of the new head? You should show us your test code.
• Melih: Sorry, I'm updating the question code. I just wanted to minimize my code.

Answer 1

Your code is working, apart from the assignment of head in insert_front(Node,int) method, I think you forgot this. before that.

Plus, maybe you would need to

• remove the head argument in insert_front method (it's the head of the dll, it has a class member for that),
• remove the underscores (not Java good practice, Sonar would complain)
• return the nodes you create so you can later reference them (and possibly create a fluent API)

A basic rework would look like this MVP:

import java.util.Objects;
public class DoubleLinkLists {
 public static void main(String[] args) {
 DoubleLinkedList dll = new DoubleLinkedList();
 DoubleLinkedList.Node node5 = dll.insertInFront(5);
 DoubleLinkedList.Node node4 = dll.insertInFront(4);
 DoubleLinkedList.Node node2 = dll.insertInFront(2);
 DoubleLinkedList.Node node1 = dll.insertInFront(1);
 DoubleLinkedList.Node node3 = dll.insertBefore(node4, 3);
 System.out.println(dll);
 }
 public static class DoubleLinkedList {
 Node head;
 @Override
 public String toString() {
 Node current = head;
 StringBuilder sb = new StringBuilder();
 while (current != null) {
 sb.append(current.data)
 .append(" ");
 current = current.next;
 }
 return sb.toString();
 }
 public Node insertBefore(Node givenNode, int data) {
 Node newNode = new Node(data);
 newNode.prev = givenNode.prev;
 givenNode.prev = newNode;
 newNode.next = givenNode;
 if (newNode.prev != null) {
 newNode.prev.next = newNode;
 }
 return newNode;
 }
 public Node insertInFront(int data) {
 Node newNode = new Node(data);
 newNode.next = head;
 newNode.prev = null;
 if (head != null) {
 head.prev = newNode;
 }
 head = newNode;
 return newNode;
 }
 public static class Node {
 int data;
 Node prev;
 Node next;
 Node(int d) {
 data = d;
 }
 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (o == null || getClass() != o.getClass()) return false;
 Node node = (Node) o;
 return data == node.data;
 }
 @Override
 public int hashCode() {
 return Objects.hash(data);
 }
 }
 }
}

• Melih: I have updated the code, I just didn't want to share all the code because then nobody reads it(I have already a down-vote and I have no idea why I get a down-vote). However, while trying to trim the code, I made some mistakes. So I added all the code I have used. I was just trying to implement a simple DLL so I didn't care about very clean coding, but I will keep these suggestions in my hand.

Answer 2

I edit the code for more readable.

public void insert_before_node(Node next, int data) {
 Node newNode = new Node(data);
 Node prev = next.prev;
 //left to right
 prev.next = newNode;
 newNode.next = next;
 //traverse right to left
 next.prev = newNode;
 newNode.prev = prev;
}

I assume the next and prev is also not null.

By the way, you should add more condition to detect null(next and prev) in insert_before_node. Please update the result and hope it help.

• Melih: It's working, null detection is the problem as I see