Thread: 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

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)

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.