Java : add node in sorted doubly linked list

Question

I am trying to add few nodes in a sorted doubly linked list. There is something wrong with the code which I am not able to figure out . I created two nodes current and prev which will help in traversing.

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node sortedInsert(Node head, int data) {
    Node newnode = new Node();
    newnode.data = data;
    Node current = head;
    Node pre = null;
    if(head == null) {
        head = newnode;
        newnode.prev = null;
    } 
    else if (head.data >= newnode.data) {
        newnode.next = head;
        head.prev = newnode;
        head = newnode;
        return newnode;
    }

    while(current!=null && current.data <= newnode.data) {
        pre = current;
        current = current.next;

        newnode.prev = pre;
        pre.next = newnode;
        newnode.next = current;
        if (current != null) {
            current.prev = newnode;
        }
    }
    return head;      
}

"There is something wrong with the code which I am not able to figure out" - what's wrong? — Leonardo Kenji Shikida
– Leonardo Kenji Shikida, Commented Jan 14, 2016 at 12:00
even I am not able to figure out. it is working only when head is null — Surya Singh
– Surya Singh, Commented Jan 14, 2016 at 12:05
What do you mean by "there is something wrong"? How do you know something is wrong - are you getting an error? What behavior are you seeing and what behavior are you expecting? That's what Leo is asking. — Ciara
– Ciara, Commented Jan 14, 2016 at 12:46
Yeah @Ciara i just tested on hackerRank and it is nit working. It is not passing any of the test cases. — Surya Singh
– Surya Singh, Commented Jan 14, 2016 at 13:16

bebbo · Accepted Answer · 2017-03-27 07:41:29Z

1

Your code has the following problems:

The if (head == null) misses a return-statement.
The else if is then an if.
Your code modifies all nodes, instead of performing one insert at the correct location, so all visited nodes are corrupted.

Here is a working version:

Node sortedInsert(Node head, int data) {
    Node newnode = new Node();
    newnode.data = data;

    // head is null -> new Node is new list
    if (head == null)
        return newnode;

    // handle special case if data < head.data
    if (data < head.data) {
        newnode.next = head;
        head.prev = newnode;
        return newnode; // newnode is the new list head
    }

    // search position in list
    Node prev = head;
    for (; prev.next != null; prev = prev.next) {
        if (prev.next.data > data)
            break;
    }

    // insert behind prev
    newnode.next = prev.next;
    if (prev.next != null) {
        prev.next.prev = newnode;
    }
    prev.next = newnode;
    newnode.prev = prev;

    return head; // head did not change
}

edited Mar 27, 2017 at 7:41

answered Jan 14, 2016 at 12:39

bebbo

2,9791 gold badge37 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Surya Singh Over a year ago

You code is great but I want to know, what's wrong with my code

Collectives™ on Stack Overflow

Java : add node in sorted doubly linked list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related