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)

Originally Posted by Mozza314

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.

Finally, someone else who points out this kind of thing! I wholeheartedly agree.

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!

GCC actually walks the list to get the size. The reason that some implementations do and some don't is that there is a trade off between constant time size() and linear time splice() vs linear time size() and constant time splice(). Can't do both in constant time.


C++ has the notion that you only pay for what you use. If you don't need a smart pointer in there then you should not be forced to. Simply allow the user of the class to use a smart pointer as their templated type.

Or you mean as the links themselves? That's actually not a good idea. If you utilised that to automatically delete the whole list by deleting just the first node say, then you end up with a recursive delete and could blow the stack, for example.
In a list, nodes don't own subsequent nodes. It's just a sequence. Enforcing some kind of ownership semantics where it doesn't belong is just wrong.

Originally Posted by Mozza314

I actually learned about this complication just the other day flicking through Scott Meyers' "Effective STL". Really makes the point that you should never do

Code:

someList.size() == 0

since that can be linear time and you have the perfectly appropriate empty() function you can use instead.

I find myself reasonably often bringing this up in code reviews or running into it in older code. Other's at work only use Microsoft's compilers, and simply don't know that the difference can be quite important if you're writing portable code.

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.