Perfecting my linked list

[Volatile Pulse]

This is continued from this post: http://cplusplus.com/forum/beginner/76498/

My complete code is this:

#include <iostream>

namespace vp {
   template<class T>
   class list {
      private:
         struct node {
            T value;
            node *next;
            node *prev;
            node *operator ++() {
               if (this->next != NULL)
                  this = this->next;
               else
                  this = NULL;
               return this;
            }
            node *operator --() {
               if (this->prev != NULL)
                  this = this->prev;
               else
                  this = NULL;
               return this;
            }
            T operator *() {
               if (this == NULL)
                  return NULL;
               return this->value;
            }
         };
         node *firstNode;
         node *lastNode;
         unsigned int mSize;
      public:
         class iterator {
            private:
               node *current;
            public:
               iterator (node *n) : current(n) {}
               iterator operator =(iterator n) {
                  this->current = n->current;
                  return *this;
               }
               void operator ++() {
                  if (current)
                     current = current->next;
               }
               node *operator ->() {
                  return current;
               }
               node *operator *() {
                  return current;
               }
               bool operator !=(iterator n) {
                  return current != n.current;
               }
         };
         /** list constructor **/
         list() : firstNode(NULL), lastNode(NULL), mSize(0) {}

         /** list deconstructor **/
         ~list() {
            /** while firstNode isn't NULL **/
            while (firstNode != NULL) {
               /** create new node at firstNode's "next" node **/
               node *n = firstNode->next;
               /** delete firstNode **/
               delete firstNode;
               /** reassign firstNode to the "next" node **/
               firstNode = n;
            }
         }
         iterator begin() {
            return iterator(firstNode);
         }
         iterator end() {
            return iterator(lastNode->next);
         }
         unsigned int size() {
            return mSize;
         }
         void push_back(T x) {
            /** create new node **/
            node *n = new node;
            /** set value equal to x **/
            n->value = x;
            /** since this is the end node there isn't a next node **/
            n->next = NULL;
            /** point to the prev node **/
            n->prev = ((lastNode) ? lastNode : NULL);
            /** if this isn't the first node **/
            if (lastNode)
               /** set the last node's next equal to this one **/
               lastNode->next = n;
            /** make the last node the new node **/
            lastNode = n;
            /** if first node doesn't exist **/
            if (!firstNode)
               /** point to n **/
               firstNode = n;
            mSize ++;
         }
         void push_front(T x) {
            /** create new node **/
            node *n = new node;
            /** set value equal to x **/
            n->value = x;
            /** point to the next node **/
            n->next = ((firstNode) ? firstNode : NULL);
            /** since this is the first node there isn't a prev node **/
            n->prev = NULL;
            /** if this isn't the first node **/
            if (firstNode)
               /** set the first node's prev equal to this one **/
               firstNode->prev = n;
            /** make the first node the new node **/
            firstNode = n;
            /** if last node doesn't exist **/
            if (!lastNode)
               /** point to n **/
               lastNode = n;
            mSize ++;
         }
         T pop_back() {
            /** make sure there is something to pop back **/
            if (!size())
               return NULL;
            /** if popping back the last element in the list **/
            if (size() == 1) {
               /** we only need the value **/
               T value = lastNode->value;
               /** delete the node **/
               delete lastNode;
               /** set them equal to NULL again **/
               lastNode = firstNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;
            }

            /** create a node equal to the 2nd to last node **/
            node *n = lastNode->prev;
            /** next should point to NULL **/
            n->next = NULL;
            /** create a variable equal to the value of the last node **/
            T value = lastNode->value;
            /** delete last node **/
            delete lastNode;
            /** assign last node to the new last node **/
            lastNode = n;
            /** reduce the size **/
            mSize --;
            /** return the value **/
            return value;
         }
         T pop_front() {
            /** make sure there is something to pop front **/
            if (!size())
               return NULL;
            /** if popping front the last element in the list **/
            if (size() == 1) {
               /** we only need the value **/
               T value = firstNode->value;
               /** delete the node **/
               delete firstNode;
               /** set them equal to NULL again **/
               firstNode = lastNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;
            }

            /** create a node equal to the 2nd node **/
            node *n = firstNode->next;
            /** prev should point to NULL **/
            n->prev = NULL;
            /** create a variable equal to the value of the first node **/
            T value = firstNode->value;
            /** delete first node **/
            delete firstNode;
            /** assign first node to the new first node **/
            firstNode = n;
            /** reduce the size **/
            mSize --;
            /** return the value **/
            return value;
         }
   };
}

int main() {
   vp::list<int> myList;
   vp::list<int>::iterator myIter(myList.begin());
   myList.push_back(5);
   myList.push_back(6);
   myList.push_back(5);
   myList.push_back(7);
   for (vp::list<int>::iterator iter(myList.begin());
        iter != myList.end();
        ++ iter)
      std::cout << "Node: " << *iter << "\t\tValue: " << iter->value << "\n"
                << "Previous Node: " << iter->prev << "\tNext Node: " << iter->next << "\n";
}

A few things that I wanted to improve upon is making my list type perfect if you will. There are a few spots where I return NULL and according to a quote from the other thread, this isn't ideal.

firedraco wrote:

Your pop_front and back won't work if NULL is not convertible to T. Just throw an exception.

I've never used exceptions before and now sure the best way to start.

Peter87 wrote:

The warnings warn you that you have not implemented the copy assignment operator and the copy constructor. This will be a problem if you try to copy the list because the predefined copy assignment operator and copy constructor will not handle the copying correctly in this case because it will just copy the two pointer members.

I know the copy ctor just loops through another list and copies each location into a new one, and doesn't seem very hard. But I feel I'll have a harder time with the assignment operator. Do I need to delete each node first then copy over? Can you implicitly call the dtor to start fresh?

What other things can I add to the list to make it more complete? I liked the challenge of this and just came back to it due to another program I was working on and realized my lack of functionality.

Thanks in advance guys.

[Volatile Pulse]

Something else that I was curious about was this line here:

   for (vp::list<int>::iterator iter(myList.begin());
        iter != myList.end();
        ++ iter)

When I tried to do iter ++, I got errors. I know it has something to do with my increment operator, but I'm not sure why it doesn't work both ways or how to fix it since I prefer to use the postfix version.

[D80DSL3A]

That looks nice. One part I will look at carefully is how you are implementing iterators. I need to learn more here.

I would like to suggest one area of improvement.
Link lists, especially doubly linked ones, are a great place to develop constructors which do a lot of the connecting of nodes for you.

Consider this ctor for your node class:

node::node( T Value, node* Prev, node* Next ): value(Value), prev(Prev), next(Next)
{
    if( prev ) prev->next = this;// establishing full linkage
    if( next ) next->prev = this;
}

Now the push_front() can be like this:

void push_front( int X )
{
    firstNode = new node( X, NULL, firstNode);
    if( lastNode == NULL ) lastNode = firstNode;
}

And for push_back():

void push_back( int X )
{
    lastNode = new node( X, lastNode, NULL);
    if( firstNode == NULL ) firstNode = lastNode;
}

Note the symmetry.

Better yet, check this!

A function to insert a value after a give node ( pNode )

void insert_after( T value, node* pNode ) {
    if(pNode != NULL) new node( value, pNode, pNode->next );
}

Insert before pNode

void insert_before( T value, node* pNode ) {
    if(pNode != NULL) new node( value, pNode->prev, pNode );
}

Notice I don't even have to catch the address returned by new!

Anyways, it's amazing the shortcuts a good ctor can open up. Explore them!

EDIT: Those insert functions above are a bit reckless. They neglect to check if we are inserting in front of firstNode or behind lastNode
Better versions:
Insert before pNode

void insert_before( T value, node* pNode ) 
{
    if( pNode )
    {
        if( pNode->prev )// then it's not firstNode
             new node( value, pNode->prev, pNode );
        else// pNode = firstNode
            push_front(value);
    }
}

Insert after pNode

void insert_after( T value, node* pNode ) 
{
    if( pNode )
    {
        if( pNode->next )// then it's not lastNode
             new node( value, pNode, pNode->next );
        else// pNode = lastNode
             push_back(value);
    }
}

[cire]

I think the first thing to do is get rid of the overloaded ++ and -- operators in your node class, since they don't belong there (and the implementations are nonsensical.) I don't really see what operator* buys you either since you can access value directly (usually a non-const version of operator* would return a reference.)

               /** delete the node **/
               delete lastNode;
               /** set them equal to NULL again **/
               lastNode = firstNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;

These sort of comments detract from readability.

Some attempt at const-correctness could be made.

// from iterator:

               void operator ++() {
                  if (current)
                     current = current->next;
               }

operator++ should return a value:

iterator& operator++()
{
    if ( current )
        current = current->next ;
    return *this ;
}

The postfix operator, since you mentioned it, can be overloaded as well:

iterator operator++(int)
{
    iterator result = *this ;
    if ( current )
        current = current->next ;
    return result ;
}

After checking out the definition of the post-fix operator, it should be obvious why the prefix operator is preferred anywhere the post-fix behavior isn't required.

[Volatile Pulse]

@fun2code

Consider this ctor for your node class:

node::node( T Value, node* Prev, node* Next ): value(Value), prev(Prev), next(Next)
{
    if( prev ) prev->next = this;// establishing full linkage
    if( next ) next->prev = this;
}

I like this idea, but this returns to part of my original problem. For my default ctor, since I have to now define that as well, what do I assign value to to ensure a type perfect node? Once I can figure out what a perfect default value is for value, then I can complete the type correctness of my list. That's mainly why I made this post, but I do like your ideas so far, thanks.

@cire

I think the first thing to do is get rid of the overloaded ++ and -- operators in your node class, since they don't belong there (and the implementations are nonsensical.) I don't really see what operator* buys you either since you can access value directly (usually a non-const version of operator* would return a reference.)

I had that from some of my original code since this was all a learning experience. I had used the nodes as my iterators and forgot to remove that once I created my iterator class. I've removed it and I'm not working on some of the other suggestions you had as well. The comments on the line above were again due to it being a learning experience so that I could go back and understand what I did step by step. I'm still confused at a few things because I check to see if a node isn't NULL, but if it is NULL, I assign it to NULL anyways. That doesn't make sense to me.

[Imadatobanisa]

@Volatile Pulse
Wow, a good idea!Keep up your good work! :)
My intention is developing an INI class manager which has similar structure above. :)

[TheIdeasMan]

@VP

Good to see you back again - it's been awhile !!

Just a word of warning about Jackson Marie - her? posts are very often bad advice. So just giving you the heads up.

Hope all is well at your end :)

[Volatile Pulse]

Yeah, been busy with real life. Been trying to master wxWidgets but that's a challenge in itself as well. Just wanted to touch up on small challenges before I completely jump head first into this stuff. Next I want to write some good polymorphism code that covers almost all possibilities I'm likely to run into. Wrote a program the other day that was subpar due to my lack of knowledge on the subject.

I'm skeptical of a lot of people I haven't read up on their posts and I try to learn if their advice is good or depending on other posts they have.

[Volatile Pulse]

Ok, I know this isn't rocket science, but I'm really impressed at how simple this was once I read it from here: http://stackoverflow.com/questions/3301362/c-template-function-default-value

But essentially to create a default value for a template type class, you just need to call it's default ctor, in this case T(). Once applied to my code, you get this for a default node ctor:
node() : value(T()), next(NULL), prev(NULL) {}

Now, I need to go back through and figure out what I want/can do about when a NULL node is referenced in my list. Should I return the default ctor for that as well, or should I try to find something different?

[Volatile Pulse]

Ok guys, I have been working on cleaning up my list code and it's coming along rather nicely. I'm still stuck on some problems with the pop_back and pop_front functions. Here:

         T pop_back() {
            /** make sure there is something to pop back **/
            if (!size())
               return NULL;
            /** if popping back the last element in the list **/
            if (size() == 1) {
               /** we only need the value **/
               T value = lastNode->value;
               /** delete the node **/
               delete lastNode;
               /** set them equal to NULL again **/
               lastNode = firstNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;
            }

            /** create a node equal to the 2nd to last node **/
            node *n = lastNode->prev;
            /** next should point to NULL **/
            n->next = NULL;
            /** create a variable equal to the value of the last node **/
            T value = lastNode->value;
            /** delete last node **/
            delete lastNode;
            /** assign last node to the new last node **/
            lastNode = n;
            /** reduce the size **/
            mSize --;
            /** return the value **/
            return value;
         }

Specifically, when the size of the list is 0 (there are no elements in it), it returns NULL. This isn't data type safe and causes issues on certain data types. firedraco had mentioned about using exceptions in this situation, but I don't even know where to begin since I've 1) never used an exception, and 2) I don't know what I'm "trying" and what's supposed to "catch" the exception. I'm trying to get this as close to the STL list as possible just for satisfaction. I know I'll never get it as nice as that, but I'd like to make a list that's easy to use and have pride in making my own.

[D80DSL3A]

Volatile Pulse wrote:

I'm trying to get this as close to the STL list as possible just for satisfaction.

Well, in the STL, the return type of pop_back() is void.
This would eliminate your dilemma.

I would guess that these functions aren't intended to provide access to data.
Perhaps, that's what iterators (and the functions front and back) are for.

[Volatile Pulse]

...I don't know what to say...I'm really speechless to be honest. I just assumed that it returned the element before removing it...I feel like a dummy now. On a brighter note, that does make my list much easier to perfect and also makes sense as to why it doesn't return that item...I really feel dumb.

Back to the drawing board. -.-

[D80DSL3A]

No wait!
The problem is simply shifted to the front and back functions, which both return T&.
Feel better?

My naive view is that you have 2 options re: the return value dilemna.
1) Return the default value for T (ie T() ) if the list is empty.
How do you know if the value is good? You test the value of size.

T x = list.front();// possibly catching a default value
if( list.get_size() > 0 )
{
    // value of x is good.
}

2) front() returns a bool to indicate if good and writes the value to a T passed as reference

T x;
if( list.front(x) )
{
    // x is good
}

I'd go with the 1st.

T& front() {
            /** make sure there is something to return **/
            if (!size())
               return T();
           //.....
}

EDIT: Wait! Now you are returning a reference to a local variable! Is this OK if it only occurs when the list is empty? You should run into trouble if you attempt to use the return as an lvalue in that event.

[Volatile Pulse]

No, not really. My biggest concern is when the list is empty, obviously, but I don't like returning the ctor of T since that can mess things up. Like, obviously I would hope that me, or someone else who uses my list, is smart enough to make sure the list isn't empty before attempting to get a value, but isn't the purpose of creating the class to try and perfect it? I know some things can't always be achieved, but this is one of those things that has to be perfected.

There has to be something that can be returned when size is size besides the ctor purely for the fact that if someone, dumb enough, doesn't check, it could cause issues. Ideally, we should assume idiots aren't using our code, but what happens when, let's say, 2 years down the road I try to use my list class because I remember how hard I worked on it, and forget to check when I grab an element? To be honest, I've had issues worse than that before and figured them out, but I don't like headaches when I try to work on code.

Reading from this site:

CPlusPlus wrote:

A reference to the first element in the list container.

Member types reference and const_reference are the reference types to the elements of the container (for the default storage allocation model, allocator, these are T& and const T& respectively).

There is no different return value when the container is empty which kind of worries me since even the reference material has no advice on this topic :/

[cire]

My naive view is that you have 2 options re: the return value dilemna.
1) Return the default value for T (ie T() ) if the list is empty.
How do you know if the value is good? You test the value of size.

How about the obvious? Throw an exception.

If you don't check if the container is empty before you call front, you're definitely not going to be checking afterward. Standard containers don't throw exceptions, of course. Invoking front on an empty container simply results in undefined behavior.

For option two.. again, if you couldn't be bothered to check if the container was empty before, you're not likely to check the return value of front.

T& pop_back() {
            /** make sure there is something to pop back **/
            if (!size())
               return T();
           //.....
}

This returns a reference to a local variable which goes out of scope when the function ends. We're back to undefined behavior.

[D80DSL3A]

If you don't check if the container is empty before you call front, you're definitely not going to be checking afterward.

Good point. I agree.

But OP is writing a function which must do something if called on an empty list.
What should it do?

How about the obvious? Throw an exception.

OK. That solves it.

But you go on to acknowledge that the standard containers don't do this.
What else could we do here?

I agree with you regarding the "returning a reference to a local variable" problem with T& front(void);

Forget my method #2, it isn't right even when the list is not empty.
The point of front() is to return a reference to the data, which could be used to change that data. my method bool front(T& x) doesn't do that.

Any other suggestions? Or is T& front(void) (returning T() if size == 0) going to have to do it?
EDIT2: Do we limit the usefulness of our list by even referring to T()?
This requires the existence of a no-arg ctor for T.

EDIT: return T* (NULL on empty list)? You can change the data through a pointer to it.
(but this would make front() more like begin() )

[Volatile Pulse]

I already have begin and end implemented, which was rather easy, but I'm trying to get the front and back completed now. I haven't changed my code for pop_back and front yet since I still would like to have access to the data until I can find something to complete it.

In regards to the STL list, does it just return the data stored in the first node, even if the first node is null? I understand that it's undefined, but if that's the way the STL works, then that works for me. Implementing exceptions don't seem to be worthwhile in this situation since you aren't doing any other error checking than you would have been doing before without using exceptions, meaning, I would still need to catch the exception which would require the same amount of work that if(myList.empty()) would require. I'm content with going this route as long as it is right. Thanks for the input so far, I'm just racking my mind trying to get all of this put together.

[cire]

Implementing exceptions don't seem to be worthwhile in this situation since you aren't doing any other error checking than you would have been doing before without using exceptions, meaning,

The benefit of exceptions in this case is that you can't ignore them by just disregarding them, it becomes very obvious what piece of code is causing the error and it doesn't result in undefined behavior.

[Volatile Pulse]

Alright, I have a few pages on exceptions in my book and a chapter from another book that I'll have to take a look at. I know very little when it comes to exceptions, but I was always under the impression that they had to be handled by the code. And, like you said, can't just be ignored. My biggest concern is going back to how the STL does it. I know it doesn't require handling of exceptions, as far as I know anyways, and wouldn't want to require myself or someone else to handle exceptions for my code either.

Lesson time...

On a side note, I took into consideration all of the advice so far and have been slowly picking away at my list. Any other improvements that you can point out that might better it?

[coder777]

And, like you said, can't just be ignored.

You can and you should. Reason: accessing a non existing element is a bug.

if this exception occurs it would (and should) come out as a crash, and that's ok because it is actually a bug. Hiding this is not a good idea.

Instead check for validity (yes: if(myList.empty()) or whatever shows that there's nothing to access is the way to go) and act accordingly.