Singly linked list template implementation

Question

My implementation is only for study purposes, I agree that some of the features may be counter-intuitive.

I guess the best method is to use a list in the STL library.

Any improvements will be greatly appreciated.

The following code compiles and works, If possible I would like the code reviewed in C++98, If not the closest to him which is C++03;

#include <iostream>
using namespace std;

template <class T>
struct node {
    node(T data) : data(data), next(NULL) {}
    T data;
    node<T> *next;
};

template <class T>
class linkedlist {
    template<class U>
    friend ostream &operator<<(ostream &os, const linkedlist<U> &rhs);
private:
    node<T> *head;
public:
    linkedlist() : head(NULL) {};
    ~linkedlist();
    linkedlist(const linkedlist &rhs);
    linkedlist &operator=(const linkedlist &rhs);
    void insert(const T data);
    bool search(const T data) const;
    void remove(const T data);
    bool isEmpty() const;
    bool operator==(const linkedlist<T> &rhs) const;
    bool operator!=(const linkedlist<T> &rhs) const;
    bool operator<(const linkedlist<T> &rhs) const;
    bool operator>(const linkedlist<T> &rhs) const;
};

template <class T>
bool linkedlist<T>::operator!=(const linkedlist<T> &rhs) const
{
    return !(*this == rhs);
}

template<class T>
bool linkedlist<T>::operator<(const linkedlist<T>& rhs) const
{
    node<T> *lhsTemp = head;
    node<T> *rhsTemp = rhs.head;
    while (lhsTemp != NULL && rhsTemp != NULL)
    {
        if (lhsTemp->data > rhsTemp->data)
            return false;
        lhsTemp = lhsTemp->next;
        rhsTemp = rhsTemp->next;
    }
    return true;
}

template<class T>
bool linkedlist<T>::operator>(const linkedlist<T>& rhs) const
{
    return rhs < *this;
}

template <class T>
bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const
{
    node<T> *lhsTemp = head;
    node<T> *rhsTemp = rhs.head;
    while (lhsTemp != NULL || rhsTemp != NULL)
    {
        if (lhsTemp != NULL && rhsTemp == NULL || lhsTemp == NULL && rhsTemp != NULL)
            return false;
        else if (lhsTemp->data != rhsTemp->data)
            return false;
        lhsTemp = lhsTemp->next;
        rhsTemp = rhsTemp->next;
    }
    return true;
}

template<class T>
linkedlist<T>::~linkedlist()
{
    while (head != NULL)
    {
        node<T> *tmp = head;
        head = head->next;
        delete tmp;
    }
    delete head;
}

template<class T>
linkedlist<T>::linkedlist(const linkedlist & rhs) : head(NULL)
{
    *this = rhs;
}


template <class T>
linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs)
{
    if (this != &rhs)
    {
        node<T> *temp;
        while (head != NULL)
        {
            temp = head;
            head = head->next;
            delete temp;
        }

        if (rhs.head != NULL)
            head = new node<T>(rhs.head->data);

        node<T> *tmpHead = head;

        for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
        {
            tmpHead->next = new node<T>(tmp->data);
            tmpHead = tmpHead->next;
        }
    }
    return *this;
}

template<class T>
void linkedlist<T>::insert(const T data)
{
    if (head == NULL)
    {
        head = new node<T>(data);
    }
    else
    {
        node<T> *temp = head;
        for (temp = head; temp->next != NULL; temp = temp->next);
        temp->next = new node<T>(data);
    }
}

template<class T>
bool linkedlist<T>::search(const T data) const
{
    if (head == NULL)
        return false;

    for (node<T> *tmp = head; tmp != NULL; tmp = tmp->next)
        if (tmp->data == data)
            return true;

    return true;
}

template<class T>
void linkedlist<T>::remove(const T data)
{
    bool removed = false;
    node<T> *curr = head;
    node<T> *prev = head;

    for (; curr != NULL && removed == false; curr = curr->next)
    {
        if (head->data == data)
        {
            node<T> *tmp = head;
            head = head->next;
            delete tmp;
            removed = true;
        }
        else if (curr->data == data)
        {
            node<T> *tmp = curr;
            prev->next = curr->next;
            delete tmp;
            removed = true;
        }
        prev = curr;
    }
}

template<class T>
bool linkedlist<T>::isEmpty() const
{
    return head == NULL;
}

template<class T>
ostream & operator<<(ostream & os, const linkedlist<T>& rhs)
{
    for (node<T> *temp = rhs.head; temp != NULL; temp = temp->next)
    {
        os << temp->data;
        if (temp->next != NULL)
            os << ", ";
    }
    return os;
}

Answer 1

Never use using namespace std in a header. While using namespace std is already considered bad practice in general, it's especially evil in a header file. It affects every file that includes your header.

Next, hide your node. It's an implementation detail. You can put it in a detail namespace, inside your linkedlist class, or in another header. But it shouldn't be readily available to an end-user.

Furthermore, you have an inconsistent naming convention. Your variables are written in camelCase, your methods are written in camelCase, but your class is just linkedlist. The sample size is too small to see how you want to name your methods. However, linkedlist is harder to read than LinkedList, linkedList or linked_list.

It's great that you implemented > in terms of < and != in terms of ==. Great way to reduce duplicate code! But why stop there? You have duplicated your code in several other places. For example clearing the list is done in both operator= and ~linkedlist(). Provide a clear() function, e.g.

void clear () {
    while(head != NULL) {
        node_ptr tmp = head->next;
        delete head;
        head = tmp;
    }
}

By the way, that node_type? That's something you could definitely add to your class for your own convenience:

typedef node<T> node_type;
typedef node_type* node_ptr;

While we're at it, you have to be very careful in those const methods. You can still accidentally change your list:

head->data = T(); // compiles fine

Your code doesn't have that error as far as I can see, but you can keep it safe by using const more often:

template <class T>
bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const
{ //vvvvv
    const node<T> *lhsTemp = head;
    const node<T> *rhsTemp = rhs.head;
    while (lhsTemp != NULL && rhsTemp != NULL)
    {
        if (lhsTemp->data != rhsTemp->data)
            return false;
        lhsTemp = lhsTemp->next;
        rhsTemp = rhsTemp->next;
    }
    return (lhsTemp == NULL) && (rhsTemp == NULL);
}

And while we're in those operators, you should check whether both sides are the same. That way you can short-cut the operation:

template <class T>
bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const
{
    if(this == &rhs) {
        return true;
    }

    // other function as above        
}

You can use the same method in operator<.

Errors

Your code has several errors. Some of them will prevent your code from compiling, some of them will lead to undefined behaviour.

Errors during compilation

Let's start with the compiler errors. Here's the part you should remember: whenenver you use a template, the compiler will only instantiate the methods if you actually use them. For example your search function does not compile, since its signature uses void, although it returns a bool:

template
void linkedlist::search(const T data) const
{
    if (head == NULL)
        return false;

    for (node *tmp = head; tmp != NULL; tmp = tmp->next)
        if (tmp->data == data)
            return true;

    return true;
}

That won't compile. Or your compiler should yell at you, but it doesn't want to. Make suire that you enable warnings.

Undefined behaviour

In operator=, your for loop must not run if rhs is empty:

template <class T>
linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs)
{
    if (this != &rhs)
    {
        // ... cut

        // let's say rhs.head == NULL

        // undefined behaviour, since rhs.head does not point
        // to something valid.
        for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
        {
            tmpHead->next = new node<T>(tmp->data);
            tmpHead = tmpHead->next;
        }
    }
    return *this;
}

Also, you have a nice little function to check whether a list is empty. Use it. And tmpHead is somewhat misleading. You don't have a temporary head, you have a temporary last element or tail. But since we focus on only one node at a time, let's call it current:

template <class T>
linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs)
{
    if (this != &rhs)
    {
        clear(); // the function at the start of this review

        if(rhs.isEmpty()) {
            // short cut, since the other list is empty
            return *this;
        }

        head = new node<T>(rhs.head->data);

        node<T> * current = head;

        for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
        {
            current->next = new node<T>(tmp->data);
            current = current->next;
        }
    }
    return *this;
}

By the way, why is it a bad idea at the moment to use insert, although it makes your code a lot easier?

template <class T>
linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs)
{
    if (this != &rhs)
    {
        clear(); // the function at the start of this review

        for(const_node_ptr tmp = rhs.head; tmp != NULL; tmp = tmp->next)
        {
            insert(tmp->data);
        }
    }
    return *this;
}

This is a lot easier to read, and you can easily check that it's correct. But why is it a bad idea at the moment? And what can you do to change that?

More on that in the last section of the review. By the way, const_node_ptr is

typedef const node_type * const_node_ptr

We have to define it that way, because

const node_ptr == node_type * const

which would mean that your pointer is constant, but not the value it points to.

Further improvements

Your remove is a tad to complex. Don't be afraid to simply return when you're done with the job. And move conditions that should be checked once out of a loop:

template<class T>
void linkedlist<T>::remove(const T data)
{
    if(isEmpty())
    {
        return;
    }

    if (head->data == data)
    {
        node<T> * tmp = head;
        head = head->next;
        delete tmp;

        return;
    }

    for (node_ptr curr = head->next, prev = head; curr != NULL; curr = curr->next)
    {
        if (curr->data == data)
        {
            node<T> *tmp = curr;
            prev->next = curr->next;
            delete tmp;

            return;
        }
        prev = curr;
    }
}

The function didn't really get shorter, but it's now easier to reason about its behaviour.

Now it's time to talk about insert. You had about a screen page to think about it, which isn't really much time, sorry. But what's the current problem? Why is it a bad idea to use it in operator=?

Because you have to traverse the whole list for every insertion. This would change your current operator= from \$\mathcal O(n)\$ to \$\mathcal O(n^2)\$. So how could you fix this? It's somewhat easy: You have to remember not only the first, but also the last element of the list. A tail.

Note that this will make all functions that remove elements more awkward. Your current implementation works, but if you want to have an \$\mathcal O(1)\$ insert, you really need another pointer in your linkedlist.

Further remarks

Your implementation is fine, but it is. Hm. Not very helpful. You can only insert things into your list, and you can check whether something is in there (and remove it). The following functions would at least help to access some elements:

• front() for the first element
• removeFirst() to remove the first element
• back() for the last element (only if you've added tail above).

And last but not least, your remark about STL:

I guess the best method is to use a list in the STL library.

Yes. It's usually a good idea to use what's already there. However, your linkedlist has only one function to add elements at the end. If you only add elements at the end, use std::vector. Not std::list. You only want to use std::list if you need to insert in the middle of the list very often. But std::list isn't really cache friendly. It depends on what you want to do with your container. See this benchmark for more information.