Please critique my LinkedList implementation

Question

I am looking for pointers / comments / critiques regarding the below code. One major flaw I know is that I need to define Nodes first and then manually join them to create a List.

Are there any flaws apart from that? C++ programming style errors? RAII?

#include<iostream>

template<typename T>
class Node {
private:
    T data_;

public:
    Node<T>* prev;
    Node<T>* next;

    const T& getData() const { return data_; }
          T& setData()       { return data_; }
    const T& setData(const T& data) {
        data_ = data;
        return data_;
    }

    Node() {
        prev = NULL;
        next = NULL;
    }
};

template<typename T>
class List {
private:
    Node<T>* head_;
    Node<T>* tail_;

public:    
    List() {
        head_ = NULL;
        tail_ = NULL;
    }

    Node<T>* getHead() const { return head_; }
    Node<T>* getTail() const { return tail_; }
    Node<T>* addNode(Node<T> & rhs) {
        if (tail_) {
            tail_->next = &rhs;
            tail_ = tail_->next;
        } else {
            tail_ = &rhs;
            head_ = tail_;
        }
        return tail_;
    }
};

int main() {

    List<int> li;
    Node<int> temp1;
    temp1.setData(5);
    li.addNode(temp1);
    Node<int> temp2;
    temp2.setData(10);
    li.addNode(temp2);

    Node<int>* h = li.getHead();
    while(h) {
        std::cout << h->getData() << std::endl;
        h = h->next;
    }
}

Answer 1

Design

Getters and setters are horrible.

The expose your code to the possibility tight coupling as they expose the internal representation. So remove them. You should be thinking in terms of what actions can be performed on the list and secondly (since this is a container) how do I expose the contained elements.

So I agree with Anton Node should not even be exposed outside the list. Why does the user of the list need to know about Node(s)?

Why does the user need to know about the head and tail of the list. That's an implementation detail. Exposing those will tightly couple your code to require to implement them even if a future version does not have the concept of head and tail internally. Now I can see getting the first and last element of a list (but they don't need to know that internally you have head and tail pointers) and also iterators (but iterators have a much simpler cleaner interface than node*).

Actions that can be done on a list.

• Check for empty (other functions may have a precondition that it is not empty)
• Add an element
• Remove an element (pre-condition not empty)
• ability to traverse the list (usually this mean iterators of some form but there are other ways).
• Access to specific elements
  • Maybe.

Implementation

I would say your list leaks; but it does not actually own the nodes (it should) otherwise how do you gurantee that all the members of the list are valid.

Secondly the addNode()

Node<T>* addNode(Node<T> & rhs) {

This assumes that the passed node is virgin and has not been re-used. Since somebody else created it you can not assume this. You must set the next pointer of rhs to NULL to guarantee that it is correct.

You never set the prev member. So I see no point in having it.

Answer 2

First of all, Node should definitely be a nested type of List -- there's no need to ever expose nodes to the users of the list. You should also be the one to manage the lifetime of the node. You definitely don't want users of the list to be able to assign the next and prev pointers of a node; it makes absolutely no sense to make data (which you care little about hiding) private but to expose implementation details.

While this code is fairly long, it mostly consists of trivial functions that are hard to say anything about, while the key features of a list (abstracted iteration via iterators, abstracted away insertion in the middle) is left for the user to do. There's not much to say.