Linked List

was bored at work so i decided to implement a linked list. tell me what u think....all criticism is welcomed. i'm here to learn it does not have every single method. (wasn't that bored). oh and i want to know if there's a way u can avoid writing template<class T> before every method besides using define. below is just the class.

Code:

template <class T>
class LinkedList
{
private:
    struct node {
        T data;
        struct node * next,
                    * prev;
    };
    T getDataAtNode(int index);
    struct node * head,
                * end;

public:
    LinkedList();
    LinkedList(T data);
    void push(T data);
    T pop();
    T operator[](int index);
    bool isEmpty();
    void clear();
    int length();
};

template <class T>
T LinkedList<T>::getDataAtNode(int index)
{
    int c = 0; struct node * iter = head;
    while(iter)
    {
        if (c++ == index)
            return iter->data;
        iter = iter->next;
    }
    return NULL;

}

template <class T>
LinkedList<T>::LinkedList()
{
    head = new node();
    head->data = NULL;
    head->next = NULL;
    head->prev = NULL;
    end = head;
}

template <class T>
LinkedList<T>::LinkedList(T data)
{
    if (head != end)
    {
        head = new node();
        end = head;
    }

    head->data = data;
    head->next = NULL;
    head->prev = NULL;

}

template <class T>
T LinkedList<T>::operator[](int index)
{
    return (getDataAtNode(index));
}

template <class T>
void LinkedList<T>::push(T data)
{
    if(head->data == NULL)
    {
        head->data = data;
    }
    else {
        struct node * new_node = new node();
        new_node->data = data;
        new_node->next = NULL;
        new_node->prev = end;
        end->next = new_node;
        end = new_node;
    }
}

template <class T>
T LinkedList<T>::pop()
{
    T data = end->data;
    if(end->prev)
    {
        end = end->prev;
    }
    else
    {
        end = head;
        head->data = NULL;
    }
    end->next = NULL;
    return data;
}

template <class T>
bool LinkedList<T>::isEmpty()
{
    return (head->data == NULL && head == end ? true : false);
}

template <class T>
void LinkedList<T>::clear()
{
    end = head;
    head->data = NULL;
    head->next = NULL;
}

template <class T>
int LinkedList<T>::length()
{
    int c = 0; struct node * iter = head;
    while(iter)
    {
        c++;
        iter = iter->next;
    }
    return c;
}

* Define them in the class declaration.
* Make a macro...
* Don't use templates!

Originally Posted by Sipher

* Define them in the class declaration.
* Make a macro...
* Don't use templates!

what's so bad about templates?

Originally Posted by codeprada

what's so bad about templates?

Nothing, nothing! I was just joking!...

Originally Posted by Sipher

Nothing, nothing! I was just joking!...

lol oh... i'll add something like a cursor, a next() and previous() function....maybe

There's a whole bunch of allocating, don't see no freeing.

>> oh and i want to know if there's a way u can avoid writing template<class T> before every method

Define all of the methods inside of the class.

Also, provide iterators, and provide assignment and copying, at least.

Avoiding writing template: write the code inline in the class.
Suggestions:
Use typename instead of class.
Use std::shared_ptr and std::weak_ptr.
Use nullptr instead of NULL.
Drop the "struct" on the pointers.
Problems:
Not freeing memory!
Class suffers from raw pointer issues (http://sourceforge.net/apps/mediawik...pointer_issues)

Don't implement operator[] - linked list are not for random access, it's inefficient to have to traverse an average of half the list to get an element out.

You should keep track of the size of the list as you add and remove elements so that when you call length() you can return a number straight away. Traversing the list just for this is extremely inefficient!

Implement a copy constructor and operator= or make them private to avoid accidental shallow copying.

Originally Posted by Elysia

Suggestions:
Use std::shared_ptr and std::weak_ptr.
Problems:
Class suffers from raw pointer issues

While I generally agree with the idea of using smart pointers over raw pointers, I think a fundamental utility like this deserves to not have the overhead of smart pointers.

Overhead is negligible. Change it if and only if performance suffers.

Even if performance suffers, I would suck it up. The only differences between a regular pointer and a weak pointer are that the weak one can transfer ownership of the pointee to a reference counted pointer if you ask it to. Since weak pointers aren't doing anything regular pointers don't, the overhead is actually paid at compile time. (From all the template code.) Actually, I should say that weak pointers are probably not the source of performance problems.

Originally Posted by whiteflags

Even if performance suffers, I would suck it up. The only differences between a regular pointer and a weak pointer are that the weak one can transfer ownership of the pointee to a reference counted pointer if you ask it to. Since weak pointers aren't doing anything regular pointers don't, the overhead is actually paid at compile time. (From all the template code.) Actually, I should say that weak pointers are probably not the source of performance problems.

Hmmm, it would be an interesting experiment to, say, run a script through all of an stl implementation to replace all the raw pointers with weak pointers (probably a custom version of weak pointer to wrap pointer arithmetic and such as well) and then to a comparison with some stl intensive code.

That is a very funny joke. There are many parts of the STL that are not bare bones though and template classes become part of other template classes, so if your point in all this is that the STL is all POD implemented, you're wrong anyway.

At any rate, I stand by what I said.

To write an STL container like std::list or even std::vector, a lot of effort is needed. Not only coding and testing but developing interfaces. IMHO your main mistake is implementing some random methods without thinking about the user and the purpose of the class.

Compare it to STL. Where are "front" and "back" methods? Why can I push and pop only in one direction if the list is bidirectional? Are getDataAtNode and operator[] methods really necessary for a list? As you say, "It does not have every single method", but the whole principle is incorrect.

Originally Posted by whiteflags

That is a very funny joke. There are many parts of the STL that are not bare bones though and template classes become part of other template classes, so if your point in all this is that the STL is all POD implemented, you're wrong anyway.

At any rate, I stand by what I said.

I don't quite follow you there. I could see problems with macros maybe but if you create a wrapper class around pointers with an identical interface why shouldn't you be able to drop it in to the stl libraries? It does seem very optimistic that it would be possible to do a simple search and replace, but I don't see why it couldn't be mostly automated and maybe patched up in a few places.