Linked Lists confusion

dawballz

Anyone know of any good websites that deal with linked lists re: classes?
c++.
I did a quick google but found nothing with classes.

It's a project for college.
I am stuck on the first, basic part.
I need to know how to add nodes and then change the data contained in them, but I am getting confused.
I dont see why I can't just use classes and create objects for each set of data I want to input.. if you know what i mean, but we have to use linked lists.

edit; should i just use a struct instead of a class?

dawballz

Here is code I already have:

#include <cstdlib>
#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 20;

class data
{
      private:
              int acNo;
              string name;
              float balance;
              char status;
              int dayOfPay;
              int monthOfPay;
              
              data *nextaddr;
      public:
             data(int *, string *, float *, char *, int *, int *);  //constructor
             data *getaddr();                                       //function that returns a pointer to and object of type data
             
             void setaddr(data *);
             void display();
             
             };
             
             
data::data(int *acNumber, string *fullName, float *acBalance, char *acStatus, int *dayOfPayment, int *monthOfPayment)
{
               acNo = acNumber;
               name = fullName;
               balance = acBalance;
               strcpy(status, acStatus);
               dayOfPay = dayOfPayment;
               monthOfPay = monthOfPayment;
               nextaddr = NULL;
               }
               
data *data::getaddr()
{
     return nextaddr;
     }
     
void data::setaddr(data *nextad)
{
     nextaddr = nextad;
     return;
     }

void data::display()
{
     cout << endl << "NAME: " << name << endl << "ACNO: " << acNo << endl;
     return;
     }
                      
      

int main(int argc, char *argv[])
{
    class data d1("123445", "joe black", "133.44", "N", "19", "12");
    class data d2("1945", "martin lawlor", "193.24", "P", "21", "11");
    class data d3("4343445", "francis baker", "3.24", "T", "9", "2");
    data *next;
    
    next = &d1;
    d1.setaddr(&d2);
    d2.setaddr(&d3);
    
    while(next != NULL)
    {
               (*next).display();      //same as next->display()
               next = (*next).getaddr();
               }
               
    return 0;
}

But it returns a big long long list of errors.
As you can see I really don't have much of an idea of these linked lists.
also, this is just a small program i made to try get my head around linked lists, the actual project is much bigger.

sean_or99

http://www.google.ie/search?q=c%2B%2B+linked+lists

The first page that comes up has a linked list class in it.

satchmo

Wikipedia also has a good explanation of it.

For the simplest singly-linked list, each node in it contains some data and a pointer to the next node. The last node points to nothing (NULL, or some custom value you set), and your program contains a pointer to the first node. This way you can start at the first (or "head") node, and keep following the 'next' pointers until you get to the node you want. And if you want to insert or remove an object, you just fiddle with the pointers - no copying or other alterations needed.

I'm not sure what you mean by "I dont see why I can't just use classes and create objects for each set of data I want to input"... where are you going to store all those objects? In an array? How do you know what size to make the array?

A good situation to use a linked list is when you want to keep a collection of objects but you don't know how many objects there might be. If you just guess an amount and make an array to store them, you'll either waste a lot of memory, or fill up the array in which case you'll need to create a bigger array and copy all the values to the new one, which can be costly. Besides that, if you wanted to insert an object in the middle of an array, you'd have to shift all the other objects over. With a linked list all you have to do is switch one or two pointers.

As for using a struct vs. using a class, it doesn't really make a difference performance-wise, but you'll need a class if you want to make a base 'LinkedList' class and inherit from it later on.

dawballz

satchmo wrote:

I'm not sure what you mean by "I dont see why I can't just use classes and create objects for each set of data I want to input"... where are you going to store all those objects? In an array? How do you know what size to make the array?

Sorry.. I know I'm not good at explaining things but...
ok..here's what i did for another program where i didn't know how many objects there was going to be:

class data
{
      int telno;
      string name;
}

on starting the program, the user was presented with a menu:
1. enter details
2. display all data

so, if he presses 1: he enters name and tel number for example.

int main()
{
      int runtimes = 0;
      
      cout << 1. enter details ...etc
     cin >> choice;

      if(choice == 1)
{
      data objects[runtimes];
      runtimes++;
}
more functions to enter data etc..

ehh well it was something like that anyway.. but obviously that's not what i want to do here... I'll work a bit more on it and reply in a while.
thanks.

dawballz

Ok I once again need help..
I want to make a function which will go through all nodes and display all data in them..
Here is the code I have, which works when it is put inside main()
..
but I want to make a function from it called showAllData();
.....

data = root;
     
     for(int x = 0; x <= NoOfPeople; x++)            
     {
             data->displayAllDetails();  //displays all data in this node
             data = data->next;        //points to next node
             cout << endl << endl;
     }

Beano

I dont think you quite have the concept of a linked list yet. To iterate through a linked list you do not need to know in advance how many items the list has. In fact you wont know otherwise why are you using a linked list? The end condition for your loop should be that there is no nextaddr i.e. nextaddr is null. Rewrite the loop again using this as the end condition and it will make more sense. First of all you really should be pseudocoding everything before you write code. It may seem like an extra step that you can do without but it will help you to understand what you are trying to achieve without worrying about the syntax of the language you are using.

I am assuming you didnt look at the google results that sean_or99 gave you? One of the pages linked has exactly what you are looking for. If you did then you need to read them again. There are some excellent tutorials there.

Hint : For loops have no place in any discussion of linked lists. Its while loops all the way.

dawballz

Ok here is what I came up with, and i think it works..

data = root;
     while(data != NULL)
     {
                      data->displayAllDetails();
                      data=data->next;
                      cout << endl;
                      }

but now i need to put it into a function.
what data do i need to pass as parameters?

hang on i just realised that won't work cos if there is only 1 node, data->next WILL be NULL.. true?
edit; fixed.. data != NULL instead of data->next != NULL

dawballz

Anyone...help please..?
I googled for "pass a class to a function" and loads of other variations but came up with nothing...
Is it possible to pass a class as a function parameter?

http://forums.devshed.com/c-programming-42/passing-a-class-as-function-argument-146336.html
that guy has the same problem but i'm not sure what they are proposing as the solution..?

cython

dawballz wrote:

Anyone...help please..?
I googled for "pass a class to a function" and loads of other variations but came up with nothing...
Is it possible to pass a class as a function parameter?

http://forums.devshed.com/c-programming-42/passing-a-class-as-function-argument-146336.html
that guy has the same problem but i'm not sure what they are proposing as the solution..?

What do you mean by passing a class? Surely you just want to pass an instance of a class (i.e. an object?)

dawballz

Yeah maybe I could get it to work like that...
How do I pass an object.. say I want to pass the root object(/node) and the data object..

class node
{
      private:
              int acNo;
              string name;
              etc......
      public:
           ...etc...

then:

void showAllNodes([B]WHAT GOES IN HERE?-I want to pass the objects 'root' and 'data'[/B]); 
int main()
{

    node *root;
    node *data;
    
    root = new node;
    data = root; 
.....etc...
....
showAllNodes(root, data);
return 0;
}

void showAllNodes([B]AGAIN, WHAT HERE..?[/B])
{
     
     while(WHAT != NULL)             
     {
             WHAT->displayAllDetails();
             WHAT = WHAT->next;        //points to next node
             cout << endl << endl;
     }
return;
}

cython

To actually be able to directly manipulate a class (which seems to be what you're trying to do), you need to have static attributes and static methods within the class. Problem is, these are mainly useful for keeping track of how many objects are in existence at a given time. I suppose that it might be possible to have a static element that points to the first element in your linked list, e.g.

class node
{
      private:
              int acNo;
              string name;
              static node *node1;
              static int numOfNodes;
              etc......
      public:
              node()
              {
                 if ( node1 == NULL)
                   node1 = &this;
                 etc...
              }

              ~node()
              {
                 if ( node1 == &this)
                   node1 = this -> next;
                 etc...
              }

              static void showAllNodes()
              {
                if ( node1 == NULL)
                {
                  cout << "There are no nodes in existence" << endl;
                  return 0;
                }
                else
                {
                  node current = node1;
                  while(current != NULL)             
                  {
                    current->displayAllDetails();
                    current = current->next;        //points to next node
                    cout << endl << endl;
                  }
                  return;
                }


           ...etc...

This is pretty rough and messy, I'll admit, but I haven't used C++ for objects in a while, and I'm not the most familiar with linked lists, but from what I know and have seen, I think this might be a starting point

Also, since I assume from what I see here that the method showAllNodes(...) is only used for a single class, then you should make use of encapsulation and include it in the class above as a static method.

You can then call:

node :: showAllNodes();

Please note that you also have to initialise the static data member node1 outside the class, and set it to NULL as follows, before creating any node objects:

node node::node1 = NULL;

I hope this is of some help to you

If anything I said up there is unclear, just ask and I'll try to clarify it

EDIT: By the way, in performing insertions and deletions into the linked list, you'll have to take care of the static member node1, and sometimes it may need to be updated by other methods

satchmo

You want to just pass in a pointer...

void showAllNodes(node* listHead)
{
     node* head = listHead;
     
     while(head != NULL)             
     {
             head ->displayAllDetails();
             head = head->next;        //points to next node
             cout << head->getData() << endl;
     }
     return;
}

And obviously you'll need a getData method which returns the actual data stored in the node (an int, string, whatever it is).

cython's way of using static variables would work, but only for one linked list. If you wanted to use the node class twice for two different linked lists then it would fall over.

I reckon the cleanest way of implementing this would be both a LinkedList class and a Node class. The LinkedList contains a pointer to the head node, any statistics you want to keep about the list (id/name, number of nodes, number of insertions etc) along with all the methods for inserting and removing nodes. These are the methods that contain the logic for manipulating the node pointers to add and remove data. Then the Node class contains the data and the next pointer, along with accessor mothods like setNextPointer(Node*) and getData() for proper encapsulation.

dawballz

Sorry.. I know this is probably becoming repetitive, but I need help now with passing down an object by reference(as opposed to by value), and then possibly delete that object if certain specifications are met by the data contained within that object. Then to move onto the next node and check if that one needs to be deleted..
But I am having trouble passing by reference...

void remZeros(node &first);    // isn't this correct for passing by reference?

.....

                            data = root;           //sets data back to root again 
                            remZeros(root);       //passes root by reference(hopefully)

void remZeros(node &first)
{
     int tempn;
     node* temp;             //temp is a pointer of type node
     temp = first;          //temp now points to first(root above)
     first = first->next;   //moves first to the next node
     
      while(first != NULL)                  //   
     {                                     //
                                           //isZero is a function in the class
             tempn = temp->isZero();       //which checks if acNo == 0
             if(tempn == 1)                // and returns 1 if true
                     delete temp;          //...
                     
             first = first->next;        //points to next node
             cout << endl << endl;
     }
 return;
 }

That's the code I have come up with, but it doesnt work...
Am I passing the right things to the function?
I get about 6 errors when I run that as it is, some of them can be reduced if I put: void remZeros(node* &first); but I am not sure of what the * does.. I know it is a pointer, but it's kinda confusing.. a pointer to the address of first..?

cython

void remZeros(node* first);

The piece you have in the first code box should read like that, I think. This means that the function remZeros will take a pointer to an object of class node.

This is because the * is used to:
- Declare a pointer to a data type, and
- Dereference a pointer (i.e. access the value(s) in the object pointed to by the pointer)

The ampersand (&), on the other hand, is used to get the address of a variable, and as such, you would call remZeros as

remZeros(&nameOfNodeObject);

not as you have done below here:

remZeros(root);       //passes root by reference(hopefully)

void remZeros(node* first)
{
     int tempn;
     node* temp;             //temp is a pointer of type node
     temp = first;          //temp now points to first(root above)
     first = first->next;   //moves first to the next node
     
      while(first != NULL)                  //   
     {                                     //
                                           //isZero is a function in the class
             tempn = temp->isZero();       //which checks if acNo == 0
             if(tempn == 1)                // and returns 1 if true
                     delete temp;          //...
                     
             first = first->next;        //points to next node
             cout << endl << endl;
     }
 return;
 }

Again, the & should be replaced with * as in the above code segment for the same reasons as before.

Give that a try and see if that removes any errors!

dawballz

Ok, sorry again but I am having remedial problems with loops..
I got the above to work using the code I supplied but I will fix it later and tidy it up..
I am basically going to have to paste in my whole function because it's a mess at the moment.. once I get the loops working properly I'll tidy it up a bit..
But, here's the problem..
It deletes the first node grand.. (the cout << "DELETE SUCCESSFUL? " etc are only to help me see where the program is exiting btw), but I can't get it to loop around to try the next node..
This is what I have:

void remZeros(node* &first)
{
    ......
      while(first != NULL)                                      //   
      {                                                         //
                                                               //isZero is a function in the class
             //tempn = temp->isZero();                          //which checks if acNo == 0
             if(temp->isZero() == 1) {                          // and returns 1 if true
                      first = first->next;
                     delete temp;          //...
                     cout << "DELETED.." << endl;
                     //temp->displayAllDetails();               //should not work..
                                                                // a new node will now need to be created since temp above was deleted
                     node* temp;                                //creates new node temp
                     temp = first;                
                     first = first->next;                       //points first to next node, which makes it the first node becuse the last one was deleted.
                     cout << "     DEL SUCCESSFUL?" << endl;
                     temp->displayAllDetails();
                     
                              
                     }
             else  {      
                     cout << "NOT DELETED" << endl;
                     temp->displayAllDetails();
                     temp = first->next;                         //point temp to the next node after first
                    
                                                                //first stays the same because the first node was not deleted.
                     }
                      
        }      
             cout << endl << endl;
            
     
 return;
 }

See http://www.rafb.net/paste/results/nmffsy82.html for full code.
So what it does is displays the details in the first node(because of line 11)
then deletes that node..(line 20)
Then displays the details of the next node.(line 28)
then the program exits.
It doesnt loop around and delete the second node.

This is if I have only 2 nodes created( I have to enter them in manually at the start, and there is no point in entering in more if I don't even have it working for 2.)

Btw thanks for all your help so far

Mutant_Fruit

Put in a cout when you assign first = first->next

Could it be possible that "next" is the null value due to an error in coding which means your program breaks out of the loop without repeating? Put cout's before and just inside each if/else/while statement and trace the programs execution. Its possible you havn't spotted a logical error in your code.

RazorEdge

Right...I'm going to give you a hint here as you'll learn from figuring this out yourself.

What will the pointer "temp" point to the second time around the loop (if the first item is deleted - at line "if(temp->isZero() == 1) {"

Figure out why it will be pointing to random data and you have your solution.

Look at your function again and have a read about what the scope of a C++ variable means and what happens when you delete a pointer. You have some confusion in this area.:)

RazorEdge

...and when you have that fixed, have a think about what "first" should be when you exit...

satchmo

cython wrote:

The piece you have in the first code box should read like that, I think. This means that the function remZeros will take a pointer to an object of class node.
...
Again, the & should be replaced with * as in the above code segment for the same reasons as before.

That's if you want to pass by pointer, he's talking about passing by reference.

Yeah that's the right code dewballs, the only thing is that when calling the function, where you have

remZeros(root);       //passes root by reference(hopefully)

that would be passing the actual object, which is the right thing to do. But what you have is a pointer to an object, node* root - to pass this in as an object you need to dereference the pointer to get the actual object:

remZeros(*root);

In this case the * is the dereferencing operator. When used on a pointer, it gets the object which that pointer is pointing to. However when used during declaring a variable, it just means 'is a pointer'. Likewise, a & can mean either 'the address of' if applied to an object, or 'is a reference' when applied to a parameter of a function.

Make sense?!

RazorEdge

There are many problems in the code above that you need to fix.

(Line numbers refer to the lines in the stuff you pasted to http://www.rafb.net/paste/results/nmffsy82.html and not the code shown above)

This is best explained on white board or with a few diagrams but I will try to explain decision-by-decision using your test case of two nodes, both of which are “zero”.

• Line 6 – temp points to the same memory that first points to.
• Line 10 – You should really check for a NULL pointer first.
• Line 11 – You should really check for a NULL pointer first.
• Line 12 – This will NEVER evaluate to FALSE.
• Line 14 – first is not NULL in this case.
• Line 18 – isZero will return TRUE.
• Line 20 –You delete the memory pointed to by temp. Note temp will still contain the same address after this call. The only difference is the memory AT this address has been deleted. You need to understand this.
• Line 20 –You declare a new variable called temp (why?Delete is confusing you I guess). From this line onwards until line 33, this local variable is the temp that will be accessed. Once this if statement finishes, this variable is now longer accessible. The outer temp becomes visible again and is in fact hasn’t been changed from the original value assigned at line 6. The memory pointed to by temp has been freed so it can have a random value. The probability of this memory having the zero value is very low and the check at line 18 will return FALSE and the second node in your test case is not deleted.

I’ll leave you to fix this problem. There are other logic flaws in this code as well. first on exit should point to the first non-zero value when in fact it will point to the last non-zero value or will be NULL if no non-zero value exists. At line 19 & 26 you have “first=first->next”. You are skipping a node by doing this. Also it is possible for first to be non-NULL but for temp to be NULL – exitstat does not terminate the loop - so line 18 will cause a general protection fault for some test cases.

dawballz

Ok I re-wrote most of it..
The part which doesnt delete the nodes works perfectly, but now I'm having trouble with the delete nodes part..
I know I need more code between lines 16 and 24 and elsewhere, but I am getting very confused...

http://www.rafb.net/paste/results/YduDHQ77.html
If there is only one node, how do I work it?

I understand delete now.. it deletes the node, but the pointer stays there..
Thanks

edit; new code:
http://www.rafb.net/paste/results/uvrrWS40.html
It will work perfectly for one node, but not for more than one or zero nodes...help...

RazorEdge

You are getting closer.:)

You need to think about a few more things now.

If you delete the first node then you must update the head pointer to the new next node.

If you delete any other node, then you must update the next pointer of the previous node to point to the node after one that you are about to delete.

See below for some pseudo code...you should have done something like this before attempting to code this.

It can be done more efficiently than this but this at least is clear (I think!).

CURRENT = FIRST // Current is the one we potentially delete
PREV = NULL // Prev is before current 
 
 
 
WHILE (CURRENT IS NOT NULL) 
   IF CURRENT.isZero TRUE
      IF CURRENT == FIRST // You always need to check if you are deleting the head of the list
         FIRST = CURRENT.NEXT
         DELETE CURRENT
         CURRENT = FIRST // First is dead, all hail the new first
      ELSE
         PREV.NEXT = CURRENT.NEXT // Update the previous
         DELETE (CURRENT) // We are going to delete the current node
         CURRENT = PREV.NEXT  // Update current
      ENDIF
   ELSE
      REM Leave node as it is non-zero (maybe display contents first)
      PREV = CURRENT  // Advance current and previous
      CURRENT = CURRENT.NEXT
   ENDIF 
 
ENDWHILE (CURRENT IS NOT NULL)

rsynnott

I'm guessing this is homework? Tsk.

dawballz

Yeah a project rsynnott..
Couldn't get the above function working so I am going to skip it and do some of the other, easier(I hope) functions.
Thanks for your help with that one.