Where to declare the Node structure when implementing a List in C++

Question

When I faced this problem, I came up with two choices.

The First one is to declare the Node structure inside the List class. It's just like:

class List
{
    private:
          struct Node
          {
              int data;
              Node* next; 
          }
          Node* head;
          //...
    public:
           //....
}

For this one, it works good. Functions in public area can make use of all the elements in Node structure to do insert, delete and so on. Also, this prevent user from directly using the Node structure(I think if we declare Node inside List, others cannot make use of this structure. Is it true?). However, if this Node is very general and will be used also by Stack, Queue and so on, we have to declare it every time. It's inconvenient. Also, if I want to implement some algorithms which works on List(e.g sort), is it possible to do this without even making use of the Node structure?

The second choice is to implement a Node class:

class Node
{
    private:
           int data;
           Node* next;
           //...
    public:
           //...
} 

class List
{
    private:
           Node* head;
           //...
    public:
           //...
}

This one does not work because I can not change pointer and data in Node with functions in public area of class List. If I put data and next in public area of class Node, I am afraid that users can also directly change pointers and destroy the list.

What do people usually do when implementing a List? Thanks ahead for your advice:-)

Answer 1

It is conventional in library code development to put those kinds of "helper" classes (and functions) in a "detail" namespace, i.e., like this:

namespace my_library {

namespace detail {

class Node
{
    public:
           int data;
           Node* next;
           //...

           //...
} 

}

class List
{
    private:
           detail::Node* head;
           //...
    public:
           //...
}

}

By convention, anyone looking or using your library should know that anything in the "detail" namespace (or sub-namespace) is "not safe for public consumption", so to speak. You can also go one step further and put the helper classes in another header (like "List_detail.h") to further "hide" them. Also, when generating your library's documentation (e.g., with doxygen), you should skip / omit / hide any declaration from the "detail" namespace (or sub-namespaces).

You can also place them in an unnamed namespace if that is appropriate (in terms of linking).

Nested classes are sometimes avoided by decree (in coding guidelines) because they are not always well handled by all compilers (mostly old sub-standard compilers).

Answer 2

My advice is to make Node a private, nested struct in List to start with. When and if the need arises to reuse it, you can move it outside List. At that time you will have to make the data of Node public or provide public get and set methods on the data.

Answer 3

You can put your node class in separate header file node.h

class Node
{
    private:
           int data;
           Node* next;
    friend class List;
    friend class Stack; 
    friend class Queue;          
    public:
           Node(int num):data(num), next(NULL)
           {
           }
           int getData()
           {
                return data;
           }
};


#include <node.h>

class List
{
    private:
           Node* head;
    public:
};