maybe somethig like this..... but right! heheh

This doesn''t work!, but is close

    node* AppendNode(node** headRef, int num) {	node* current = *headRef;	node* prev_ptr = *headRef;    node* newNode;    newNode = (node*)malloc(sizeof(node));    newNode->value = num;    newNode->next = NULL;			// special case for length 0    if (current == NULL) 	{    *headRef = newNode;	}	else	{       while (current->next != NULL && newNode->value > current->value)		{            prev_ptr = current;			current = current->next;		}	    prev_ptr->next = newNode;		newNode->next = current;	}	return *headRef;}    

||||-- Our creation is the transformation of one. --|||

From the top of my head...

                            node* insertNode(node** headRef, int num) {	node* current = *headRef;	node* newNode;	newNode = (node*)malloc(sizeof(node));	newNode->value = num;	newNode->next = NULL;			// special case for length 0	if (current == NULL) 	{		*headRef = newNode;	}	else	{		while ((current->next != NULL) && (newNode->value > current->value))		{			current = current->next;		}		newNode->next = current->next;		current->next = newNode;	}	return *headRef;}    

Edited by - Steven Edwards on August 21, 2000 3:16:29 PM

nope, im sorry but it didn''t work.... maybe a little change in the design?

||||-- Our creation is the transformation of one. --|||

You run through the linked list until you find a node with a value greater than the number you want to store OR a null pointer to the next node. Then you just put the value you want to store before that if it is a greater number or on the end of the list if it is null.

------------------------------
#pragma twice

It''s integer not interger.

------------------------------
#pragma twice

anybody want to take up the discussion that if you have sorted data, the linked list is the last data structure you want to use?

Basically, the cool thing about having a sorted container is that you use a binary search to find data. Since you''re using a linked list, you''re relegated to doing a linear search.

If you want something sorted, and want to add and remove items in the middle, use a tree-based structure instead of a linked list. You''ll get much more efficiency.

If you''re comfortable with STL (I assume not since you''re writing your own list class), look up map and set.

Sure, I''ll take up that discussion.

The answer is, as always, it depends on the situation.

If the time it takes to insert new items is a really big deal then obviously a list is better than an array, and yes, a binary tree is better than a list. However, if the time it takes to retrieve the data is a really big deal, then you must take the trouble to make sure your tree remains balanced. In the worst case (all items inserted in order), the tree gives you the same look-up performance as the list. Also, if data size is a bigger deal, then an array is better than a list, which is better than a tree.

Of course a hash table kills array, list, and tree for both insertion and look up times, but it doesn''t necessarily sort the data, it must be tuned to the data being handled, and it can be very expensive memory-wise.

On the other hand, if none of these issues are super critical, then finding and implementing the faster/slicker way is a waste of development time. Just do it the simplest way.

[...which is the sad thing about this thread... This is supposed to be a game development board and someone can''t figure out how to insert into a list (the simplest way). Someone, please take your homework elsewhere.]

if it is soo simple, then why don't you tell me how to do it.

and linked lists play a huge role in game development!

yes... its sad, but i should learn somehow.

Edited by - Virus on August 21, 2000 6:09:27 PM

You need to remember to check for the case when the item you are inserting is going to become the first item in the list.

And, Virus, yes linked lists can play a large role in game development, but I think that the anonymous poster is making the point that if you want to learn anything, you need to do your homework by yourself. This is at least the third thread that you''ve started that looks pretty much like "Ok, here is problem #1 of my homework. Please solve it for me."

Holy Carp!!! (yes, carp.)

You''re absolutely right. I just scanned Virus''s last 4 posts, and they''re all homework questions!

I propose we give Virus either:
1) complete misinformation in response to his posts, or..
2) complicated solutions that will tip off the teacher to the fact that he''s cheating.

In the spirit of #2, here''s a program that inserts a number into the right place:

    #include &ltlist>#include &ltalgorithm>using namespace std;const int theNumberToInsert = 4;int main (){  list&ltint> myList;  for (int n=0; n<theNumberToInsert*2; myList.push_back (n++));  myList.insert (find (myList.begin (), myList.end (),     theNumberToInsert),    theNumberToInsert);  return 0;}    

For fun at home, set theNumberToInsert to be very large.

I love writing obfuscated code.