19.3 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. 19.1 defines the shell of a self-referential class named Node. This type has two properties—Data (an int) and Next (a Node). Next references another Node object—that is, an object of the same type as the one being declared here, hence the term “self-referential class.” Next is referred to as a link (like the links in a chain).

Fig. 19.1 Self-referential Node class declaration.

Alternate View 

 1   // Fig. 19.1
 2   // Self-referential Node class declaration.
 3   class Node
 4   {
 5      public int Data { get; set; } // store integer data
 6      public Node Next { get; set; } // store reference to next Node
 7
 8      public Node(int data)
 9      {
10         Data = data;
11      }
12   }

Self-referential objects can be linked together to form useful data structures, such as lists, queues, stacks and trees. Figure 19.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 link normally indicates the end of a data structure.

Common Programming Error 19.1

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

Fig. 19.2 Self-referential class objects linked together.

Creating and maintaining dynamic data structures requires dynamic memory allocation—a 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 10.8, C# programs do not explicitly release dynamically allocated memory—rather, the CLR 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


var nodeToAdd = new Node(10);

allocates the appropriate amount of memory to store a Node, initializes it 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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset