Doubly Linked List, Insert Before A Given Node in Java

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.

Answer

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