Double linked list c++

Question

I'm trying to figure out double linked lists. I'm looking for any type of comments you might have for my code. Anything that will make it better.

#include <iostream>

using std::cout;
using std::endl;
using std::clog;
using std::cerr;

class List {
private:
    struct node{
        node* n_next;
        node* n_prev;
        int n_data;
        node(int data = 0)
            :n_next(NULL)
            ,n_prev(NULL)
            ,n_data(data){}
    };
    node* m_head;
    node* m_tail;
public:
    List() :m_head(NULL) ,m_tail(NULL) {}
    List(const List& listObj) {
        m_head = m_tail = NULL;
        for(node* tmp = listObj.m_head; tmp!=NULL; tmp=tmp->n_next) {
            addToTail(tmp->n_data);
        }
    }
    List& operator=(List listObj){
        m_head = m_tail = NULL;
        for(node* tmp = listObj.m_head; tmp!=NULL; tmp=tmp->n_next) {
            addToTail(tmp->n_data);
        }
    }
    ~List() {
        node* tmp = m_head;
        while(tmp) {
            m_head = tmp;
            tmp = tmp->n_next;
            delete m_head;
        }
    }
    void addToHead(int data = 0) {
        if(m_head) {
            node* tmp = new node();
            tmp->n_data = data;
            tmp->n_next = m_head;
            m_head->n_prev = tmp;
            m_head = tmp;
            //clog << "+m_head @ " << m_head <<endl;
        } else {
            node* tmp = new node();
            tmp->n_data = data;
            m_head = tmp;
            m_tail = tmp;
            //clog << "+m_head @ " << m_head <<endl;
        }
    }
    void addToTail(int data = 0) {
        if(m_head) {
            node* tmp = new node();
            tmp->n_data = data;
            tmp->n_prev = m_tail;
            m_tail->n_next = tmp;
            m_tail = tmp;
            //clog << "+m_tail @ " << m_tail <<endl;
        } else {
            node* tmp = new node();
            tmp->n_data = data;
            m_head = tmp;
            m_tail = tmp;
            //clog << "+m_head @ " << m_head <<endl;
        }
    }
    void addAfterN(int pos = 0, int data = 0) {
        if( pos == 0 ) {addToHead(data); return;}

        int i = 0;
        for(node* tmp = m_head ; tmp!=NULL; tmp=tmp->n_next)
            {i++;}
        if( i < pos ) {
            cerr << "no such node" << endl;
        } else {
            node* tmp = m_head;
            for(int i=0; i<pos-1; i++){
                tmp=tmp->n_next;
            }
            node* newNode = new node();
            newNode->n_data = data;
            newNode->n_next = tmp->n_next;
            newNode->n_prev = tmp;
            tmp->n_next->n_prev = newNode;
            tmp->n_next = newNode;
        }
    }

    void deleteHead(){
        node* tmp = m_head;
        m_head = m_head->n_next;
        m_head->n_prev = NULL;
        delete tmp;
    }
    void deleteTail(){
        node* tmp = m_tail;
        m_tail = m_tail->n_prev;
        m_tail->n_next = NULL;
        delete tmp;
    }
    void deleteN(int pos = 0, bool fromHead = true) {
        if( pos==0 &&  fromHead ) {deleteHead(); return;}
        if( pos==0 && !fromHead ) {deleteTail(); return;}

        int sum = 0;
        for(node* tmp = m_head; tmp!=NULL; tmp=tmp->n_next) {sum++;}
        if( sum<=pos ) { cerr << "no such node" << endl; return; }

        else {
            if(fromHead) {
                node* tmp = m_head;
                for(int i=0; i<pos; i++){
                    tmp = tmp->n_next;
                }
                if(tmp->n_prev)tmp->n_prev->n_next = tmp->n_next;
                if(tmp->n_next)tmp->n_next->n_prev = tmp->n_prev;
                delete tmp;
            } else {
                node* tmp = m_tail;
                for(int i=0; i<pos; i++){
                    tmp = tmp->n_prev;
                }
                if(tmp->n_prev)tmp->n_prev->n_next = tmp->n_next;
                if(tmp->n_next)tmp->n_next->n_prev = tmp->n_prev;
                delete tmp;
            }
        }
    }

    void printList(bool ascending = true) const {
        if( ascending ){
            for(node* tmp = m_head; tmp!=NULL; tmp=tmp->n_next) {
                cout << tmp->n_data <<endl;
            }
        } else {
            for(node* tmp = m_tail; tmp!=NULL; tmp=tmp->n_prev) {
                cout << tmp->n_data <<endl;
            }
        }
    }
    int getN(int pos = 0, bool fromHead = true) const {
        int sum = 0;
        for(node* tmp = m_head; tmp!=NULL; tmp=tmp->n_next)
            {sum++;}
        if( sum<=pos ) {
            cerr << "no such node" << endl;
            return 0;
        } else {
            if(fromHead) {
                node* tmp = m_head;
                for(int i=0; i<pos; i++){
                    tmp=tmp->n_next;
                }
                return tmp->n_data;
            } else {
                node* tmp = m_tail;
                for(int i=0; i<pos; i++){
                    tmp=tmp->n_prev;
                }
                return tmp->n_data;
            }
        }
    }
};

int main(void) {
    List foo;
    foo.addToTail(1);
    foo.addToTail(2);
    foo.addToTail(3);
    foo.printList();
    return 0;
}

Answer 1

Warning: this has a lot of text and very little code. You've inadvertently gotten close to the black hole of exception safety, and your life may never be quite the same. Or you might not care, and prefer to ignore all of this exception safety "stuff", at least for now.

Assignment operator

A few problems have already been pointed out: it receives its parameter by value, so a complete copy of the source is made just to be passed as the parameter, then it's destroyed as soon as the assignment completes.

It also leaks all the nodes currently in the list when an assignment happens.

It also fails to return a value of the type it's defined to return, so it has undefined behavior.

I'm going to disagree, however, with @Simon Kraemer on one point though. At least in my experience, testing for self-assignment is usually a net loss. The problem is that self assignment happens extremely rarely, but you execute the test for it every time. Given how rarely it happens, the time you save when it does happen doesn't make up for the time you spend checking for it the rest of the time. Worse, since it does happen so rarely the CPU will predict that you're not going to do that, so even when you do run into self assignment, you don't gain as much as you might think anyway.

Finally, I'll note that the basic approach taken in your current assignment operator is difficult to make exception safe. What you'd usually like is what's called strong exception safety. This means that an assignment does one of two things: it succeeds, so the list takes on the new value, or else it fails completely, and the list remains exactly as it was before.

In your case, you start by destroying the current contents of the list. Then you try to copy the source list. If that fails (e.g., new throws an exception) you end up with a list that's neither the "before" nor the "after" state, and may not be in a usable state at all (e.g., may have a node that's been added partially, but not completely).

Fortunately, although that list of problems is pretty long, there are some fairly easy ways to deal with them. One common approach is called the copy and swap idiom. The idea here is that instead of throwing away the current list, then copying the existing list, you reverse the order: first copy the existing list, then swap its contents with the existing list. The swap only requires modifying some pointers (not allocation) so it can't throw an exception.

The code for that looks something like this:

List& operator=(List const &listObj){
    List temp(listObj);
    std::swap(m_head, temp.head);
    std::swap(m_tail, temp.tail);
    return *this;
}

Yes, I know: after that amount of text, there should be more code. Sorry 'bout that. :-)

Seriously though, it's probably worth analyzing what this is doing, and how/why it does it.

This starts by creating a copy of the source list. We then swap the head and tail pointers of the destination of the assignment with the head and tail pointers of that copy of the source list. This means the destination object is now a copy of the source object. The temporary (which was a copy of the source object) now contains the data we want to destroy. That's local to the assignment operator--so as soon as the assignment operator returns, it will be destroyed (so we no longer leak the old contents of the list).

The result is strong exception safety: only one of two results can happen: either the assignment completely succeeds, or else it completely fails, and the list remains exactly as it was previously.

Copy Constructor

The trick we just used can be seen as kind of a cheat--it leaves most of the hard work to the copy constructor. That quickly leads to another question: is the copy constructor exception safe? Unfortunately, no, it's not.

In particular, if new throws an exception in the middle of its execution, it will leak all the nodes that were copied successfully. The problem here is fairly simple: until/unless the ctor returns successfully, you don't actually have an object. So, if an exception is thrown in the middle of the copy constructor trying to do its thing, the destructor for that object will not execute automatically to destroy it.

Therefore, it's your responsibility to catch any exceptions, and if you do, you need to undo what you'e done so far.

List(const List& listObj) {
    try {
        for(node* tmp = listObj.m_head; tmp!=NULL; tmp=tmp->n_next) {
            addToTail(tmp->n_data);
        }
    catch(...) { 
        while (m_head != nullptr)
            deleteTail();
        throw; // re-throw the exception, so callers know construction failed
    }
}

There is one caveat here: in some cases you want to "eat" the exception that was thrown, and throw some other exception in its place. For example, in this case it might be reasonable to catch bad_alloc, and in its place throw a failed_copy or something on that order.

Move assignment

The preceding has one major problem: in some cases it's pretty inefficient. In particular, it makes a complete copy of a linked list, even when that's not really needed. Consider something like:

List get_some_data(some_input) {
    List ret_val;
    // ...
    return ret_val;
}

This (potentially) ends up making a complete copy of the list that will almost immediately get thrown away. The "potentially" part is that the compiler is free to optimize out at least some such copies, and often will.

We can add a little bit to the code to help out though, by defining a move constructor and move assignment operator:

List(List &&src) { 
    m_head = src.m_head;
    m_tail = src.m_tail;

    src.m_head = nullptr;
    src.m_tail = nullptr;
}

List &operator=(List &&src) { 
    this->~List(); // Destroy our current contents

    m_head = src.m_head;
    m_tail = src.m_tail;

    src.m_head = nullptr;
    src.m_tail = nullptr;

    return *this;
}

Note the parameter type here: the && means each takes what's called an rvalue reference as its parameter. To make a long story short, this signifies a value that doesn't need to be preserved--so we don't. We steal the contents out of the parameter, so making the "copy" is fast and cheap (we just copy a couple of pointers).

When we do this, we're required to leave the source in a state that it can at least be destroyed safely, so we just null out its member pointers. That's not the only possibility, but it's pretty typical.

Answer 2

Some remarks:

1. You could use nullptr instead of NULL: What exactly is nullptr?
2. You could use size_t instead of int for indizes. Currently your code will crash if you pass a negative value as pos (see deleteN, getN)
3. You could keep track of the size of the list, so you don't need to calculate it every time you access it via pos. Also this might make it nice getter.
4. Why don't you pass data in the constructor of your node. Also you could make the constructor of node take all three arguments data, prev and next and pass them accordingly when creating a node.
5. There is no need for default initialization of data anywhere in your code.
6. Your assignment operator List& operator=(List listObj) should take a const reference: List& operator=(const List& listObj) like your copy constructor.
7. Your assignment operator should check whether the passed object is the list itself and do nothing if so.
8. Your assignment operator does currently not check if there is already any data in the list. You need to clean up first (delete all nodes) before initializing the object with the new data from the other list. Otherwise you have a memory leak.
9. Your assigment operator doesn't return anything. Add return *this;.
10. Why do deleteN and getN have a fromHead yet addAfterN has not?
11. Instead of, or additional to, printList you might want to implement an ostream operator.

12. Try to avoid duplicate code.

    else {
        if(fromHead) {
            node* tmp = m_head;
            for(int i=0; i<pos; i++){
                tmp = tmp->n_next;
            }
            if(tmp->n_prev)tmp->n_prev->n_next = tmp->n_next;
            if(tmp->n_next)tmp->n_next->n_prev = tmp->n_prev;
            delete tmp;
        } else {
            node* tmp = m_tail;
            for(int i=0; i<pos; i++){
                tmp = tmp->n_prev;
            }
            if(tmp->n_prev)tmp->n_prev->n_next = tmp->n_next;
            if(tmp->n_next)tmp->n_next->n_prev = tmp->n_prev;
            delete tmp;
        }
    }
    

    Could be written as

    else {
        node* tmp = nullptr;
        if(fromHead) {
            tmp = m_head;
            for(int i=0; i<pos; i++){
                tmp = tmp->n_next;
            }
        } else {
            tmp = m_tail;
            for(int i=0; i<pos; i++){
                tmp = tmp->n_prev;
            }
        }
        if(tmp->n_prev)tmp->n_prev->n_next = tmp->n_next;
        if(tmp->n_next)tmp->n_next->n_prev = tmp->n_prev;
        delete tmp;
    }