Re: insert [sorted] a node in a linked list
On Mon, 11 Mar 2013 09:38:38 -0700 (PDT)
alexo <alelvb@inwind.it> wrote:
Now the list is sorted almost completely. The sole exception
is the very first node inserted that remains as last Node.
Any suggestion?
.....
void Linked_List::insert_after(int value, Node * after_me)
{
Node * new_node = new Node(value);
new_node->next = after_me->next;
after_me->next = new_node;
}
You may have noticed in reading about the STL the odd-looking
mathematical notation for what's known as a "half-open" interval:
[begin, end)
It indicates that "begin" is part of the range and "end" is not. Cf.
http://www.mathwords.com/i/interval_notation.htm. It's a useful way to
think about any sequence.
To see if, say, "x" is in the range, the test is
if( begin <= x && x < end )
Note that no value of x satisfies the test when begin == end.
How does that apply to your function? Ask: how to insert a node before
the first node? (Bonus question: how to insert before *any* node?!)
if(temp == 0) // if the list is empty
{
insert_after(value, head);
print_list();
}
Not that way! The sequence you really want to iterate over is
(begin, end]
You need a before-the-beginning position because you can only insert
after.
More concretely, the list is created with one empty node
Linked_List() { head = new Node(); }
and there's no Node method to set its data thereafter. It would
probably be better to start with
Linked_List() : head(0) {}
and change insert_after such that when "after" is NULL, it represents
the position before the head
Node *p = new Node(value);
if( after == 0 ) {
p->next = head;
head = p;
} else {
after->next = p;
}
That has the nice property of dealing with an empty list in a nonspecial
way. :-)
Aside: this thread has been very instructive IMO, and not only to you.
While the advice to just use the std containers is well founded, the
process of trying to program a linked list reveals how fiddly they are
and emphasizes the value of a correct, debugged implementation.
--jkl
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]