Beginner: Linked List question

This is a discussion on Beginner: Linked List question within the C++ Programming forums, part of the General Programming Boards category; Hi folks, I'm a beginner to C++ and have been working my way through the tutorial and got as far ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    2

    Beginner: Linked List question

    Hi folks,

    I'm a beginner to C++ and have been working my way through the tutorial and got as far as class and linked lists so decided to have a go at writing one myself.

    I think i'm very nearly there, but have come across a difficulty in the search function i've written. It's not returning the required value.

    See the code:-

    Code:
    #include <iostream>
    
    using namespace::std;
    
    struct node {
       int x;
       node* child;
    };
    
    class linked_list_int {
    
       public:
       
          linked_list_int();
          ~linked_list_int();
          
          void insert(int value);
          node* search(int value);
          void destroy_list();
       
       private:
       
          node* head;
          
          void insert(int value, node* a_node);
          node* search(int value, node* a_node);
          void destroy_list(node* a_node);
    
    };
    
    
    linked_list_int::linked_list_int() {
       head=NULL;
    }
    
    linked_list_int::~linked_list_int() {
       destroy_list();
    }
    
    void linked_list_int::destroy_list() {
       destroy_list(head);
    }
    
    void linked_list_int::insert(int value) {
       if (head != NULL) {
         insert(value, head);
       }
       else {
         head=new node;
         head->x=value;
         head->child=NULL;
       }
    }
    
    node* linked_list_int::search(int value) {
       cout<<"publically searching for:"<<value<<endl;
    //   node* banana=search(value,head);
    //   cout<<"    publically found it at: "<<banana->x<<endl;
       return search(value, head);
    }
    
    void linked_list_int::insert(int value, node* a_node){
       if (a_node->child == NULL) {
          a_node->child=new node;
          a_node->child->x=value;
          a_node->child->child=NULL;
       }
       else {
          insert(value, a_node->child);
       }
    }
    
    node* linked_list_int::search(int value, node* a_node){
       cout<<"  privately searching for: "<<value<<endl;   
       if (a_node != NULL) {   
         if (a_node->x == value) {
           cout<<"    privately found it at: "<<a_node->x<<endl;
           return a_node;
         }
         else {
            search(value, a_node->child);
         }     
       }
       else {
         return NULL;
       }
    }
    
    void linked_list_int::destroy_list(node* a_node) {
       if (a_node != NULL) {
         destroy_list(a_node->child);
         delete a_node; 
       }
    }
    run by a small program:-

    Code:
    #include <iostream>
    #include "linked_list_int.cpp"
    
    using namespace::std;
    
    int main(int argc, char* argv[]) {
    
    //  cout<<"Hello, is this working?"<<endl;
      
      linked_list_int* ll=new linked_list_int;
      
      ll->insert(3);
      ll->insert(1);
      ll->insert(4);
      ll->insert(9);
      ll->insert(8);
      ll->insert(5);
      
      node* found_node;
      found_node=ll->search(4);
      
      cout<<"retrieved: "<<found_node->x<<endl;
      
      
      delete ll;
      ll=NULL;
    
    
     return 0;
    
    }
    which returns:-

    publically searching for:4
    privately searching for: 4
    privately searching for: 4
    privately searching for: 4
    privately found it at: 4
    retrieved: 0


    i.e. it creates the linked list ok, and find's it in the search (private function) but it is not passed upto the search (public function) and hence not returned to the calling program (i.e. retrieved:0 rather than 4).

    What am i doing wrong here?

    I added some (commented out) output in the public search function which confirmed that the node wasn't even getting passed to here.

    I appreciate that this is a very basic bit of code, and that there are many other better ways of writing this sort of thing, but i'm after the learning experience here rather than getting too complicated on my first day.

    I'd appreciate any help you could offer.

    Cheers,
    WM

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You are recursively searching, so you need to return the result form search no n to search n-1.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    2
    Thank you !

    i didn't notice or even think about this!
    I replaced the line:-

    search(value, a_node->child);

    with:

    return search(value, a_node->child);

    and it worked!

    Cheers,
    WM

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 03:05 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21