Insert into a Cyclic Sorted List

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list.


EDIT:
Thanks to dear readers Saurabh and reader who pointed out my mistake. When the list has only one value, inserting a different value would be handled by case 3), not case 1). Besides, I believe I did not explain “What is a cyclic sorted list” nicely, as this had caused some confusion. Imagine you have a sorted list, but its tail points back to its head. In other words, the list must have a minimum node, continue in a non-descending order, and eventually points back to this minimum node itself. And the only way to access the list is via aNode, which can point to any node in the list and does not necessarily point to the minimum node.

First, it is important that you understand what a cyclic linked list is. A cyclic linked list differs from a normal linked list in that its tail node points back to its head node instead of NULL.

This problem seems a little tricky because the given node is not necessarily the list’s head (ie, the node that has the smallest element). It shouldn’t take you too long to come up with an idea, but beware. There are hidden traps around the corner and you are bound to make some mistakes if you are not careful in your thoughts.

A cyclic sorted linked list. Note that the tail is pointing back to its head. The only reference to the list is a given node which can be any node in the list. Let’s say that you need to insert 4 into the list.

This is how the cyclic list becomes after inserting 4. Note that the cyclic linked list remained in sorted order.

Hints:
It is best to list all kinds of cases first before you jump into coding. Then, it is much easier to reduce the number of cases your code need to handle by combining some of them into a more generic case. Try to also list down all possible edge cases if you have time. You might discover a bug before you even start coding!

Solution:
Basically, you would have a loop that traverse the cyclic sorted list and find the point where you insert the value (Let’s assume the value being inserted called x). You would only need to consider the following three cases:

  1. prev→val ≤ x ≤ current→val:
  2. Insert between prev and current.
  3. x is the maximum or minimum value in the list:
    Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.
  4. Traverses back to the starting point:
    Insert before the starting point.

Most people have no problem getting case 1) working, while case 2) is easy to miss or being handled incorrectly. Case 3), on the other hand is more subtle and is not immediately clear what kind of test cases would hit this condition. It seemed that case 1) and 2) should take care of all kinds of cases and case 3) is not needed. Think again… How can you be sure of that? Could you come up with one case where it hits case 3)?

Q: What if the list has only one value?
A: Handled by case 1). Handled by case 3).
Q: What if the list is passed in as NULL?
A: Then handle this special case by creating a new node pointing back to itself and return.
Q: What if the list contains all duplicates?
A: Then it has been handled by case 3).

Below is the code. You could combine both negation of case 1) and case 2) in the while loop’s condition, but I prefer to use break statements here to illustrate the above idea clearer.

VN:F [1.9.22_1171]
Rating: 4.5/5 (66 votes cast)
Insert into a Cyclic Sorted List, 4.5 out of 5 based on 66 ratings

70 thoughts on “Insert into a Cyclic Sorted List

  1. zhanwu

    I don’t understand why you need case 3).

    In case of all duplicates, x (the value to be inserted) should be inserted right after the starting node, since it satisfies rule 1 immediately.

    VA:F [1.9.22_1171]
    +1
      1. zhanwu

        say we have a list 1 -> *1 -> 1 -> 1 -> (point back), and our starting point is the second 1 in the list.

        if the number to insert is not 1, then it is either a maximum or a minimum of the new list, that’s case 2.

        if the number to insert is also 1, then 1 <= 1 <= 1 which means it should be inserted right after the starting point, that's case 1

        am I missing anything?

        VA:F [1.9.22_1171]
        0
      2. zhanwu

        read it again and figured out your logic

        the code is quite clear but the explanation above is rather confusing

        VA:F [1.9.22_1171]
        0
        1. Profile photo of 1337c0d3r1337c0d3r Post author

          Thanks for your feedback, zhan.
          I agree it is quite confusing.
          The second condition:
          if ((prev->data > p->data) && (x < p->data || x > prev->data)) break;

          doesn’t exactly mean that it breaks when x is the maximum or minimum in the list.

          It only breaks when the prev element is greater than the current element (ie, the cyclic point where prev is largest and current is smallest) and x is smallest or largest element in the list if inserted.

          Like you said, it can be actually handled in only two cases, like the example you gave. But that would require you to traverse the entire list to find the cyclic point. With the code I gave above, it is more efficient and able to break early in some cases.

          VN:F [1.9.22_1171]
          0
  2. Pingback: Insert Into A Cyclic Sorted List « Programming Praxis

  3. Ratna Kumar

    I guess the second case was not handled properly in the code.Say, if I pass the value 0 to the list, it wont break as expected.

    VA:F [1.9.22_1171]
    0
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      Using your example, x = 0, prev points to 5 and p points to 1.

      if ((prev->data > p->data) && (x < p->data || x > prev->data))

      Then it will satisfy the above condition and break for the 2nd case.

      VN:F [1.9.22_1171]
      +1
      1. Ratna Kumar

        Yup, it breaks as you said.

        I think the head of the linked list should also be changed when we are inserting the new node in the beginning.

        3rd case can be in turn split into two types after the break.
        Type 1: Insert at the beginning. Code: aNode = newnode;
        Type 2: Insert at the end. code. //Do nothing.

        VA:F [1.9.22_1171]
        +1
        1. Ali

          Ratna I think you are confusing aNode as head node having the smallest value, but we have not been given a head node instead any node from that list so updating it wont do any good. In the first case setting aNode is just to create a handle to the CSL.

          VA:F [1.9.22_1171]
          0
        1. Jay

          Good luck detecting if either of these is asc or desc:
          5 (single list)
          2->3 (desc list with starting point as second element!)

          How the data is structured is outside the scope of this function itself. If you wanted to do this, you’d need your function to take this as an input (eg a function pointer).

          VA:F [1.9.22_1171]
          0
  4. Saurabh

    What if the list has only one value?
    Handled by case 1).

    Isn’t it actually handled by case 3 ? What if i have a List with one value say “4” and I want to add “3” or “5” to the list.

    VA:F [1.9.22_1171]
    +1
  5. fatalerror

    “if ((prev->data > p->data) && (x data || x > prev->data))”

    can’t it just be
    ” if ((prev->data > p->data)) ”
    Right half condition serves no purpose in a circular linked list,
    am i wrong ?
    Thank u.

    VA:F [1.9.22_1171]
    0
    1. Jay

      Consider the list:
      5 6 7 1 2

      Just because 7 is greater than 1 doesn’t mean you’re ready to insert 3. Only the max or min value should be inserted where the tail meets the head, so you need to keep going.

      VA:F [1.9.22_1171]
      0
  6. A_Kareem

    hi, 1337c0d3r
    I am really excited with your great thinking and appreciate your efforts.
    I would like to discuss this with you, I think you need to add these two lines to the endof your function to work properly to change the head or list pointer in case of you insert before the head,

    if ((x data) && (p == aNode))
    {
    aNode = newNode;
    }

    Regards

    VA:F [1.9.22_1171]
    0
  7. jr

    what about this

    void Insert(strcut node** source, int num)
    {

    struct node* newNode = maclloc(sizeOf(struct node));
    newNode->num = num;

    if (*souce == NULL || *(source->num) >= num)
    {
    nwNode->next = *source;
    *source = newNode;
    }
    else
    {
    struct node* current = *source

    while(current->next != NULL && current->next->num > num)
    {
    current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;
    }

    }

    VA:F [1.9.22_1171]
    0
  8. reader

    The code posted is wrong.It does not handle the case of a list with 1 node and trying to insert a value less than the one in the existing (only) node of the list. Example: list with just 1 node (pointing to itself) with value 2. Try to insert value 1.The code will insert a new node after the existing one breaking the sorted order.

    VA:F [1.9.22_1171]
    0
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      hi reader,
      thanks for your comment and pointing out your concern. Since the cyclic sorted list doesn’t have a head (it is only referred by aNode (which can be any node) in the list).

      Therefore, by inserting a smaller value before aNode (any node), it doesn’t break the sorted order per say.

      Think of the following list, which is 5->1->3 [3 points back to 5] where aNode is pointing to 5, it doesn’t break the sorted order.

      VN:F [1.9.22_1171]
      0
      1. reader

        I see what you mean. But when you would build the cyclic list, inserting the elements in sorted order, the code would have a reference of the first node i.e. the node containing the min value. Wouldn’t this be “treated” in the code as the head of the list?

        VA:F [1.9.22_1171]
        0
        1. Profile photo of 1337c0d3r1337c0d3r Post author

          Yes, the smallest value would be the head. For your example with a value of 2, inserting 1 will satisfy the condition prev→val ≤ x ≤ current→val: break the loop, and 1’s next will point to 2, and 2’s next point back to 1. This seem correct to me.

          Are you suggesting that in this case, we should update the head to point to 1?

          VN:F [1.9.22_1171]
          0
  9. reader

    At this point you are incorrect. None of the 2 conditions are satisfied when we try to insert the value 1 in a list wich has only one node with value 2.
    Neither the first

    nor the second

    . So you go out of the while loop immediately and the next pointer of prev (which has value 2) now points to a node with value 1 i.e. less than the prev node. Do you agree on this or am I missing something?

    VA:F [1.9.22_1171]
    0
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      Thanks for your response. When we try to insert the value 1 into one node with value 2, prev and p both point to 2 initially (in the first iteration of do-while loop, note that p->next points to itself, which is 2) and the condition (x < = p->data && x >= prev->data) is satisfied, so it breaks out of the loop.

      VN:F [1.9.22_1171]
      0
    2. Jay

      It’s a circular list. There is no “head”. The parameter is passed in as “a node” for this reason.

      The initial pointer is not guaranteed to point to the lowest value, just a value. Inserting 1 into the list 2 will always have this effect.

      You could take the pointer by reference and change it to point to the newly inserted value if you prefer, but is not required for correctness. (This would have significant performance benefits if you were inserting sorted values.)

      VA:F [1.9.22_1171]
      0
  10. reader

    I am sorry but I don’t see what you mean.If x equals 1 and p-data and prev->data are both equal to 2 then how is the condition

    satisfied? The second part of the if is false. So we exit the while loop and at this point we have prev==p==p->next.
    Then as a result of the last 3 lines we have:

    So the new node with value 1 is inserted after the node with value 2 which is p or prev or aNode

    VA:F [1.9.22_1171]
    0
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      Hey reader, I want to thank you for pointing out my mistake. I can’t believe I didn’t notice this condition (x < = p->data && x >= prev->data) is not satisfied when x is 1 and the only data in the list is 2. (p and prev both point to 2).

      And you are right about the second condition too (it won’t match). Which comes to the while loop, and this evaluates to be false (since p == aNode, both points to 2), so it breaks out of the while loop.

      Up to this point, I agree with you so far. But the last point you are saying 1 -> 2, and 2 -> 1 is not correct. But without doing this it would never satisfy the cyclic property, which says the tail must point back to the head.

      Thanks again for pointing out the mistake! :)

      VN:F [1.9.22_1171]
      0
  11. reader

    Hi 1337c0d3r,
    So you are saying that the fact that the code ends up with a list of this form:
    2–>1
    is irrelevant since the list is cyclic? Did I get your last comment?
    But if you agree that in a sorted cyclic list the head is the smallest element then the caller of the function would end up with a list in descending order.
    I agree that in general a cyclic list does not have a head, but I think there is a subtlety in the sorted case. Or am I missing your point?
    I agree that the the last node must point back to the head, but shouldn’t we end up with
    1 –> 2
    not with
    2 –> 1 ?

    VA:F [1.9.22_1171]
    0
  12. reader

    @1337c0d3r
    May be I am splitting hair but what I am trying to say is the following:
    In a cyclic sorted list with many nodes which node is passed in the method is irrelevant.
    But in case of a cyclic sorted list with only one node, the only node that can be passed to the method is the head which we have defined as the node with the minimum element of the list (and assumed that normally the calling code would keep it as a reference).
    So the result of the posted code would be
    2–>1 as mentioned in my previous comment.
    A way to fix this with minimum change in your code is by adding a flag before you break out of the while loop indicating that you are not in the case of a list with one node. Then take into account if the node should be inserted before prev or not. I.e.

    Haven’t written C++ in a while so, sorry if I messed up something.
    But I am interested on your opinion on this subtlety.
    Thanks

    VA:F [1.9.22_1171]
    0
  13. Profile photo of raghavGraghavG

    the code exact&works for all cases…..
    explanation for all cases including while(3rd case):
    case1 handles the “duplicate case” and “only one element in the list case” also along with element(given x) in between case.

    If either case2 fails or case1 fails (means that there are bigger elements in forward direction from anode->next), then “while(p!=anode)” is needed to progress in the list .i.e 3rd case …

    VN:F [1.9.22_1171]
    0
  14. Profile photo of raghavGraghavG

    sorry for above explanation….as it is not covering in the case of “single element exist in list and given element(x) is either greater or lesser to that one”..

    i think the following code will cover all the cases….
    comment:little change to first solution
    void insert(Node *& aNode, int x) {
    if (!aNode) {
    aNode = new Node(x);
    aNode->next = aNode;
    return;
    }
    Node *p = aNode;
    Node *prev = NULL;
    do {
    prev = p;
    p = p->next;
    if (x data && x > prev->data) break;
    if (prev->data > p->data)&&(x>prev->data!!xdata) break;
    if(prev->data==p->data) break;

    } while (p != aNode);

    Node *newNode = new Node(x);
    newNode->next = p;
    prev->next = newNode;
    }
    }

    VN:F [1.9.22_1171]
    0
  15. Vinay

    I have a question with regard…
    say you have list as 3->*2->1 where the aNode points to 2 i.e its starts from 2 …now if you try to insert 4 in the list
    then for the first time it goes inside the do while loop
    prev is pointing to 2 and
    P is pointing to 1
    then the case 2 i.e
    ((prev->data > p->data) && (x data || x > prev->data))
    [(2>1) && [(41)]]
    is true and it breaks out of do while loop and
    inserts 4 between 2 and 1.which is wrong

    VA:F [1.9.22_1171]
    0
  16. a

    IMO, a circular linked list data structure would have a head and rear pointer.
    Various strategies are available for CRUD operations when this is data structure assumption.

    Also another strategy could be using a header node containing a sentinel value and CRUD operations happen on the basis of this head node.

    That way, we deal with circular linked list, pretty much like we would deal with a linear linked list.

    VA:F [1.9.22_1171]
    0
  17. shantanu

    the following code shd work :

    void insert(Node start, int val)
    {
    Node tmp = new Node(val);

    //if list is empty
    if(start == null) { tmp.next = tmp; return; }

    //initialize current and greatest pointers
    Node current = start;
    Node greatest = start;

    while(current.next != start)
    {
    //case 1: node lies between 2 values already present in the list
    if(val > current.data && val greatest.data) greatest = current;
    }

    //now, value is either greater than all values in the list, or smaller than all values. //in any case, value should be inserted after the greatest node
    tmp.next = greatest.next;
    greatest.next = tmp;

    }

    VA:F [1.9.22_1171]
    0
    1. shantanu

      made a mistake in the while loop. shd be written as below

      while(current.next != start)
      {
      //case 1: node lies between 2 values already present in the list
      if(val > current.data && val greatest.data)
      greatest = current;

      }

      VA:F [1.9.22_1171]
      0
  18. shantanu

    while(current.next != start)
    {
    //case 1: node lies between 2 values already present in the list
    if(val > current.data && val current.data)
    {
    greatest = current;
    }

    }

    VA:F [1.9.22_1171]
    0
  19. Profile photo of Song QiangSong Qiang

    With all three cases

    VN:F [1.9.22_1171]
    0
  20. Profile photo of CoderCoder

    when there is only one node in the cyclic list, program will stop at the following line:
    if (x data && x >= prev->data) break; // For case 1)

    p->data is not valid because p is null pointer

    VN:F [1.9.22_1171]
    0
  21. Profile photo of ZaneZane

    I don’t understand why would someone use this data structure, you are going through the trouble of sorting the list, yet the way you access it gives away all the performance benefits. If it were a doubly linked list, i could see easy access to the smaller values from the node->prev and larger values from node->next.

    VN:F [1.9.22_1171]
    0
  22. Shoumo

    Just use this method to add a new node and it will always enter it in a sorted way

    VA:F [1.9.22_1171]
    0
    1. Rami

      void insert(Node * aNode, int x)
      {
      // handle NULL list case
      if( aNode == NULL )
      {
      aNode = new Node(x);
      aNode->next = aNode;
      return;
      }

      while(
      ( aNode->next->v >= aNode->v && x >= aNode->next->v ) ||
      ( aNode->next->v v && x >= aNode->next->v ) )
      {
      aNode = aNode->next;
      }

      Node n = new Node(x)
      n->next = aNode->nex;
      aNode->next = n;
      }

      VA:F [1.9.22_1171]
      0
    2. sachin

      @Shoumo : it seems that your code is only for you have given head node. I’m i correct ? What if other node is given as input?

      VA:F [1.9.22_1171]
      0
  23. Dipesh Gupta

    Hi admin,
    I am doubtful about one case though. With your given linked list, lets say the value to be inserted is 0.
    Although it may be inserted before 1 (or after 6) with the given code, but should not the headPointer (aNode) be now pointing to 0.
    Because the list is sorted, it makes sense to start with the smallest element.

    VA:F [1.9.22_1171]
    0
  24. hakki

    Actually your solution is unnecessarily complicated. Please see the following strightforward code. It handles all the cases mentioned.

    VA:F [1.9.22_1171]
    +1
    1. hakki

      Sorry, ignore the previous post. There is a copy/paste mistake. See the following code.

      VA:F [1.9.22_1171]
      0
    2. hakki

      there is a problem with code tag. It crops some parts while posting. I am sending without code tags this time. I hope it shows the code correctly.

      public static Node insert(Node node, int x)
      {
      if(node == null)//empty list
      {
      Node newNode = new Node(x);
      newNode.next = newNode;
      return newNode;
      }

      Node start = node;

      while(node.next != start)
      {
      if(node.val = x)
      {
      Node newNode = new Node(x);
      newNode.next = node.next;
      node.next = newNode;
      return node;
      }
      else
      {
      node = node.next;
      }
      }

      //if list has one value, min, max
      Node newNode = new Node(x);
      newNode.next = start;
      node.next = newNode;
      return node;

      }

      VA:F [1.9.22_1171]
      0
    3. ahmad omar

      what if insert for node in circular linked list as this ( void insert (const Type& newItem)) please help

      VA:F [1.9.22_1171]
      0
  25. Profile photo of robertiroberti

    VN:F [1.9.22_1171]
    +1
  26. Profile photo of badcoderbadcoder

    Can any one please check my code and let me know if I have done any mistake.

    public ListNode insertIntoSortedCircularList(ListNode head, int val){
    ListNode temp = new ListNode(val);
    if(head == null){
    head = temp;
    head.setNext(head);
    }else if (head.getData()>val){
    temp.setNext(head.getNext());
    head.setNext(temp);
    temp.setData(head.getData());
    head.setData(val);
    }else{
    ListNode current = head;
    ListNode prev = null;
    while(current.getNext() != head && current.getData()<val){
    prev = current;
    current = current.getNext();
    }
    if(current.getNext() == head && current.getData()<val){
    temp.setNext(head);
    current.setNext(temp);
    }else{
    temp.setNext(current);
    prev.setNext(temp);
    }

    }
    return head;
    }

    VN:F [1.9.22_1171]
    0
  27. Profile photo of badcoderbadcoder

    Can any one please check my code and let me know if I have done any mistake?

    VN:F [1.9.22_1171]
    0
  28. Risshi

    // CircularLinkedList.cpp : Defines the entry point for the console application.
    //

    #include “stdafx.h”
    #define N 5
    //#define N 4
    //#define N 3
    //#define N 2
    //#define N 1

    typedef struct node_tag
    {
    int data;
    node_tag* link;
    }node;

    void printCircularLinkedList(node* tail)
    {
    if (tail == NULL)
    {
    printf(“\nLinked List is empty”);
    return;
    }

    node *cur;
    cur = tail;

    do
    {
    cur = cur->link;
    printf(“%d\n”, cur->data);
    } while (cur != tail);
    }

    node* addNode(node *tail, int x)
    {
    node *p = new node;
    p->data = x;
    if (tail == NULL)
    p->link = p;
    else
    {
    p->link = tail->link;
    tail->link = p;
    }
    tail = p;
    printf(“\n Added node with data %d\n”, x);
    return tail;
    }

    node* createCircularLinkedList(node* tail)
    {
    int i, x;
    printf(“Enter elements\n”);
    for (i = 0; i data = x;

    if (tail == NULL)
    {
    p->link = p;
    tail = p;
    return tail;
    }

    if (tail->link == tail)
    {
    tail->link = p;
    p->link = tail;
    return tail;
    }

    prev = tail;
    cur = tail->link;
    if (x data)
    {
    while (x data)
    {
    prev = cur;
    cur = cur->link;
    if (prev->data > cur->data)
    break;
    }
    if (x > cur->data)
    {
    while (x > cur->data)
    {
    prev = cur;
    cur = cur->link;
    }
    }
    }
    else
    {
    while (x > cur->data)
    {
    prev = cur;
    cur = cur->link;
    if (prev->data > cur->data)
    break;
    }
    }
    p->link = cur;
    prev->link = p;
    return tail;
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    node *tail;
    tail = NULL;
    int option, x;
    tail = createCircularLinkedList(tail);

    //printCircularLinkedList(tail);

    do
    {
    printf(“\nEnter option:\n 1. Print \n 4. Insert \n 9. Exit \n”);
    scanf_s(“%d”, &option);

    switch (option)
    {
    case 1:
    printCircularLinkedList(tail);
    break;
    case 4:
    printf(“\nEnter element to be Inserted in a sorted Circular linked List:\n”);
    scanf_s(“%d”, &x);
    tail = insertNodeCircularLinkedList(tail, x);
    printf(“\nLinked list after Insertion operation:\n”);
    printCircularLinkedList(tail);
    break;
    case 9:
    return 0;
    default:
    printf(“\nEnter a vaid option\n”);
    }
    }
    while (true);
    return 0;
    }

    VA:F [1.9.22_1171]
    0
  29. dominations crowns hack

    When it comes to entertainment and games
    to be even more specific, you can get hundreds of these games online and be able to choose form a wide range and variety of
    games there. And lecithin is a major component of the
    protective sheath that surrounds nerve cells. In the beginning, new tiles are usually 2 but later users will get larger figure tiles.

    VA:F [1.9.22_1171]
    0
  30. fb hacker online

    You really make it appear so easy together with your presentation however I to find this matter to
    be actually something that I believe I’d by no means understand.
    It kind of feels too complicated and very broad for me.

    I’m looking forward for your next put up, I will try to get the
    hang of it!

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.