Thread: 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

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