3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ You're missing the includes and the using declarations. Please post complete code. Also, does this actually compile? return true in a void function should give you at least a warning. You tried all functions at least once to instantiate the template, right? Also, all of this is in a single header file, isn't it? \$\endgroup\$ – Zeta Feb 16 '17 at 6:46
  • \$\begingroup\$ Also, do you want to have a review in terms of C++03 or C++11/C++14? \$\endgroup\$ – Zeta Feb 16 '17 at 6:49
  • \$\begingroup\$ Thank you for your input, I will add the includes and the using, And yes the code compiles. And I want review in terms of C++98 if possible. \$\endgroup\$ – Dannz Feb 16 '17 at 6:55
  • \$\begingroup\$ @Dannz, I don't think many of us so ancient to know C++98. I was just born at that time, lol. By the way, didn't you forget references on insert, remove, search? \$\endgroup\$ – Incomputable Feb 16 '17 at 7:00
  • \$\begingroup\$ Your code does not compile. You have to instantiate the class and use the methods to check whether they work with a specific template parameter T. Minimal example to show failing code: int main() { linkedlist<int> int_list; int_list.search(10); }. \$\endgroup\$ – Zeta Feb 16 '17 at 7:09
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ First of all, Thank you for taking the time to reply. I can say that after reading this post I have become a better programmer. And by the way, isn't returning in void is a bad habit for breaking the flow or something? And about adding a tail pointer isn't it making it a double linked-list, Or I could maintain a single linked list with pointer to end and a pointer to start? thank you once again. @Zeta \$\endgroup\$ – Dannz Feb 16 '17 at 8:39
  • \$\begingroup\$ @Dannz Well, the tail pointer allows you to insert at the end. It doesn't allow you to remove at the end, since you cannot find the previous node in constant time. So all it does is to allow constant-time insertion. return; in void is fine. It is a problem in C, since you have to clear your resources. In C++, RAII should take care of that. \$\endgroup\$ – Zeta Feb 16 '17 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.