Singly linked list template implementation

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
using namespace std;

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

template
class linkedlist {
template
friend ostream &operator &rhs);
private:
node *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 &rhs) const;
bool operator!=(const linkedlist &rhs) const;
bool operator &rhs) const;
bool operator>(const linkedlist &rhs) const;
};

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

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

template
bool linkedlist::operator>(const linkedlist& rhs) const
{
return rhs
bool linkedlist::operator==(const linkedlist &rhs) const
{
node *lhsTemp = head;
node *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;
}

t

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 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 
linkedlist & linkedlist::operator=(const linkedlist &rhs)
{
    if (this != &rhs)
    {
        // ... cut

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

        // undefined behaviour, since rhs.head does not point
        // to something valid.
        for (node *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
        {
            tmpHead->next = new node(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 
linkedlist & linkedlist::operator=(const linkedlist &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(rhs.head->data);

        node * current = head;

        for (node *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
        {
            current->next = new node(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 
linkedlist & linkedlist::operator=(const linkedlist &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
void linkedlist::remove(const T data)
{
    if(isEmpty())
    {
        return;
    }

    if (head->data == data)
    {
        node * 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 *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.

StackExchange Code Review Q#155495, answer score: 5