Simple imperative doubly linked list

Question

I've started learning C++ and still making my first program. This is a continuation of my last post.

My original aim was to make a linked list at a professional level. But have now changed it to a doubly linked list, to simplify the code. It implements a couple of public functions that should increase the usability of the list significantly.

I also tried to implement an internal iterator. But didn't see a benefit to making a bidirectional iterator, for internal use, to replace getNode.

Whilst I think I improved all problems mentioned in my last post. I mostly focused on implementing the sentinel. I don't think it's a sentinel, as it's doing more than just being my end condition. And so I'd love some feedback on my implementation. But any and all critiques are wanted.

#include <iostream>

template <class T>
class LinkedList {
private:
    class Node {
    public:
        Node* next;
        Node* prev;
        T data;
        // For the sentinal
        Node(): data('\0'), prev(this), next(this) {}
        Node(T data, Node* before)
                : data(data) {
            prev = before;
            next = before->next;
            prev->next = this;
            next->prev = this;
        }
        ~Node() {
            prev->next = next;
            next->prev = prev;
        }
        Node(Node const&)            = delete;
        Node& operator=(Node const&) = delete;
    };
    Node sentinal;
    Node* getNode(int index) {
        if (index >=  0) {
            int i = 0;
            for (Node* node = sentinal.next; node != &sentinal; node = node->next) {
                if (i == index) {
                    return node;
                }
                i++;
            }
        } else {
            int i = -1;
            for (Node* node = sentinal.prev; node != &sentinal; node = node->prev) {
                if (i == index) {
                    return node;
                }
                i--;
            }
        }
        throw std::out_of_range("List doesn't contain that item.");
    }
public:
    LinkedList() {}
    ~LinkedList() {
        clear();
    }
    LinkedList(LinkedList const&)            = delete;
    LinkedList& operator=(LinkedList const&) = delete;

    void clear() {
        while (sentinal.next != &sentinal) {
            delete sentinal.next;
        }
    }

    int length() {
        int length = 0;
        for (Node* node = sentinal.next; node != &sentinal; node = node->next) {
            length += 1;
        }
        return length;
    }

    void append(T data) {
        new Node(data, sentinal.prev);
    }

    T get(int index) {
        return getNode(index)->data;
    }

    void insert(T data, int index) {
        new Node(data, getNode(index)->prev);
    }

    T pop(int index=-1) {
        Node* node = getNode(index);
        T data = node->data;
        delete node;
        return data;
    }
};

int main() {
    LinkedList<char> list;
    list.append('h');
    list.append('l');
    list.append('l');
    list.append('l');
    list.append('o');
    list.insert('e', 1);
    std::cout << list.pop(2) << list.get(-1) << '\n';
    for (int i=0; i < list.length(); i++) {
        std::cout << list.get(i);
    }
    std::cout << '\n';
    list.clear();
    std::cout << list.length() << '\n';
}

Answer 1

Fundamental Capabilities

Let's start with a really fundamental question: why do you want a linked list to start with?

At least among the basic linear data structures, linked lists offer one capability that's unique: inserting/deleting data in the middle of the linked list in constant time. That can be a single node, or it can be an arbitrary number of nodes that themselves form a linked list.

Now let's consider what your linked list class does to take advantage of that capability: nothing. It provides me with no possibility of doing an insertion or deletion in the middle of the list in constant time.

Iterators

The advantages of iterators over a function like your getNode relate to the preceding. In particular, although finding a particular spot in a linked list has linear complexity, once you have such a point, you can do insertions/deletions with constant complexity. Oh, but with your getNode, every such operation starts with a (linear-complexity) traversal of the list to get to the required point.

This becomes particularly interesting when we do things like sorting, where we typically need to refer to a number of different parts of the list simultaneously. For example, one common implementation of a Quicksort is to traverse a collection both from front to back and back to front simultaneously, and exchange data between the two locations if they're out of order. With this design of linked list, what was supposed to be a Quicksort quickly degenerates into a "really slow sort". The sort overall should have \$O(N log N)\$ complexity, but with this list design, it'd end up something like \$O(N^2 log N)\$--even worse than a typical bubble sort.

Answer 2

• getNode does not replace an iterator. It always starts at the beginning of the list. It means that scanning over the list has a quadratic time complexity.

• A Node default constructor is dubious. It assumes that T can be constructed from a NUL character. It seems like an unnecessary restriction. Assuming that T itself has a default constructor, and using it is more logical.

• length() method is expected to have a constant time complexity. A linear one is at best surprising. I recommend to make a member, to be incremented at each insertion, and decremented on each removal.