Self-Referential Classes

A self-referential class contains a reference member that refers to an object of the same class type. For example, the class declaration in Fig. 25.1 defines the shell of a self-referential class named Node. This type has two private instance variablesinteger data and Node reference next. Member next references an object of type Node, an object of the same type as the one being declared herehence, the term "self-referential class." Member next is referred to as a link (i.e., next can be used to "tie" an object of type Node to another object of the same type). Class Node also has two propertiesone for instance variable data (named Data) and another for instance variable next (named Next).

Figure 25.1. Self-referential Node class declaration.

(This item is displayed on page 1324 in the print version)

 1 // Fig. 25.1: Fig25_01.cs
 2 // A self-referential class.
 3 class Node
 4 {
 5 private int data; // store integer data
 6 private Node next; // store reference to next Node
 7
 8 public Node( int dataValue )
 9 {
10 // constructor body
11 } // end constructor
12
13 public int Data
14 {
15 get
16 {
17 // get body
18 } // end get
19 set
20 {
21 // set body
22 } // end set
23 } // end property Data
24
25 public Node Next
26 {
27 get
28 {
29 // get body
30 } // end get
31 set
32 {
33 // set body
34 } // end set
35 } // end property Next
36 } // end class Node

Self-referential objects can be linked together to form useful data structures, such as lists, queues, stacks and trees. Figure 25.2 illustrates two self-referential objects linked together to form a linked list. A backslash (representing a null reference) is placed in the link member of the second self-referential object to indicate that the link does not refer to another object. The backslash is for illustration purposes; it does not correspond to the backslash character in C#. A null reference normally indicates the end of a data structure.

Figure 25.2. Self-referential class objects linked together.

Common Programming Error 25 1

Not setting the link in the last node of a list to null is a logic error.

Creating and maintaining dynamic data structures requires dynamic memory allocationa program's ability to obtain more memory space at execution time to hold new nodes and to release space no longer needed. As you learned in Section 9.9, C# programs do not explicitly release dynamically allocated memoryrather, C# performs automatic garbage collection.

The new operator is essential to dynamic memory allocation. Operator new takes as an operand the type of the object being dynamically allocated and returns a reference to an object of that type. For example, the statement

Node nodeToAdd = new Node( 10 );

allocates the appropriate amount of memory to store a Node and stores a reference to this object in nodeToAdd. If no memory is available, new throws an OutOfMemoryException. The constructor argument 10 specifies the Node object's data.

The following sections discuss lists, stacks, queues and trees. These data structures are created and maintained with dynamic memory allocation and self-referential classes.

Good Programming Practice 25 1

When creating a large number of objects, test for an OutOfMemoryException. Perform appropriate error processing if the requested memory is not allocated.