who else can I ask?

Everyone is on vacation...

The Internet is the only source available I have right now.

Please I didn''t mean to bother you or anything, I just thought that you could offer me your experience.

I have a little more than 13 hours trying to learn linked lists... and I suppose I should have some questions!

But anyway.... thanks to everyone who replayed...

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

I read your original post, you said it only puts it on the the end of the list, but you do that it will print it int he opposite order right, and thats not the problem?

no, that's not the problem; The problem is that my function does not sorts the linked list.
It is supposed to insert each new number in the right place in the list, every time the user enters a number.

I wrote a new version, but it crashes whenever 3 or more numbers are entered.

        Node* Insert (Node** list, int value ){	Node* current = *list;	Node* prev_ptr = *list;	Node* new_node = NULL;	int counter =0;	new_node = (node*)malloc(sizeof(Node));	new_node->value = value;	new_node->next = NULL;	if ( current == NULL )	{		// linked list is empty		*list = new_node;		}	else	    if ( current->next == NULL )		{			// there's 1 item in the lsit			if ( current->value > new_node->value )			{						new_node->next = *list;			    *list = new_node;							}		    else				current->next = new_node;		}		else		{					while ( current->next != NULL )			{               				current = current->next;			}                          new_node->next = current->next;		                          current->next = new_node;		}			return *list;}        

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

Edited by - Virus on August 21, 2000 12:55:59 AM

Some basics
There are 4 results to check for when inserting into a linked list.
1) There are no items on the list
2) You insert at the beginning
3) You insert at the end
4) You insert in the middle

Sorry, but to learn linked lists you need to draw the diagrams and not just modify semi-working code hoping to luck out.

I''m pretty sure I''ve got some working linked-list code on my web-page in my Programmer''s diary


ZoomBoy
Developing a 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor, diary, 3D Art resources at
Check out my web-site

for one thing, this is not the place to do your homework, there are other sites for that crap.

second, they told you many times to change:

while(current->next != NULL)
current = current->next;

this is still in your code, and is ALWAYS ALWAYS ALWAYS going to go to the end of your list. my guess is that you have a weak grasp on pointers and how they work, go read your textbook again.

and WTF is ''int counter'' doing there?? you NEVER use it!!

don''t mean to sound like an ass here, but seriously this isn''t that hard of a problem...

AZ

Errm..I might be missing something here but why is a indirect
point being used? (node** headRef)
why not just use:
node* AppendNode(node* headRef, int num)
{
node* current = headRef;
node* prev_ptr = headRef;
...
just curious..

quote: Original post by Epoch

Errm..I might be missing something here but why is a indirect
point being used? (node** headRef)
why not just use:
node* AppendNode(node* headRef, int num)
{
node* current = headRef;
node* prev_ptr = headRef;
...
just curious..

Well, assuming that this code is eventually working, you will need to worry about the case where the item you are inserting becomes the new head of the list. In this case, you need to update the head pointer that was passed in.

Or you could pass in some "dummy" list head, that has a key value that is always lower than the minimum of your input set (say, -1). You will then have to skip the first element when printing your list, of course.

And since we''re at it: why not put a sentinel at the end of our list (that has a value larger than any input value). That way, we eliminate 3 out of 4 of ZoomBoy''s inserting conditions (we always insert in the middle, and the list is never empty).

Hey Virus, try it out will you , I think you''ll get some extra credits for that!

Dormeur

"Sure, I''ll take up that discussion."
Me too.


"The answer is, as always, it depends on the situation."
For sure, always follow the kis principle.
"keep it simple."

"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."

That''s only if you do not use a balanced tree, if you use an AVL
tree then there is a "Invariant" that grants you the balancing.
Why not using the STL (standard template library) it''s easy and
super fast (red black tree) implementation of the map type for example. ("STL is for free, and comes with VC")

"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,"
Create a map, pump the data in and use an iterator to go through it.

"it must be tuned to the data being handled, and it can be very expensive memory-wise.
No, that is what the "invariant" of a container implementation is for. Otherwise people who would use things like STL would have to bother about that, and that is not what OO is for.


"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."
That is absolutely right, so take a ready to use container and forget doing it yourself, unless you only code it yourself to get some knowledge.




PS: For all who are really interested in the bits and the bytes of conatiner classes and sorting etc. i would recommend to read
the following book:

Algorithms in C.
Robert Sedgewick
Addison Wesley
ISBN 0 - 201 - 31452 - 5

This book is absolutely understandable and has a good scientific value. It tells you all you need to know about BIG O notation for
Algorithm Complexity calculation and all the Math stuff you''ll need to understand Algorithms. If you are planning to study computer science this book is a must, since it''s more or less standard.
There are some other books like Knuth etc. but they are harder to understand for beginners.


cu

Peter

Finally, i understand linked lists....

The problem was mainly dealing with pointers, but now that i master pointers, im very close to master linked lists.

It toke me 19 hours; I think i must have some sleep now.

To all of you who are planning to learn linked lists, b-tress, and all kinds of data structures.

LEARN POINTERS FIRST.

Thanks to every one who replayed!


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