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

[devonrevenge]

how can fun2codes operator= code use push back while using the existing nodes to copy the data, surley you would wind up with two lots of the same list??

[fun2code]

surley you would wind up with two lots of the same list??

That was the intent.

int main()
{
    list list_a;
    // add some nodes to list_a

    list list_b;// default construction
    // add some nodes to list_b

    list_a = list_b;// operator= invoked. Intent is to make list_a a copy of list_b
}

We have actually reached a stopping point here.
Further functions may be added as future exercises to extend functionality as desired.
I suggest adding a node* back; as a data member of the list class so we don't have to iterate through the whole list to perform a push_back operation. Note: Our operator= is an expensive operation as we are iterating through the whole list with every call to push_back() there.If we would just remember the last node pushed back we would not have to do that.

I suppose we could implement in just that function.

Either way, I present a pop_back() here because even with a pointer to the back node we still have to iterate through the list.
Why? We need a pointer to the next to last node. This will become the last node after the back node is popped and we must assign link = NULL for it.
I have refined this over time. It used to be cumbersome.
I think that I am finally handling the iterations below cleanly:

void list::pop_back(void)
{
    if( front )
    {
        if( front->link )// more than 1 node in list
        {
            node* iter = front;
            while( iter->link->link )// looking for link->link = NULL
                iter = iter->link;

            // iter now points to node before back
            delete iter->link;
            iter->link = NULL;
            // back = iter;// uncomment if a back member is added as a list member
        }
        else// only 1 node in list
        {
            delete front;
            front = NULL;
            // back = NULL;
        }
    }
    return;
}

You now have a list which is basically functional, but is specialized to work only with nodes in which an integer, string pair is stored.
This sort of limits its usefulness.
You could rewrite all the member functions to work with a different node type, but that would get old quick.

The next step would be to turn the list into a template class. You then define your int/string as a structure, add a couple of operator overloads (for < for instance, so that insert_asc() will work), then declare an instance of a list for your data type and you are good to go again.

I think that going for all that in this thread would be a bit much though.

Shall we summarize, handle questions, and then call it a wrap?

EDIT: comments, adapting pop_back() to THIS list class

[devonrevenge]

what we havnt done doubly linked lists yet!! nah just kidding, im in your debt fun2code you helped me loads, i have a lot to practice and understand, this is the best linked list tutorial on the net, seriously it proly is.



im amazed that the operator= function means that when i use = to copy the things in main it goes about it differently, are their any other cases when i might want to change the use of =?
could i change the value of say an int but only when i copy it with =? i cant think of a reason why i would want to, other than to see how it works, any other cases it might work?

i havent done anything with templates, or std list, next subject i guess


***thanks fun2code***

self directed learning wouldnt have got me this far very quickly, i dont think i would have given up but i would have floundered so you have made my new coding hobby even better so thanks ^_^

it also seems to be fundemental to everything else i might want to learn, i looked at boost and winsock stuff, i say its a load of structs and linked lists, in (the form of templates too) i might be able to use them now, but nothing clever till i understand.

[naraku9333]

are their any other cases when i might want to change the use of =?

Anytime you have a class that has pointer members that need to be (deep) copied. Follow the rule of three http://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming) if you need a destructor, copy ctor or operator= then you need all three.

[fun2code]

You're welcome for the help here devonrevenge.

I think that linked lists make great learning exercises.
They touch on a lot of elementary skills, and they aren't super hard so you can tinker with them casually. Like a good Lego model.

The code for our list got scattered a bit back there, so I'll present the (hopefully) finished (ie properly working) class here.

I added a couple of more "bonus" features (why not?)

I added a node* back as a private data member.
I have rewritten some member functions where back is involved, and to simplify where I could.

The main() is setup to create 2 lists (chapter_1, chapter_2), then create a 3rd list wholeStory which is the "sum" of chapter_1 and chapter_2
I overloaded += in the myList class for this purpose.

Also, I renamed the class myList to avoid naming conflicts. The name 'list' was asking for trouble here.

#include <iostream>
#include <string>
using namespace std;


class myList
{

public:

    struct node
    {
        int num;
        string word;
        node* link;
        node(): link(NULL) {}
        node( int Number, string Word, node* Link ): num(Number), word(Word), link(Link) {}
    };

    //*** functions ***
    void push_front(int number,string word );// add node to front of list
    void push_back(int number,string words);// add node to back of list
    void pop_front(void);// delete node at front of list
    void pop_back(void);// delete node at back of list
    void clear(void);// delete all nodes. Leave front = back = NULL
    void insert_asc(int number, string word);// use instead of push_front/back to build an ordered list

    void displaylist(void);// write entire list contents to cout

    // operators
    myList& operator=( const myList& r_list );// assignment
    myList& operator+= ( const myList& r_list );// append lists

    // ctor
    myList();// default ctor
    myList( const myList& r_list );// copy ctor
    // dtor
    ~myList();

private:
    node* front;// points to 1st node in the list
    node* back; // points to last node in the list
};

// destructor
myList::~myList()
{
    unsigned N = 0;// a frill
    while( front )// could call clear() here, but we want a node count
    {
        pop_front();
        ++N;// counting nodes
    }
    cout << "*** deleted myList with " << N << " nodes" << endl;
}

myList::myList(): front(NULL), back(NULL) // default ctor
{ cout << "default ctor here." << endl; }

// copy ctor
myList::myList( const myList& r_list )
{
    front = back = NULL;
    for( node* iter = r_list.front; iter != NULL; iter = iter->link )
        push_back( iter->num, iter->word );

        cout << "copy ctor here." << endl;
}

myList& myList::operator=( const myList& r_list )
{
    clear();// destroy existing nodes

    // create the new nodes
    for( node* iter = r_list.front; iter != NULL; iter = iter->link )
        push_back( iter->num, iter->word );

    cout << "operator = here" << endl;
    return *this;
}

myList& myList::operator+= ( const myList& r_list )
{
    // add nodes  to existing list
    for( node* iter = r_list.front; iter != NULL; iter = iter->link )
        push_back( iter->num, iter->word );

    cout << "operator += here" << endl;
    return *this;
}

void myList::push_front(int number,string word )
{
    front = new node(number, word, front);
    if( !back ) back = front;

    return;
}

void myList::push_back(int number,string word)
{
    if( back )
    {
        back->link = new node(number, word, NULL);
        back = back->link;
    }
    else
        front = back = new node(number, word, NULL);

    return;
}

void myList::pop_front(void)
{
    if( front )
    {
        node* temp = front;
        front = front->link;
        delete temp;
        if( !front ) back = NULL;
    }
}

void myList::pop_back(void)
{
    if( front )
    {
        if( front->link )// multi node myList
        {
            node* iter = front;
            while( iter->link->link )// looking for: link->link = NULL
                iter = iter->link;

            // iter points to node before back
            delete iter->link;
            iter->link = NULL;
            back = iter;
        }
        else// only 1 node in myList
        {
            delete front;
            front = back = NULL;
        }
    }
}

// delete all nodes from myList. Post cond: front = back = NULL
void myList::clear(void)
{
    while( front )
        pop_front();
}

//insert nodes in ascending order
void myList::insert_asc(int number,string word)
{
    if( front == NULL )
        push_front(number, word);// new front because myList is empty
    else if( number < front->num )
        push_front(number, word);// new front because it belongs there
    else// insert past front
    {
        node* iter = front;
        while( (iter->link != NULL) && (number > iter->link->num) )
            iter = iter->link;

        // iter now points to the node before the insertion point
        if( iter->link )// mid-myList
            iter->link = new node(number, word, iter->link);
        else// iter = back
            push_back(number, word);
    }
}

void myList::displaylist(void)
{
    node* iter = front;
    while( iter )
    {
        cout << iter->word << iter->num << endl;// customize here
        iter = iter->link;
    }
}

For testing:

int main ()
{
    myList chapter_1;
    chapter_1.insert_asc( 6," Lay on the ground quite still  " );
    chapter_1.insert_asc( 4," Find fresh underpants to try on ");
    chapter_1.insert_asc( 1," ** CHAPTER 1 ** ");
    chapter_1.insert_asc( 8," Keep like that day after day  ");
    chapter_1.insert_asc( 2," If you're attacked by a Lion ");
    chapter_1.insert_asc( 7," Pretend you are very ill ");
    chapter_1.insert_asc( 9," Perhaps the lion will go away ");
    // display chapter 1
    chapter_1.displaylist(); cout << endl << endl;

    // a list to store all chapters
    myList wholeStory( chapter_1 );// start as a copy of chapter 1

    myList chapter_2;
    chapter_2.insert_asc( 3," that boy stood on the burning deck ");
    chapter_2.insert_asc( 5, " a wolly scarf around his neck ");
    chapter_2.insert_asc( 9," shoes on his feet ");
    chapter_2.insert_asc( 11, " he wished he was wearing trunks instead ");
    chapter_2.insert_asc( 7, " hat on his head ");
    chapter_2.insert_asc( 1, " ** CHAPTER 2 ** ");
    // display chapter 2
    chapter_2.displaylist(); cout << endl << endl;

    wholeStory += chapter_2;// add chapter 2 to the story

    // display entire story so far
    wholeStory.displaylist();cout << endl << endl;

    cout << endl;
   return 0;
}

Output:

default ctor here.
 ** CHAPTER 1 ** 1
 If you're attacked by a Lion 2
 Find fresh underpants to try on 4
 Lay on the ground quite still  6
 Pretend you are very ill 7
 Keep like that day after day  8
 Perhaps the lion will go away 9


copy ctor here.
default ctor here.
 ** CHAPTER 2 ** 1
 that boy stood on the burning deck 3
 a wolly scarf around his neck 5
 hat on his head 7
 shoes on his feet 9
 he wished he was wearing trunks instead 11


operator += here
 ** CHAPTER 1 ** 1
 If you're attacked by a Lion 2
 Find fresh underpants to try on 4
 Lay on the ground quite still  6
 Pretend you are very ill 7
 Keep like that day after day  8
 Perhaps the lion will go away 9
 ** CHAPTER 2 ** 1
 that boy stood on the burning deck 3
 a wolly scarf around his neck 5
 hat on his head 7
 shoes on his feet 9
 he wished he was wearing trunks instead 11



*** deleted myList with 6 nodes
*** deleted myList with 13 nodes
*** deleted myList with 7 nodes

[naraku9333]

@fun2code
Maybe make the Node struct private? Also, since you add a back pointer in the class, why not add a second link in Node?
I'm not a huge fan of the idea of the insert_asc function, it doesn't make sense to me unless the list is already sorted. I would also have just one data member (std::pair?), might be easier to covert to a template. Just my opinions/suggestions.

@devonrevenge
If you think this is fun, wait until you implement a binary search tree (BST).

[fun2code]

@naraku9333

OK, easy ones first...

...since you add a back pointer in the class, why not add a second link in Node?

Two node*'s in the node structure? Would they be prev and next ?
I didn't want to get into a doubly linked list here (just wrap this singly linked case). Were you thinking of something else?

I'm not a huge fan of the idea of the insert_asc function, it doesn't make sense to me unless the list is already sorted.

Of course. The function is there in order to make it possible to create an ordered list. It would have to be used exclusively for adding nodes to the list.

I would also have just one data member (std::pair?), might be easier to covert to a template.

I agree. The node with two separate data fields is devons design choice.
I went with it because we were working on devonrevenge's list.

At this point I would just go straight for a template class version.

Now for the harder one...

Maybe make the Node struct private?

The issue here for me is access to data in the list.

Normally, when I'm tinkering with a list class I've written myself I will even (hold onto something) leave front public, so I may freely mangle manipulate the list in the main().

We probably want to do better than that here.
Note that we presently have no access to the data in the list.
We have no front() or back(). None of our member functions return a node pointer and front is private so there is no way to obtain a pointer to front in the main().
If we make the node structure private then this list is really on lockdown.

I'd say that until we have fully functional iterator objects setup (which is beyond my skill level), the best we can do is to permit the use of nodes in the main(), provide a get_front() which returns a pointer to front by value NOT by reference (so the user cannot re assign front itself), and then warn the user not to mess with the values of link, which are exposed to him/her.
Your thoughts?

Q: So is that the primary difference beween an iterator into a list and a node*?
An iterator exposes the data in a node, but hides the links?

Another issue concerns any front() which might be written.
It gets too convoluted due to there being two data fields in a node.
( would it be void front( int*& rpInt, string*& rpWord ) so we can change num and word in the node through these pointers? )

We'd probably be better off just working through node*'s for now.

[naraku9333]

A proper iterator is essential for a functional list, and to be honest the one I made in school didn't implement an iterator (wasn't required) so I decided to make a new list attempting to replicate the std::list. I just finished (for the most part, need to debug more and implement reverse iterators) the iterator class.

class iterator
		{
			node* _node;
		public:
			iterator() : _node(NULL){}
			iterator(node* n) : _node(n){}
			iterator(const iterator& it) : _node(it._node){}
			T& operator*(){ if(_node)return _node->data; }
			T& operator->(){ if(_node)return _node->data; }
			iterator& operator++()
			{
				if(_node)
				{
					_node = _node->next;
				}
				return *this;
			}
			iterator operator++(int)
			{
				iterator it(*this);
				++(*this);
				return it;
			}
			iterator& operator--()
			{
				if(_node)
				{
					_node = _node->prev;
				}
				return *this;
			}
			iterator& operator--(int)
			{
				iterator it(*this);
				--(*this);
				return it;
			}
			bool operator!=(const iterator& it) const { return (this->_node != it._node); }

			iterator& operator=(const iterator& it)
			{
				_node = it._node;
				return *this;
			}
		};

As you can see I have it implemented basically just encapsulating the node. Now whether this is how the stl does it or the recommended way I'm not sure, as I said I'm new to implementing iterators myself.

Heres the rest of the code in case your interested. I haven't implemented everything yet. http://ideone.com/ZP4xsx
Edit: Added reverse_iterator http://ideone.com/lN6NSA

[devonrevenge]

woo thats way above my level, will come back in six months and tackle that

[fun2code]

@naraku9333. Thanks for that iterator code.
I will tinker with iterators for the above class once I'm working with a template version.

I have found various codes for an iterator class online.
What I couldn't picture was how to create an object (iterator) which behaves entirely as though it is another type (pointer to T), without ever referring to it's data members. I see that this behavior is "teased out" through the creative definition of operators.

Did you copy your operator-> correctly? It returns the same as operator* (namely T&).

I found one operator-> definition for an iterator particularly interesting.
Check this:
this <--pointer to iterator
*this <--- reference to iterator
**this <--- reference to T (left * interpreted as our overload for * in iterator class)
&(**this) <--- pointer to T

Hence:

T* iterator::operator->()
{
    return &(**this);
}

Also, I came across the real hardcore stuff. Here's a link to an article which explains how to define an iterator class so that it is fully compatible with the STL algorithms. ie, so you can call std::sort(), etc on your own containers.
There are numerous typedefs, iterator "traits", and an inheritance heirarchy (where eg. iterator derives from const_iterator, etc,..).

So, spoiler alert! Every detail for creating a singly linked list that is fully compatible with the standard STL methods is here:
http://en.literateprograms.org/Singly_linked_list_%28C_Plus_Plus%29

@devonrevenge: Gets deep fast, huh?
I'm only a couple of steps ahead of you.

EDIT: Readers may wish to add front() and back() functions (both returning T&). The issue of what to return if the list is empty will arise.
This issue is discussed in detail, and some valuable examples of exception handling code, can be found in this other thread (currently active in the general programming forum)
http://www.cplusplus.com/forum/general/85346/
I have linked to the beginning of the thread. See pg. 2 re. above issues.

[naraku9333]

@fun2code
Your'e right operator-> should return a pointer, nice catch I probably wouldn't have noticed that for a while. I may try to make the iterator compatible with std functions, but for now I just want to implement as much of std::list functionality for now. I want to be able to change std::list to sv::list in testing code and have them behave the same, which seems to be working (I've only done minimal testing). Latest version http://ideone.com/76GVqa

[devonrevenge]

hey ive tried this a few times, declaring an array in a struct

 struct node
    {
        char letter[10][10];
        string word;
        node* link;
        node(): link(NULL) {}
        node( char letter [10][10], string Word, node* Link ): letter[10][10](letter[10][10]), word(Word), link(Link) {}
    };

whats the correct way to do it??

im gonna try and out put letters in a bigger array so i can use the linked list to display asci style art and animate it.
all i think i will have to do is save a shape in each link say a letter and some how display each link side by side.

i got an idea how to do it