A self-referential class contains a member that points to a class object of the same class type. For example, the definition
class Node {
public:
explicit Node(int); // constructor
void setData(int); // set data member
int getData() const; // get data member
void setNextPtr(Node*); // set pointer to next Node
Node* getNextPtr() const; // get pointer to next Node
private:
int data; // data stored in this Node
Node* nextPtr; // pointer to another object of same type
};
defines a type, Node
. Type Node
has two private
data members—integer member data
and pointer member nextPtr
. Member nextPtr
points to an object of type Node
—an object of the same type as the one being declared here, hence the term self-referential class. Member nextPtr
is referred to as a link—i.e., nextPtr
can “tie” an object of type Node
to another object of the same type. Type Node
also has five member functions—a constructor that receives an integer to initialize member data
, a setData
function to set the value of member data
, a getData
function to return the value of member data
, a setNextPtr
function to set the value of member nextPtr
and a getNextPtr
function to return the value of member nextPtr
.
Self-referential class objects can be linked together to form useful data structures such as lists, queues, stacks and trees. Figure 19.1 illustrates two self-referential class objects linked together to form a list. Note that a slash—representing a null pointer (nullptr
)—is placed in the link member of the second self-referential class object to indicate that the link does not point to another object. The slash is for illustration purposes only; it does not correspond to the backslash character in C++. A null pointer normally indicates the end of a data structure.
Not setting the link in the last node of a linked data structure to nullptr
is a (possibly fatal) logic error.
The following sections discuss lists, stacks, queues and trees. The data structures presented in this chapter are created and maintained with dynamic memory allocation (Section 10.9), self-referential classes, class templates (Chapters 7, 15 and 18) and function templates (Section 6.17).