# linked list find

• 07-03-2003
confuted
I don't know why I'm having so much trouble with this. It seems like it should be easy. I have a linked list class (there are some other functions which make it more than a standard linked list, but they aren't important here). I'll paste in a simplified version of what I have. I realize that 0 can't be added to the list, but that's ok, because I don't ever need to - that is not the problem.

Code:

```class linked_list        {     public:         void adddata(int add);    //adds data to the list if it is not already present         int countnodes();    //counts the nodes in the list through recursion         linked_list();                ~linked_list();                    private:         int data;         linked_list *next;    //pointer to the next node in the linked list                         linked_list *getlastnode();    // return address of last node (uses recursion)         linked_list *findlow(int *min); }; linked_list::linked_list() {     data=0;     next=NULL; } linked_list::~linked_list() {     if (next)        //if next node, delete it (recursion again)         delete next; } void linked_list::adddata(int add) {     if (data!=add)     {         if (data==0)    //no data in this node yet             data=add;         else        //node contains data, and it isn't add         {             if (next==NULL)    //no next node yet                 next=new linked_list;             next->adddata(add);    //call adddata on the next node...recursion         }     } } int linked_list::countnodes() {     if (next)    //there are more nodes         return (1+ (next->countnodes()) );    //use recursion to count the nodes     else         return 1;                //reached the end of the list } linked_list* linked_list::getlastnode() {     /* This function uses recursion to get and     return the address of the last node in the list */     if (next)         return next->getlastnode();     else         return this; } linked_list* linked_list::findlow(int *min) {     /* Find the node with the lowest     frequency and return a pointer to it */     if (*min>data)         *min=data;     /*********************************************     this is what I don't know     *********************************************/     return NULL; }```
Yeah, I know there's a lot of commenting, more than is needed. Oh well. Any ideas on how to return the pointer to the node with the smallest value for data?
• 07-03-2003
Eibro
Re: linked list find
Quote:

Originally posted by blackrat364
I don't know why I'm having so much trouble with this. It seems like it should be easy. I have a linked list class (there are some other functions which make it more than a standard linked list, but they aren't important here). I'll paste in a simplified version of what I have. I realize that 0 can't be added to the list, but that's ok, because I don't ever need to - that is not the problem.

Code:

```class linked_list        {     public:         void adddata(int add);    //adds data to the list if it is not already present         int countnodes();    //counts the nodes in the list through recursion         linked_list();                ~linked_list();                    private:         int data;         linked_list *next;    //pointer to the next node in the linked list                         linked_list *getlastnode();    // return address of last node (uses recursion)         linked_list *findlow(int *min); }; linked_list::linked_list() {     data=0;     next=NULL; } linked_list::~linked_list() {     if (next)        //if next node, delete it (recursion again)         delete next; } void linked_list::adddata(int add) {     if (data!=add)     {         if (data==0)    //no data in this node yet             data=add;         else        //node contains data, and it isn't add         {             if (next==NULL)    //no next node yet                 next=new linked_list;             next->adddata(add);    //call adddata on the next node...recursion         }     } } int linked_list::countnodes() {     if (next)    //there are more nodes         return (1+ (next->countnodes()) );    //use recursion to count the nodes     else         return 1;                //reached the end of the list } linked_list* linked_list::getlastnode() {     /* This function uses recursion to get and     return the address of the last node in the list */     if (next)         return next->getlastnode();     else         return this; } linked_list* linked_list::findlow(int *min) {     /* Find the node with the lowest     frequency and return a pointer to it */     if (*min>data)         *min=data;     /*********************************************     this is what I don't know     *********************************************/     return NULL; }```
Yeah, I know there's a lot of commenting, more than is needed. Oh well. Any ideas on how to return the pointer to the node with the smallest value for data?

You need a pointer to the head of the list. I don't see any way of obtaining this through the code you supplied.
• 07-03-2003
confuted
Well, the head of the list will be in main, and the function will be called from the head, so just assume "this" to be a pointer to the head.
• 07-03-2003
Zach L.
It seems to me that 'linked_list' is actually a linked list node, and not the list itself (which I know is little more than a bunch of these things linked together). At any rate, it doesn't seem to make much sense to have your findlow function as part of the node.

What you could do without drastic changes though (just an idea), is to have each findlow function take a pointer to a node, and then compare its own data against that nodes... hard to explain, here's some pseudo-code:

Code:

```// Utility function, ptr := linked_list* ptr ptr_to_min(ptr a, ptr b) {   if(a->data < b->data)       return a   else       return b } // Part of the class. ptr findlow(ptr cmp) {   if(next == NULL)       return ptr_to_min(this, cmp)   else       if(cmp == NULL)         ptr node := this       else         ptr node := ptr_to_min(this, cmp)       return next->findlow(node) // Yes, I know node is not in scope... just pseudo-code }```
Edit:
To call this, just call the function for the first node with a null argument.

Edit:
Made stupid typo... fixed it.
• 07-03-2003
confuted
I guess I was unclear in my original post. Darn AIM. I don't want to just determine which of two nodes has the smallest value for data... I want to find the smallest value of data in the entire list. Oh well, I'll work on it some more.
• 07-03-2003
Casey
>I want to find the smallest value of data in the entire list.
Then you have to walk the entire list
Code:

```// Example node* small = head; node* walk = head; while (walk) {     if (walk->data < small->data)         small = walk;     walk = walk->next; } // small points to the smallest value in the list at this point.```
• 07-03-2003
confuted
*feels like a moron*

Wow, that is easy. Thanks guys.
• 07-03-2003
Zach L.
Mine should work (in theory) for the entire list as well... Its just nasty and recursive.

Edit: No it didn't, there was a typo... fixed now.