Insert into a Cyclic Sorted List
August 12, 2011 in linked 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:
- prev→val ≤ x ≤ current→val:
- Insert between prev and current.
- 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.
- 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 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 <= p->data && x >= prev->data) break; // For case 1) if ((prev->data > p->data) && (x < p->data || x > prev->data)) break; // For case 2) } while (p != aNode); // when back to starting point, then stop. For case 3) Node *newNode = new Node(x); newNode->next = p; prev->next = newNode; } |
zhanwu said on August 15, 2011
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.
1337c0d3r said on August 15, 2011
The problem is you don’t know it has all duplicates until you traverse back to the starting point.
zhanwu said on August 17, 2011
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?
zhanwu said on August 17, 2011
read it again and figured out your logic
the code is quite clear but the explanation above is rather confusing
1337c0d3r said on August 17, 2011
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.
Ratna Kumar said on August 16, 2011
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.
1337c0d3r said on August 16, 2011
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.
Ratna Kumar said on August 17, 2011
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.
Ratna Kumar said on August 17, 2011
There’s a typo in the above comment, it’s in the 2nd case
bread said on August 19, 2011
I don’t think we should make the assumption that the list is ASC sorted.
Ramesh said on August 22, 2011
You can first find whether list is sorted in ASC or DESC order and then check conditions accordingly.
bread said on September 5, 2011
of course we can… my point is that we definitely need this
Saurabh said on August 24, 2011
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.
1337c0d3r said on December 28, 2011
Thanks for pointing out this mistake. Another reader has pointed out below, and I just noticed it. Sorry for not noticing your comment earlier.
fatalerror said on August 27, 2011
“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.
vinay said on October 23, 2011
This question has taught me to check all the edge cases before we code !! Thanks
A_Kareem said on November 6, 2011
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
A_Kareem said on November 6, 2011
sorry the line is
if ((x data) && (p == aNode))
{
aNode = newNode;
}
A_Kareem said on November 6, 2011
sorry again
if ((p->data > x ) && (p == aNode))
{
aNode = newNode;
}
flo said on November 10, 2011
Thanks for the problem, implemented something similar.
I will do all the problems you posted on the site and comment on every one to thank you and remind me I done them
jr said on November 21, 2011
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;
}
}
reader said on December 27, 2011
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.
1337c0d3r said on December 27, 2011
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.
reader said on December 27, 2011
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?
1337c0d3r said on December 27, 2011
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?
reader said on December 27, 2011
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?
1337c0d3r said on December 27, 2011
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.
reader said on December 27, 2011
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
1337c0d3r said on December 28, 2011
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!
1337c0d3r said on December 28, 2011
I have updated with EDIT on top of the post. Please let me know if this clarify this a little bit, and I appreciate your comments. Thank you!
reader said on December 28, 2011
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 ?
reader said on December 28, 2011
@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
raghavG said on February 27, 2012
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 …
raghavG said on February 27, 2012
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;
}
}
Vinay said on March 18, 2012
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
Vinay said on March 18, 2012
sorry i wrote it wrong
[(2>1) && [(42)]]…which is true
a said on April 15, 2012
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.
shantanu said on June 9, 2012
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;
}
shantanu said on June 9, 2012
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;
}
shantanu said on June 9, 2012
sorry for spamming, but I am not able to post the correct code here. Please follow the link for the correct implementation : http://phreakhoughts.blogspot.com/2012/06/problem-insert-given-value-into-sorted.html
shantanu said on June 9, 2012
does not let me write the correct code !!!!
shantanu said on June 9, 2012
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;
}
}
phoenixwsl said on September 12, 2012
it seems u didn’t update your head node if x is the smallest value
Song Qiang said on December 14, 2012
With all three cases