can you help me with linked lists? im close, so very close to grasping it.

[devonrevenge]

yep, still digesting, the good thing is theres enough here to help anyone with linked lists.

:D thas spike milligan, hes very good. (the first one)

[D80DSL3A]

OK. I can understand if you've had enough. (the green check mark suggests you have)

devonrevenge wrote:

... the good thing is theres enough here to help anyone with linked lists.

However, this list class has been left at a dangerous point in development!
This is a great example of where the expression "knowing just enough to be dangerous" definitely applies!

I added a destructor so that we are cleaning up after our usage of new properly
when a list object goes out of scope.
This needed to be done.

This destructor has a dark and insidious side though!
A time bomb has been set by including it.

This code will set off the bomb.

int main ()
{
    list object;// now the object contains the list. No list::node* needed here.

    object.push_front(6," Lay on the ground quite still  ");
    object.push_front(4," Find fresh underpants to try on ");
    object.push_front(8," Keep like that day after day  ");
    
    object.displaylist();// good to here

    // I'd like to leave object like it is and continue working with a copy of it
    list object2( object);// KA-BOOM!!

    // for a REALLY spectacular crash, try actually using it
    object2.push_back(20, "** CHAPTER 2 **");// This caused a BAD crash!
                                            // Had to terminate program via Task Manager
    cout << endl;
    object2.displaylist();

   return 0;
}

Creation of a copy via default construction + assignment:

    // default construction + assignment
    list object2;
    object2 = object;// make that a copy please 

Will cause the same problem.
So will passing an instance of a list by value to a function, etc...

I suggest we add the crucial copy constructor and the assignment operator (=).

I humbly offer this quite possibly imperfect solution:
If I'm doing this wrong someone please let me know (I am not an expert at this):

I like to put the working code for creating a copy of an object in the operator = definition:

list& list::operator=( const list& r_list )
{
    // destroy existing nodes (similar to dtor)
    while( front )
    {
        node* temp = front;// we would just call pop_front() here
        front = front->link;// IF we had such a function
        delete temp;
    }// post cond: front = NULL

    // create the new nodes
    node* iter = r_list.front;
    while( iter )
    {
        push_back( iter->num, iter->word );
        iter = iter->link;
    }
    cout << "operator = here" << endl;
    return *this;
}

I then call operator = from the copy ctor:

// copy ctor
list::list( const list& r_list )
{
    cout << "list::copy ctor here" << endl;
    cout << "Handing off to operator =" << endl;

    front = NULL;// absolutely CRITICAL
    *this = r_list;// invoke construction via assignment
}

After adding these functions to the class the program above gives:

 Keep like that day after day  8

 Find fresh underpants to try on 4

 Lay on the ground quite still  6

list::copy ctor here
Handing off to operator =
operator = here

 Keep like that day after day  8

 Find fresh underpants to try on 4

 Lay on the ground quite still  6

 ** CHAPTER 2 ** 20


*** deleted list with 4 nodes
*** deleted list with 3 nodes

As expected.

@devonrevenge I'm surprised you had nothing to say about that insert_asc()!

This function could be used to support use of this list as a priority queue, were it not for the missing pop_front() that is.

Addition and maintenance of a node* back for the list was next.
It would be nice not to have to iterate all the way through the list on push_back().
Follow conventional wisdom and use the STL folks!
Things like the list class above are just for play.

EDIT: I have selection_sort() working now, but it needs to be simplified.
It is a "real" list type sorting routine. It leaves the data in place and accomplishes the sort by rearranging the links among the nodes.

[devonrevenge]

no no i accidently pressed the green tick i was just afk for a day (playing max payne should give my eyes a break at somepoint, i havnt focused my eyes on anything further than a few feet away since moving to london)

[devonrevenge]

ive been away i havent looked, im gonna proly spend the rest of the week finnishing this, this is my first c++ break in a while and proly the last, cant wait to understand it, im at a really good point of absorbing knowledge, i think i will be making good applications april ish at this rate

[D80DSL3A]

Yeah, I'm good to continue here. You probably want to look over my last few posts good though. You may have some questions.

It looks like that insert_asc() function put your sentences in the right order, so that was your intent in pairing an int with each sentence. It indicates sentence order.

[devonrevenge]

kay i love insert asc, i think it would have taken a long time and many different
combinations of the wrong code til it still works, why does using a copy crash it then, i dont understand a single bit of our new code here, not a shred :( i actually found some holes in my understanding of class as well, like the member selection initialising code, i covered it practiced it once and moved on, im a bit rustty from the subject as well so im tryinf to create another function to manipulate the code a bit like insert asc :D

one simple thing i cant see too, in the destructor code...it says while (front)

i cant think how it knows that front is happening for it to be in while, i dont see how it knows, i might just be being dumb.

i need a warm up exercise simlar but not the same s linked list....and ive found out theres double linked lists too, im determined, but i think i have to have this clearly first, clearly clearly clearly, then i have to work on fully understanding the linker too

[D80DSL3A]

You have a lot of good questions there. Clearly, you read those last few posts carefully.

I will ty to answer the questions well.

Sorry about throwing the copy ctor and operator= in there without any detailed explanations. I thought you had bailed so I was trying to throw a quick wrap on things to make the list class safe to use.


Let' start with the issue of constructor styles. The issue of a copy of a list causing a crash can be seen starting there.

Our node structure:

struct node
    {
        int num;
        string word;
        node* link;
        node(): link(NULL) {}// default ctor
        // this ctor will be quite helpful
        node( int Number, string Word, node* Link ): num(Number), word(Word), link(Link) {}
    };

For our purposes here the (perhaps more common) notation for a ctor would work fine.
ie, For our structure here this ctor:
node( int Number, string Word, node* Link ): num(Number), word(Word), link(Link) {}
and this:

node( int Number, string Word, node* Link )
{
    number = Number;
    word = Word;
    link = Link;
}

are equivalent. In the latter ctor, the data members number, word and link are first default constructed, then values are assigned to them in the body of the ctor.
This 2nd form cannot be used if any of the objects data members is lacking a no arg ctor itself.

How does this hint at the cause of our crash?
The issue of existence of default ctors has been raised.

As we know, if we provide a ctor definition at all it will override the default no arg ctor provided by the compiler.

If I eliminated the no-arg ctor from the node class:
node(): link(NULL) {}// default ctor <- remove this line from structure

We could no longer create nodes this way:
node* front = new node;// ERROR - no no-arg ctor
We HAVE TO creat nodes like this:
node* front = new node(3, "a line", NULL);//using the only ctor available

The compiler also automatically supplies a copy ctor and an overload for =.
The default versions perform a straight across member by member copy of values.
The list class actually has only ONE data member, so the default copy ctor for the list class would be quite simple:

list::list(const list& rList )
{
    front = rList.front;
}

Or, equivalently:
list::list( const list& rList ): front(rList.front) {}

And for = it would be:

list& list::operator=( const list& rList )
{
    front = rList.front;
    return *this;// return a reference to the object calling this function
}

These default versions do what we would WANT done in most cases.
In our case though this is a disaster.

This assignment: front = rList.front;
causes both lists to point to the same data.
When we create a copy of a list we need to create a new copy of all of the data in rList
for our front pointer to point to.

Our copy ctor needs to allocate nodes of its own and copy the data from rLists nodes.

The crash occurred because both object.front and object2.front point to the same memory space.
When object2 is destroyed at the end of program execution, it's OK because its front is pointing to valid data.

When object is destroyed, the memory pointed to by its front has already been deleted.
Calling delete on the invalid front* causes the crash.

The crashes are occurring when the destructor for the 2nd list is called.
You may have noticed from the destructors output in our program that objects are destroyed in the reverse order in which they were constructed.

ie:

list object;
list object2( object );
//...
~object2();// object2 destroyed first leaving front =garbage
~object();// object destroyed. Crash occurs. 

I'll pick apart the new copy ctor and operator= in the next post.

EDIT: I forgot to address this:

one simple thing i cant see too, in the destructor code...it says while (front)

Sorry, I changed notations on you. Note that while(front) is equivalent to:
while(front != NULL)
Similarly, if( !front ) means the same as:if(front == NULL)

EDIT2: I just came across these links (posted by cire) in another thread where the same issue is involved.
The 3 member functions we have been considering lately in this thread are the:
1) destructor
2) copy ctor
3) Assignment operator (=) overload.

These are the 3 functions in the "Rule of Three" covered here:
http://en.wikipedia.org/wiki/Rule_of_three_%28C%2B%2B_programming%29
http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three

[devonrevenge]

ah i understand, you cant use the object for very much so you have to write the node in such a way so that it can be copied?
theres a lot too this linked list buisness isnt there.

im not familiar with 'operator' yet, i need to study the copy constructor

[D80DSL3A]

theres a lot too this linked list buisness isnt there.

Yes. The complications are here because we have a data member (front) which is being used to dynamically allocate memory. That's what brings in the memory management issues.

You mentioned wanting a "warm-up" problem to this (list) problem.
I suggest a toy vector class. You get the same memory management issues, but without all the confusing links and iterating through nodes, etc..

The copy ctor we need for the list class can be quite simple.
We need to make a new list as a copy of a given list:

list::list( const list& r_list )
{
    front = NULL;// clean slate here

    // create the new nodes
    node* iter = r_list.front;// we need to iterate through r_list
    while( iter != NULL )
    {
        push_back( iter->num, iter->word );// create nodes using the values from r_list
        iter = iter->link;
    }
}

Do you see how that creates a completely separate copy of r_list?

EDIT: If you like the style better, the above can be done in a for loop (replacing while)

list::list( const list& r_list )
{
    front = NULL;
    
    for( node* iter = r_list.front; iter != NULL; iter = iter->link )    
        push_back( iter->num, iter->word );    
}

[devonrevenge]

theres something here im not following, a copy of list? thats a copy of an entire class isnt it?

so r_list is the address of list

its member front is initialized to NULL

and its node pointer is assigned to front it cycles through the nodes initialising each member to num or word.

so you create a copy of the entire list... :D i get it its just not very strong in my head.

EDIT: its very clever.

[D80DSL3A]

Not quite on some of that.

so r_list is the address of list

No. r_list is a reference to the list being copied.
We're doing this in main:

int main()
{
    list object;
    // ... add some nodes ...
    list object2( object );// create object2 as a copy of object
}

Here, object is passed to the copy ctor by reference.

its member front is initialized to NULL

No. That would result in losing the front of r_list.

The assignment: front = NULL; applies to the list being created.
The push_back() calls are for the list being created too.

Want a mind blower?
It is crucial that the list to be copied is passed by reference, not by value, to the copy ctor. Why is that do you suppose?

...a copy of list? thats a copy of an entire class isnt it?

It's a copy of an instance of the class. object is one (instance of a) list. object2 is another (instance of a) list.

[devonrevenge]

okay i think i get it, we change the class's use of '=' with a bit of code?

and so when we copy right to left with = it behaves differently and copies of pointer locations are now copies of pointers.

so what does putting this code in the class mean that now you can use

object1 = object2?? as per usual?

[devonrevenge]

is that right or am i still on the wrong track?

[D80DSL3A]

I think you're on the right track there.

Each list has it's own set of nodes.
You're ready for operator=?

In this assignment:list_b = list_a; both list_a and list_b already exist, so it's somewhat like this:

int a = 3;// create some space for an int and store a 3 there
int b = 5;// create a 2nd separate space for another int

a = b;// a forgets about 3, becomes 5 now
b = 7;// does not change a, a still = 5. a and b store data in separate memory locations 

Similarly:

list list_a;
list_a.push_back(1);
list_a.push_back(2);
list_a.push_back(3);
list_a.displayList();// expecting 1 2 3

list list_b;
list_b.push_back(10);
list_b.push_back(20);
list_b.displayList();// expecting 10 20

list_a = list_b;
list_a.displayList();// expecting 10 20

list_b.push_back(30);
list_a.displayList();// expecting 10 20 still. Changing list_b does not change list_a 

Again, the default version of operator= just assigns members straight across.
Same as if we had written:
list_a.front = list_b.front;
We can't have this, both lists would be in the same memory space.
We must first destroy all of list_a's nodes (it "forgets" its value), then push_back new nodes (its new value), with copies of the values stored in list_b's nodes:

list& list::operator=( const list& r_list )
{
    // destroy existing nodes (similar to dtor)
    while( front )
    {
        node* temp = front;// we would just call pop_front() here
        front = front->link;// IF we had such a function
        delete temp;
    }// post cond: front = NULL

    // create the new nodes
    node* iter = r_list.front;// iterating through r_list
    while( iter )
    {
        push_back( iter->num, iter->word );// use the values from r_list's nodes
        iter = iter->link;// next node in r_list
    }
    cout << "operator = here" << endl;
    return *this;// return a reference to the new list
}

EDIT: How about we add a pop_front() next, so we have some way of removing nodes from the list (other than via total destruction)?

[devonrevenge]

yep i understand now, stronger in my head at last.


havnt you allready kind of written the pop front code up their allready (presuming pop front means a function that deletes all the nodes it iterates through)

void list:: pop_front ()
{

while(front)
{
node* temp = front;
        front = front->link;
        delete temp;
}

}

why pop front? i need to recap, fortunatley ive accidently saved nothing over my code...so im gonna write it all again so i remember, i keep forgetting how it all works, like the memory of a new node is stored in temporary memory both in my head and in c++.

incidently i think all this would be easier if i had knowledge of the whole compiling/macine code system, i dont know what gcc is properly though i can read it up on wiki over and over again, i cant suss out anything linker, and i dont know the difference between a library and an api, im losing focus the more i learn, as theres more and more knowledge.

can you recommend some reading? this way im learning something in an order that will make more sense than linking loose bits of understanding to others

[coder777]

pop_front () does what it implies. It pops the first element hence remove the while loop

[devonrevenge]

oh so iterate down nodes, then if front == NULL then delete front?

one day someone will make a computer language that uses english

[coder777]

no, you over complicate things. front is the pointer to the first item. No need to iterate. line 7 to 9 suffice

if front == NULL the list is empty. you may complain about trying to pop something that doesn't exists

[EDIT]
You may introduce a function clear() that do what your pop_front () is actually doing

[D80DSL3A]

Yes devonrevenge, the intent with pop_front() is to pop (or delete) only the front node in the list.

You may have gotten "delete all" from the context in the operator = function:

// destroy existing nodes (similar to dtor)
while( front )
{
    node* temp = front;// we would just call pop_front() here
    front = front->link;// IF we had such a function
    delete temp;
}// post cond: front = NULL 

I meant that, instead of the 3 lines of code there for deleting the front node, we would call pop_front() instead:

while( front )
    pop_front();
// post condition: front = NULL 

Where

void list::pop_front()
{
    if( front )
    {
        node* temp = front;
        front = front->link;
        delete temp;
    }
}

We could also do as coder777 suggested and add a clear() which deletes all nodes.

void list::clear()
{
    while( front )
        pop_front();
}

Let's use this function, and the for loop notation (introduced a few posts back) to tidy up our operator= function:

list& list::operator=( const list& r_list )
{
    clear();// destroy existing nodes (similar to dtor)
    
    for( node* iter = r_list.front; iter != NULL;  iter = iter->link )
        push_back( iter->num, iter->word );// add new nodes from data in r_list
    
    return *this;// return a reference to the new list
}

[devonrevenge]

ah thanks