Inserting data in a sorted Circular Linked List

Question

I want to add a given data into an already sorted Circular Linked List such that the resultant list is also sorted. The class for the Node is already provided which have public int data and public Node next as the class members.

A function addNode(Node head) is to be implemented which will insert a known data(9) into the list. Node head is the head pointer of the circular linked list.

I have considered the following cases

When the list is empty, create the Node, put its data as 9 and refer its next to itself. Make the newly created node as the head.
When the list contains only one item. Modify the first node's next pointer to point to the new node and new node's next pointer to the given head node. Make the head node point to the node whose value is the lowest.
When the inserted data is the smallest among all i.e it will be smaller than the data of the node which the head node points to and it will be inserted before the Head node.
When the data is to be inserted between two nodes. So I am using the while loop which will find the node before which the new data will be inserted and modifying the node's next pointer accordingly.

When I am submitting the code, it is somehow failing one test case which I am not able to find out. Can someone help me in finding out the condition that I might be overlooking in my logic.

Below is the implemented code:

public static Node addElement(Node input1)
{
    //Write code here
Node result = new Node();
Node current = new Node();
current = input1;

Node value = new Node();
value.data = 10;

if(current == null){
    value.next = value;
    result = value;
}
else if(current.next == current){
    value.next = input1;
    current.next = value;
    result = current.data < value.data ? current : value;
}
else if(value.data < current.data){
    while(current.next != input1)
        current = current.next;     

    current.next = value;
    current.next.next = input1;
    result = current.next;
}   
else{
    while(current.next != input1 && current.next.data <= value.data)
        current = current.next;

    Node currentNext = current.next;
    current.next = value;
    current.next.next = currentNext;
    result = input1;
}

return result;
}

What do you mean it is failing a test case which you cannot find out? Is there a specific set of data for which it is failing? — Christina
@Christina I suppose it's homework that is checked by a number of JUnit tests. Looks like the OP doesn't know himself which test is failed. — svz
I think there is an error in your logic for case 2. What if your new node is the lowest value? You said that the new node points to the head and the head to the node with the lowest value. You would then lose the reference to your old node. Edit: scratch the rest, I just saw that input1is supposed to be the head node. — Sebastian_H
This is strange, I did my own implementation and did a few manual test. I then took your code and made the same tests. The results are identical. All the basic operations should work correctly. Is there maybe something you have not considered. For example, should the list accept duplicates? If yes, in which order should they be. Should the duplicate be inserted before or after the existing elements. Are you absolutely sure that it doesn't matter if your data is 9 or 10? If the order is examined or the list checked for a specific number, the test might fail. Otherwise I can't see a problem. — Sebastian_H
As a side note you don't really need all thoses cases you are taking into account. The only cases you really need are 1. list empty, 2. list not empty (this will actually merge cases 2-4 above together). Perhaps by minimising the cases you are trying to handle and simplifying your code you will find something we're not seeing right now (for what it's worth I can't see any errors in your code above either). — Christina

Anuj Garg Anuj Garg · Accepted Answer · 2014-12-10T19:52:02

void sortedInsert(struct node** head_ref, struct node* new_node)
{
  struct node* current = *head_ref;

  // Case 1 of the above algo
  if (current == NULL)
  {
     new_node->next = new_node;
     *head_ref = new_node;
  }

  // Case 2 of the above algo
  else if (current->data >= new_node->data)
  {
    /* If value is smaller than head's value then
      we need to change next of last node */
    while(current->next != *head_ref)
        current = current->next;
    current->next = new_node;
    new_node->next = *head_ref;
    *head_ref = new_node;
  }

  // Case 3 of the above algo
  else
  {
    /* Locate the node before the point of insertion */
    while (current->next!= *head_ref && current->next->data < new_node->data)
      current = current->next;

    new_node->next = current->next;
    current->next = new_node;
  }
}

Inserting data in a sorted Circular Linked List

1 Answers