9.6 SELF-REFERNTIAL STRUCTURES

It is some times desirable to include within a structure one member that is a pointer to the parent structure type.In general terms, this can be expressed as

struct tag  {
member 1;
member 2;
..............
struct tag *name;
};

where name refers to the name of a pointer variable.Thus the structure of type tag will contain a member that points to another structure of type tag. Such structures are known as self-referential structures.

Self referential structures are very useful in applications that involve linked data structures, such as lists and trees.

The basic idea of linked data structure is that each component within the structure includes a pointer indicating where the next component can be found.Therefore, the relative order of the components can easily be changed simply by altering the pointers.In addition, individual components can easily be added or deleted, again by altering the pointers. As a result, a linked data structure is not confined to some maximum number of components.Rather, the data structure can expand or contract in size as required.

Fig. 1 illustrates a  linked list containing three components.Each component consists of two data items; a string and a pointer that references the next component within the list.Thus, the first component contains the string red, the second contains green and the third contains blue.Also, the end of the list is indicated by a special pointer, called NULL.

Now let us add another component, whose value is white, between red and green. To do so, we merely change the pointers as illustrated in fig. 2. Similarly, if we choose to delete the component whose value is green, we simply change the pointer associated with the second component, as shown in fig. 3.

 

In fig. 4 we  see an example of tree. Trees consists of nodes and branches, arranged in some hierarchical manner which indicates a corresponding hierarchical structure within the data.(A binary tree is a tree in which every node has no more than two branches.)

In fig. 4 the root node has the value screen, and the associated branches lead to the nodes whose values are foreground and background, respectively. Similarly, the branches  associated with foreground lead to the nodes whose values are white, green and amber, and the branches associated with background lead to the nodes whose values are black,blue and white.

 Fig. 5 explains the manner in which pointers are used to construct tree.

Self referential structures are ideally suited for applications involving linked data structures.Each structure will represent a single component (i.e. one node) within the linked data structure.The self referential pointer will indicate the location of the next component.