2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ You should take a look at including a "sentinel" value in your list. Using this removes a lot of complicated code around handling empty lists. \$\endgroup\$ – Martin York Sep 12 '15 at 9:09
  • \$\begingroup\$ DLL.h/.c is a bad name for the source files. People will think it is some code related to Dynamic Link Libraries. \$\endgroup\$ – glampert Sep 12 '15 at 17:56
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you much. It seems that using unconventional conditions and initializations in for loops are no good and less useful than using them in a while loop, also it will lead to less errors. Thanks, all the advice was good however I have one question. You said use as little as possible external references like my isEmpty() method. I am curious because couldn't using external functions that I have defined in a class be useful and help modularize my code? For example, using a length() function over and over again as opposed to counting till null every time \$\endgroup\$ – Dominic Farolino Sep 14 '15 at 2:44
  • \$\begingroup\$ That's not exactly accurate. I didn't say: "use as little as possible". I said: "don't use if you don't need". It's fine to use non-local elements when you need them, or useful, or improve clarity. In the destructor in this example you simply didn't need them, and the implementation is clearer without them. \$\endgroup\$ – janos Sep 14 '15 at 6:58
1
\$\begingroup\$

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.

\$\endgroup\$

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.