Re: insert [sorted] a node in a linked list
On Fri, 8 Mar 2013 07:20:30 -0800 (PST)
alexo <alelvb@inwind.it> wrote:
I have a linked list that inserts nodes at the top or at the
bottom of the list, but I can't get it working if I try to sort the
inserting.
.....
void Linked_List::insert_sorted(int value)
{
Node * temp = head->next;
if(temp == 0) // if the list is empty
{
push(value); // insert the first element
}
else
{
while(temp != 0)
{
if( value > temp->getValue() )
{
Node * new_node = new Node(value);
insert(new_node, temp);
break;
}
else
{
push(value);
break;
}
temp = temp->next;
}
}
}
Suppose your linked list has three values {2, 4, 6}. You call
insert_sorted(5). temp is not NULL. On the first iteration of the
while loop, 5 > 2. So insert, and the list is {2,5,4,6}.
Watch for the antipattern of using if-while on the same array. A good
algorithm doesn't have special cases. You could write just
Node *prior = head, *pnode = new Node(value);
for( Node *p= head;
p && p->getValue() < value;
prior = p, p = p->next );
insert(pnode, prior);
if insert() deals correctly (as it needs to) with the possibility that
there is no prior node. Better would be if insert() allocated and took
{node,value} as parameters instead of two nodes.
While on the subject of simplification, sometimes you can simplify your
code by using temporary values and sometimes temporaries just create
more work. Your insert doesn't need temp; it could just be
Node * Linked_List::insert(Node * new_node, Node * after_me)
{
new_node->next = after_me->next;
after_me->next = new_node;
return new_node;
}
which permits successive inserts in order, and perhaps makes clearer why
insert should allocate. :-)
HTH.
--jkl
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]