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:-)

They do neither because they don't reinvent the wheel. They use std::list<>, and often not even that, opting for either std::vector<> or std::deque<>. That said, unless you have to expose the node as an external entity or are sharing it with other classes as their "node" type, there is little reason to make it stand-alone. — WhozCraig
– WhozCraig, Commented Mar 26, 2014 at 5:13

Mikael Persson · Accepted Answer · 2014-03-26 05:33:21Z

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).

R Sahu · Accepted Answer · 2014-03-26 05:26:47Z

0

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.

answered Mar 26, 2014 at 5:26

R Sahu

207k15 gold badges168 silver badges291 bronze badges

Comments

Dipika · Accepted Answer · 2014-03-26 06:35:47Z

0

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:
};

answered Mar 26, 2014 at 6:35

Dipika

5843 silver badges12 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related