Linked list nodes: pros and cons of each approach to writing them

[Lehti]

I'm currently in the middle of studying for my Programming 2 finals, which essentially is a practical test about data structures and sorting algorithms.
We've been taught by a C programmer who showed us only the implementation with head as a private member. I've experimented a bit and have come up with two other approaches, but I'm not sure about which one I should use when I write linked lists.

Approach #1
structs

This is a slightly different spin on what we've seen in class. I've added a ctor (the professor didn't because "structs can't have methods", in his own words)

template <typename T>
struct Node {
    Node(T data) {
        this->data = data;
        this->next = nullptr;
    T data;
    Node *next;
}

Pros:
- Quick to implement
- No need for defining getters and setters
Cons:
- Pretty much no encapsulation

Approach #2
classes

Similar to the struct approach, but this one uses public getters and setters and a private variable data and pointer to the next element

template <typename T>
class Node {
public:
    Node(T data) {
        this->data = data;
        this->next = nullptr;
    }
    void set_data(T data) { this->data = data; }
    void set_next(Node *next) { this->next = next; }
    T get_data() const { return data; }
    Node* get_next() const { return next; }
private:
    T data;
    Node *next;
}

Pros:
- Encapsulation

Cons:
- More code to type
- Slightly awkward syntax[/code]

Approach #3
friend class

This is what I found myself using the most.

template <typename T>
class Node {
    friend class List<T>;
    Node(T data) {
        this->data = data;
        this->next = nullptr;
    }
    T data;
    Node *next;
}

Pros:
- Best encapsulation of all (cannot instantiate nodes outside of a List)
- Quick to write
Cons:
- Not easily extensible (friendliness doesn't extend to classes derived from List)

Does anyone know of any other approaches to writing nodes? And what do you guys think about the ones I described?

[jonnin]

your prof is wrong (maybe you knew that). The primary difference between a class and a struct in modern c++ is that struct is default public on all, class is default private on all, both can be overridden with the keywords of course. Both can have methods etc.

eh. your nodes have pointers.

What if your node pointer were instead just an unsigned integer?
what if that integer was the index into a vector that was tied to the class, possibly a static one that every node shared?
you could iterate that easier.
you can count the nodes easier.
you don't have to fool with memory / pointer stuff.
you can copy it, <algorithm> it, and more really easily.

cons: the list order and the vector order need not be the same, and probably won't be after a short time. sorting and searching.. you need to be very careful. You can't for example just sort the vector and search it, because that changes what points to what in the list. But you can copy the list and sort the copy, if that is useful. There are times when this approach will be much, much better than a pointer based approach. But its something to think about.

<list> may already be doing some of this or similar tweaks. I honestly haven't studied HOW it is implemented much.

[JLBorges]

> Does anyone know of any other approaches to writing nodes?

This is what I would do:

template < typename T >
struct list
{
    // in the public interface, there is no hint of there being
    // an implementation detail called node

    void push_back( const T& v )
    {
        if( last ) { last->next = new node{ v, nullptr, last } ; last = last->next ; }
        else first = last = new node{v} ;

        ++sz ;
    }
    // etc.

    private: // or protected:

        // best encapsulation: the type node is not available outside list
        struct node // node is an implementation detail of list
        {
            // there is no need to make anything private here
            // the entire type is already encapsulated

            T value ;
            node* next = nullptr ;
            node* prev = nullptr ;
        };

        node* first = nullptr ;
        node* last = nullptr ;
        std::size_t sz = 0 ;
        // ...
};