linked list find

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?

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.

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.

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.

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.

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

---

*feels like a moron*

Wow, that is easy. Thanks guys.

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.