A Doubly Linked List strange issue...

[Deimos]

Hey everyone.

My "Game Engine" required a container in which insert and remove operations are fairly easy. I chose to go with a doubly linked list. I made it a templated class and I can't get it to work! It's the strangest issue I've ever faced, I insert more than 4 elements and the application hangs. No reponse, I have to exit the console manually in order to terminate it.
I have gone through it several times and I can't seem to find the problem, I even made the list print out a series of debug messages and they're all OK. Perhaps it's just some noobish mistake hiding in the dark, but since my efforts to correct it are useless I hope you'll have better luck than me.
Here's the full source code so far:

#ifndef CLINKEDLIST_H
#define CLINKEDLIST_H

#include <iostream>

using namespace std;

template <class Type>

class CLinkedList
{
      private:
              class Node
              {
                friend class CLinkedList;

                private:

                    Type data;
                    Node* ptNext, *ptPrev;

                public:
                    Node(Type _data, Node* _next)
                    {
                        data = _data;
                        ptNext = _next;
                        ptPrev = _next->ptPrev;
                        _next->ptPrev = ptPrev->ptNext = this;
                        cout << "New node created: \n";
                        cout << "\tdata: " << data << '\n';
                        cout << "\tthis: " << this << '\n';
                        cout << "\tptNext: " << ptNext << '\n';
                        cout << "\tptPrev: " << ptPrev << '\n';
                        cout << endl;
                    }
                    Node()
                    {
                        ptNext = ptPrev = this;
                        cout << "New Guard created: \n";
                        cout << "\tthis: " << this << '\n';
                        cout << "\tptNext: " << ptNext << '\n';
                        cout << "\tptPrev: " << ptPrev << '\n';
                    }
                    ~Node()
                    {
                        ptPrev->ptNext = ptNext;
                        ptNext->ptPrev = ptPrev;
                    }
              };

              Node* curr;
              Node* guard;

              int length;
              Node* find(Type _data);
      public:
             CLinkedList();
             ~CLinkedList();
             bool contains(Type _data);
             void insert(Type _data);
             void remove(Type _data);
             void display();


};

template <class Type>

CLinkedList<Type>::CLinkedList()
{

    curr = guard = new Node();
    length = 0;
}

template <class Type>

CLinkedList<Type>::~CLinkedList()
{
    for(curr = guard->ptNext; curr->ptNext != guard ; delete curr, curr = curr->ptNext);
}

template <class Type>

class CLinkedList<Type>::Node* CLinkedList<Type>::find(Type _data)
{
    for(curr = guard->ptNext;
        curr != guard
        && curr->data != _data;
        curr = curr->ptNext);

    return (curr != guard ? curr : NULL);
}

template <class Type>

bool CLinkedList<Type>::contains(Type _data)
{
    return (find(_data) != NULL);
}

template <class Type>

void CLinkedList<Type>::insert(Type _data)
{
    if(!contains(_data))
        curr = new Node(_data, curr);
    ++length;
}

template <class Type>

void CLinkedList<Type>::remove(Type _data)
{
    if(find(_data))
        delete curr;
    curr = guard->ptNext;
    --length;
}

template <class Type>

void CLinkedList<Type>::display()
{
    for(curr = guard->ptNext; curr != guard ; curr = curr->ptNext)
        cout << curr->data << endl;
}

#endif

I know that I'm missing a lot of important operations here, now. I just didn't want to carry on with this bug.
Sorry to be bothering you with this.
Thanks in advance and best regards,
~Deimos

[helios]

Was there any problem with std::list<T>?

[kbw]

Helios is right. Why not use the standard one?

Your implementation is unusual. It's traditional to maintain a head/tail pointer and only insert data nodes. It's not clear advantage your guard node offers.

Further, your insert method seems to care about the content of the list. A list is expected to store duplicates, yours doesn't.

Are you moving properties from your app into the list, or is this meant to be a standard list.

[Deimos]

Well, I suppose that the list I'm implementing will never be as fast as the standard one. I just wanted to do it in order to understand things a little better.

The non duplicates code is specific for my purposes. The idea is a "DisplayList" which will store pointers to all in game sprites and render them according to their position on that same list. I don't want any sprite to be rendered twice, that's where !contains(_data) kicks in.

Still, couldn't you find any bug with it?

[jsmith]

Things I've found

1. Node( Type, Node* ) constructor does very bad things if the Node* passed in is NULL;
2. ~CLinkedList() first deletes curr, then dereferences it: curr->curr->ptNext;
3. remove() always seems to remove the first node, whether or not it is the one you're looking for;
4. I'm pretty sure your Node( Type, Node* ) constructor does not work in the case where the
list contains more than just a guard node.

[Deimos]

Thanks a lot, jsmith. The problem lied within the destructor. Its's funny how a new pair of eyes finds the issue much faster. :D

1. Well, only CLinkedList can access Node objects and since there is always a guard node NULL will never be passed to its constructor.
3. Actually, the method find(Type _data) besides returning the address of the node, stores the found node's address on curr, that's why I reset curr to point to the first node after the deletion. :)
4. Nah, it works perfectly. xD

Again, thanks a lot :)

Best Regards
~Deimos

[EDIT]

I compared the performance of my list with the performance of std::list...one test was all it took:

Insertion of 1000 integers:

CLinkedList<int>: 2.171 seconds;
std::list<int>: 0.187 seconds;

I must say I wasn't expecting that my list would perform so badly... What could be the cause of such disparity?

[jsmith]

Just some suggestions (take or leave):

1. From an engineering point of view, I would argue that functions should work for all inputs. The constructor should not crash if NULL is passed; it should do something sane (perhaps throw an exception).

3. Ah, I missed that. Slightly non-intuitive, IMHO. I'd expect find() to be a const member
function that does not modify the state of the object.

[helios]

The std::cout statements seem to be the biggest contributors.

[Deimos]

@helios:
I took 'em all out before running the test.
@jsmith:
Yes, I do belive you're right, I could make it throw an exeption. But, since an exeption needs handling, would an assert(_next) statement do the trick?

[jsmith]

Well, assert() kills the program; no way to stop it.

An unhandled exception also kills the program, but gives the programmer the flexibility to handle the exception and thus not terminate the application.

Therefore, I'd say an exception is better.