Thread: Problem with my first linked list attempt.

[EDIT] Please read my reply, as well, it has more information [EDIT]
[EDIT] Problem solved. Sorry noone got to help. You can read on if you wish to watch me talking to myself [EDIT]

Alright let me start out by saying this is hardly an attempt. I took the tutorials' linked list and in trying to understand it, added a thing or two. I have no idea if what I think I doing correctly is actually correct, so tell me if something is wrong.

So... a bit about the code(before I show you the code). I took the tutorial code and wrapped the statement that transverses through the list and adds new nodes and wrapped it into a for loop set to run 50 times. Each time it loops, it creates a new node and sets the value of the node to a random number from 0-50 (using rand()).

Ok, simple so far. As far as I could see, I had no problems with that. Now the next thing I did was create a function that searches the list for a specific number. Starts from the beginning, checks to see if that node is the number, if it isn't it moves until it either gets to the end or finds the number. I'm doing this wrong. For whatever reason, when it gets to the part of the function where it searches for the number, it crashes. If someone could explain why, I'd be very appreciative.

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

string searchList(int);

struct node {
  int x;
  node *next;
};

int main() {
  node *root;  
  node *conductor; 
  
  srand ( time(NULL) );

  root = new node; 
  root->next = 0; 
  root->x = 12;
  conductor = root;

  for (int y = 0; y <= 50; y++) {
    if ( conductor != 0 ) {
      while ( conductor->next != 0)
         conductor = conductor->next;
    }
    conductor->next = new node; 
    conductor = conductor->next; 
    conductor->next = 0;    
    conductor->x = rand() % 50;
  }

  cout << searchList(rand() % 50);
  cin.get();
  
  return 0;
}

string searchList(int y) {
  node *root;
  node *conductor;

  conductor = root;  // I'm not sure if I'm initizalizing enough to get back
                     // to the beginning of the list here.
  
  cin.get(); // Fine at this point, crashes when I continue
  
  if ( conductor != 0 ) {
    while ( conductor->next != 0 && conductor->x != y)
      conductor = conductor->next;
  }
  
  if ( conductor->x == y )
    return "Number was in the list";       // I know this is highly unnessasary
  else                                     // when I could just make a void
    return "Number was not in the list";   // function and cout this, but I
                                          // figured "what the hell".

Note: Edit(3) after the code.

Alright did a little more looking into it and found that I'm in an infinite loop, I'll fix that and see if it works, if there is another problem, feel free to say.

EDIT: I figured it out, I guess I was right when I thought I didn't initialize enough. If there is another problem, still... well, you know what to do.

EDIT(2): Ok, well it compiles, it works... sort of. Here's the thing, it's never finding the number. I even raised the odds of generating the same number twice by change it to 1-10 rand and making the same 50 numbers. So why is it never finding a number, I'm guessing it's not doing the search correctly. Why? Well, I think it's because I'm not looking at the same linked list in my functions. How did I come to this conclusion? I changed my function so if it doesn't find the number, it prints out the values of the list. This printed 12 and then abruptly closed, ignoreing pauses, cin.gets(), everything. So something is wrong. I also did a cout in the main loop to make sure it's properly adding random numbers to the list.
... phew ...
Ok, well here is the code:

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

string searchList(int);
void printList();

struct node {
  int x;
  node *next;
};

int main() {
  node *root;  
  node *conductor; 
  
  srand ( time(NULL) );
  
  int z = rand() % 10;
  
  cout << z << endl << endl;
  
  root = new node; 
  root->next = 0; 
  root->x = 12;
  conductor = root;

  for (int y = 0; y <= 50; y++) {
    if ( conductor != 0 ) {
      cin.get();
      while ( conductor->next != 0) {
         conductor = conductor->next;
      }
    }
    conductor->next = new node; 
    conductor = conductor->next; 
    conductor->next = 0;    
    conductor->x = rand() % 10;
    cout << conductor->x << endl;
  }

  cout << searchList(rand() % 10);
  cin.get();
  
  return 0;
}

string searchList(int y) {
  node *root;
  node *conductor;

  root = new node; 
  root->next = 0; 
  root->x = 12;
  conductor = root; 
  
  if ( conductor != 0 ) {
    while ( conductor->next != 0 && conductor->x != y)
       conductor = conductor->next;
  }
  
  if ( conductor->x == y )
    return "Number was in the list";
  else
    printList();
}

void printList() {
   node *root;
   node *conductor;

   root = new node; 
   root->next = 0; 
   root->x = 12;
   conductor = root;
   
   if ( conductor != 0 ) {
     while ( conductor->next != 0 ) {
       cout << conductor->x << endl;
       conductor = conductor->next;
     }
     cout << conductor->x << endl;
   }
}

EDIT(3): Ok, if I take this out of a function, it works fine. Finds the number sometimes and other times it doesn't. Just what I wanted, so I guess now it's just down to how to get it into a function? Do I have to pass pointers "root" and "conductor" to the function?

Any help would be good. Remember, if you help, I automatically love you.

It all works, now.

Here is some finished code if you want to see what I did. Thanks for reading this far into the post, by the way.

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

struct node {
  int x;
  node *next;
};

string searchList(int, node*, node*);
void printList(node*, node*);

int main() {
  node *root;  
  node *conductor; 
  int z;
  
  srand ( time(NULL) );
  
  z = rand() % 50;
  
  cout << "Populating Linked list...";
  cout << "Here is the number that will be looked for: " << z << endl << endl;
  
  root = new node; 
  root->next = 0; 
  root->x = 12;
  conductor = root;

  for (int y = 0; y <= 50; y++) {
    if ( conductor != 0 ) {
      while ( conductor->next != 0) {
         conductor = conductor->next;
      }
    }
    conductor->next = new node; 
    conductor = conductor->next; 
    conductor->next = 0;    
    conductor->x = rand() % 50;
  }
  
  cout << searchList(z, root, conductor);
  cin.get();
  
  return 0;
}

string searchList(int y, node *root, node *conductor) {

  conductor = root; 
  
  if ( conductor != 0 ) {
    while ( conductor->next != 0 && conductor->x != y)
       conductor = conductor->next;
  }
  
  if ( conductor->x == y )
    return "Number was in the list";
  else
    cout << "Number not found, here are the elements of the list." << endl;
    printList(root, conductor);
}

void printList(node *root, node *conductor) {
     
   conductor = root;
   
   if ( conductor != 0 ) {
     while ( conductor->next != 0 ) {
       cout << conductor->x << " ";
       conductor = conductor->next;
     }
     cout << conductor->x << endl;
   }
   cin.get();
}

Hi,

I think a linked list is typically implemented as an object of a LinkedList class. So you have two classes: the Node class and the LinkedList class. The LinkedList class consists of a Node* member pointing to the front of the list and some member functions for adding a node to the list, displaying the list, getting the pointer to the front of the list, etc.

As an exercise try implementing it like that. Since this is the subject of another thread, try adding a member function to the list class that will remove the nth node.

Then if you want some more practice, create another linked list class that is doubly linked, so you can go backwards and forwards through the list--in that case a Node will have both a next and previous pointer. The list class will also have an additional member to store a pointer to the last node, so that you can start at the beginning or end of the list and traverse it. Try writing the remove node function for that list class as well.