Doubly linked list implementation in C++

Question

I made this C++ doubly linked list implementation and it seems to work right, handle everything well, and not have any errors. However, I've been working with it for a while and would like some fresh eyes to take a look and see if I am missing anything large or if my code contains any 'gotchas'.

Side note: I ran valgrind on several tests of this implementation and never got any memory leaks so I suspect it is handling that end of this correctly.

DLL.H

#ifndef DLL
#define DLL

class DoublyLinkedNode {
public:
    int info;
    DoublyLinkedNode *next, *prev;

    DoublyLinkedNode() {
        next = prev = 0;
    }

    DoublyLinkedNode(int nu, DoublyLinkedNode *ne = 0, DoublyLinkedNode *pre = 0) {
        info = nu;
        next = ne;
        prev = pre;
    }
};

class DoublyLinkedList {
private:
    DoublyLinkedNode *head, *tail;
public:
    DoublyLinkedList() {
        head = tail = 0;
    }

    ~DoublyLinkedList();

    bool isEmpty() const {
        return head == 0;
    }

    void addToHead(int);
    void addToTail(int);
    int removeFromHead();
    int removeFromTail();
    void remove(int);
    bool isInList(int) const;

};

#endif

DLL.cpp

#include <iostream>
#include "DLL.h"


DoublyLinkedList::~DoublyLinkedList() {
    for (DoublyLinkedNode *p; !isEmpty();) {
        p = head->next;
        delete head;
        head = p;
    }
}

void DoublyLinkedList::addToHead(int n) {
    if(head == 0){
        head = new DoublyLinkedNode(n);
        tail = head;
        return;
    }

    DoublyLinkedNode *tmp = new DoublyLinkedNode(n, head);
    head->prev = tmp;
    head = tmp;

}

void DoublyLinkedList::addToTail(int n) {
    if (tail != 0) {
        tail = new DoublyLinkedNode(n, 0, tail);
        tail->prev->next = tail;
    } else {
        head = tail = new DoublyLinkedNode(n);
    }
}

int DoublyLinkedList::removeFromHead() {
    int el = head->info;
    if(head == tail) {
        delete head;
        head = tail = 0;
    } else {
        head = head->next;
        delete head->prev;
        head->prev = 0;
    }
    return el;
}

int DoublyLinkedList::removeFromTail() {
    int el = tail->info;
    if(head == tail) {
        delete tail;
        head = tail = 0;
    } else {
        tail = tail->prev;
        delete tail->next;
        tail->next = 0;
    }
    return el;
}

void DoublyLinkedList::remove(int n) {
    if (head != 0) {

        if(head == tail) {
            delete head;
            head = tail = 0;
        } 

        if(head->info == n) {
            removeFromHead();
            return;
        }

        if(tail->info == n) {
            removeFromTail();
            return;
        }

        DoublyLinkedNode *tmp;
        tmp = head;
        while(tmp != 0) {
            if (tmp->info != n) {
                tmp = tmp->next;
            } else {
                tmp->prev->next = tmp->next;
                tmp->next->prev = tmp->prev;
                delete tmp;
                tmp = 0;
                //return;
            }
        }
    }
}

bool DoublyLinkedList::isInList(int el) const {
    DoublyLinkedNode *tmp;
    for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
    return tmp != 0;
}

Answer 1

Unusual API

Some method names are a bit unusual in a linked list, here are some more common alternatives:

• addToHead -> addFirst, unshift, prepend
• addToTail -> add, addLast, append
• removeFromHead -> removeFirst, shift
• removeFromTail -> removeLast, pop
• isInList -> contains

Information hiding

Users of DoublyLinkedList don't need to be aware of DoublyLinkedNode. This implementation detail can be hidden. I suggest to make it private by moving it out of the header file.

Naming

The naming is quite terrible at places. Here's the worst part:

DoublyLinkedNode(int nu, DoublyLinkedNode *ne = 0, DoublyLinkedNode *pre = 0) {
    info = nu;
    next = ne;
    prev = pre;
}

It would be better to call "ne" -> "next" and "pre" -> "prev", and "nu" -> "info" and use this-> on the left hand sides:

DoublyLinkedNode(int info, DoublyLinkedNode *next = 0, DoublyLinkedNode *prev = 0) {
    this->info = info;
    this->next = next;
    this->prev = prep;
}

"info" is an unusual name for the payload in a linked list node. "value" or "data" would be better.

Instead of DoublyLinkedNode, I'd call it simply Node. As it can be private, and it's unlikely to need any other kind of node in the linked list implementation.

Constructor initialization

There's a simpler way of initializing variables in the constructor:

DoublyLinkedNode(int info, DoublyLinkedNode *next = 0, DoublyLinkedNode *prev = 0) : info(info), next(next), prev(prev) {}

Use nullptr

Instead of setting pointers to 0 to null them out, it's recommended to use nullptr. You might need to enable this in your compiler, for example with g++ you can pass the --std=c++0x flag.

Avoid external references when you don't really need them

This loop in the destructor makes references to head and isEmpty defined elsewhere:

for (DoublyLinkedNode *p; !isEmpty();) {
    p = head->next;
    delete head;
    head = p;
}

It would be more clear and simple to avoid such external references:

for (DoublyLinkedNode * node = head; node != nullptr;) {
    DoublyLinkedNode * toDelete = node;
    node = node->next;
    std::cout << "deleting: " << toDelete->info << "\n";
    delete toDelete;
}

For loop without body

The for loop in this method doesn't have a body. This is not recommended.

bool DoublyLinkedList::isInList(int el) const {
    DoublyLinkedNode *tmp;
    for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
    return tmp != 0;
}

The reason the loop doesn't have a body is because of the !(tmp->info == el) in the loop condition. That condition doesn't belong there. It's recommended to put in the loop condition only what concerns the iteration process, in this example checking if the loop variable tmp has reached the end of the list or not.

The condition !(tmp->info == el) is about something else, it's about evaluating the return value of the function. That condition would be much better in the loop body, like this:

bool DoublyLinkedList::isInList(int el) const {
    for (DoublyLinkedNode * node = head; node != nullptr; node = node->next) {
        if (node->info == el) {
            return true;
        }
    }
    return false;
}

Also note that this alternative also saves an extra boolean check.

Answer 2

Bug

You are missing a return statement at the end of this block, in remove():

    if(head == tail) {
        delete head;
        head = tail = 0;
    }

Right now, if you use remove() on a list with one element, it will enter that block and keep going. This will result in a NULL dereference on the very next line.

Redundant

Actually that block of code is also redundant. Since you already have a case for removing the head of the list (the next block of code), and that case correctly handles one item lists, you can remove that whole block of code.

There was something wrong with the if statement anyway, which was that it didn't check to make sure that the one item in the list actually matched the n requested for removal.