Thread: linked list find

  1. #1
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916

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

  2. #2
    I lurk
    Join Date
    Aug 2002
    Posts
    1,361

    Re: linked list find

    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.

  3. #3
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    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.
    Away.

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    Last edited by Zach L.; 07-03-2003 at 03:43 PM.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    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.
    Away.

  6. #6
    Registered User Casey's Avatar
    Join Date
    Jun 2003
    Posts
    47
    >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.

  7. #7
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    *feels like a moron*

    Wow, that is easy. Thanks guys.
    Away.

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    Last edited by Zach L.; 07-03-2003 at 03:50 PM.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM