Avoiding pointers in this C++ linked list

Question

As I know it is not good idea to have so many pointers in c++ code. But I have written this simple implementation of linked list in c++ and there are many pointers in it, how can I improve that? Also as I tried I can not use functions in algorithm module on this linked list, how can I make this class compatible with those?

template <typename T>
class linkedlist {
private:
    struct node {
        node() : T() {
        }

        node(node * prev, node * next, const T & data) :
                prev(prev), next(next), data(data) {
        }

        node * next;
        node * prev;
        T data = T();
    };

    node first;
    node last;

public:
    linkedlist() :
            first(nullptr, &last, T()),
            last(&first, &last, T()) {
    }

    class iterator {
        friend class linkedlist;
    private:
        node * current_node;

    public:
        iterator(node * current_node) : current_node(current_node) {
        }

        T & operator*() {
            return current_node->data;
        }

        const T & operator*() const {
            return current_node->data;
        }

        iterator & operator++() {
            current_node = current_node->next;
            return *this;
        }

        bool operator!=(const iterator & other) {
            return current_node != other.current_node;
        }
    };

    void add(const T & data) {
        node * new_node = new node(last.prev, &last, data);
        new_node->prev->next = new_node;
        new_node->next->prev = new_node;
    }

    bool remove(iterator & iterator) {
        if (iterator.current_node == &first || iterator.current_node == &last)
            return false;
        node *to_remove = iterator.current_node;
        to_remove->prev->next = to_remove->next;
        to_remove->next->prev = to_remove->prev;
        delete to_remove;
        return true;
    }

    iterator begin() {
        return iterator(first.next);
    }

    iterator end() {
        return iterator(&last);
    }

    iterator find(const T & data) {
        for (iterator it = begin(); it != end(); ++it) {
            if (*it == data) {
                return it;
            }
        }
        return end();
    }
};

Answer 1

I see some things that may help you improve your code.

Write member initializers in declaration order

One of the constructors for node looks like this:

node(node * prev, node * next, const T & data) :
        prev(prev), next(next), data(data) {
}

That looks fine, but in fact, next will be initialized before prev because members are always initialized in declaration order and next is declared before prev in this class. To avoid misleading another programmer, you should swap the order of those such that it says instead:

node(node * prev, node * next, const T & data) :
        next(next), prev(prev), data(data) {
}

This way the initialization actually proceeds from left to right as one might expect at first glance.

Eliminate the default constructor

At the moment, one of the constructors for node is written like this:

node() : T() { }

However, this is not good at all since, if it were ever used, it would leave next and prev uninitialized. Better would be to explicitly delete it like this:

node()  = delete;

Add a destructor

Because you're allocating memory with new you must also deallocate it with delete or your program will leak memory. Here's one way to write it:

virtual ~linkedlist() {
    for (auto it = begin(); it != end(); it = begin()) {
        remove(it);
    }
}

Provide move semantics for iterators

Right now, it's not possible to do this:

linkedlist<std::complex<float>> ll;
ll.remove(ll.begin());

The reason is that ll.begin() is an "rvalue" and so can't be passed as a reference. To fix this, create a version of remove with move semantics:

bool remove(iterator &&iterator) {
    if (iterator.current_node == &first || iterator.current_node == &last)
        return false;
    node *to_remove = iterator.current_node;
    to_remove->prev->next = to_remove->next;
    to_remove->next->prev = to_remove->prev;
    delete to_remove;
    return true;
}

Provide const versions of iterators

The cbegin() and cend() forms of the iterators are missing. Here's a simple cbegin():

iterator cbegin() const {
    return iterator(first.next);
}

Provide an initializer_list constructor

At the moment, this form of the constructor doesn't work:

linkedlist<std::complex<float>> ll{{3,4}, {5,12}};

It's simple to add, however:

linkedlist(std::initializer_list<T> list) :
        first(nullptr, &last, T()),
        last(&first, &last, T()) 
{
    for (auto &item : list) {
        add(item);
    }
}

Provide copy function or delete it

At the moment, a copy function is compiler generated but almost certainly not what you want because it will only copy pointers and not the underlying data. Either delete the function explicitly or provide one.

Provide member functions to suit the data structure

A linked list is not a very good data structure for many purposes, but one thing that is efficient is the ability to insert one linked list within another (a splice). Unfortunately, this function is not provided, so any advantage is unrealized.

Provide a full iterator implementation

In order to use the algorithms in <algorithm>, you will need first class iterators, but although somewhat useful, yours are missing a number of pieces. See this reference page for details on what a real iterator provides.