Why can't a struct have a member that is of the same type as itself?

Question

I'm stuck on understanding what's happening with this struct (from C for Programmers a Deitel book).

The book says, "A structure cannot contain an instance of itself. For example, a variable of type struct employee cannot be declared in the definition for struct employee. A pointer to struct employee, however, may be included."

It then gives the following example:

struct employee2 {
   char firstName[ 20 ];

   char lastName[ 20 ];

   unsigned int age;

   struct employee2 *ePtr;
};

I don't understand what this is doing, and I don't understand the reference to struct employee without the 2.

How does struct employee2 *ePtr know about struct employee or am I off basis here?

Answer 1

A more meaningful example might be

struct employee2* manager;

Note that to remove the * means the C compiler must lay out the 44 (or so) bytes needed for the top-level employee, then another 44 bytes for the next inner employee, then the 44 for the next next inner employee, then 44 for the next next next inner employee... and so forth. Needless to say this is a compile error.

Furthermore this impossible structure would force them to all be distinct employees, and would require that when you create any employee you create all the managers, which have to be not null, and distinct. This means you can't have a CEO, whereas with a pointer the CEO's manager could be NULL or herself, depending on your implementation. It also makes it rather impossible to change managers without deleting a record from the employee system (i.e. firing an employee) and recreating it (hiring), which also requires revoking building access, computer access, and so forth. My point in saying this is that to not have a pointer is a really, really bad way to model what's going on in the real world.

However the C compiler can lay out 44 bytes for the employee then 4 for the address of the employee's manager, which will in turn point to 44+4 bytes, if it's not null. Note these aren't necessarily distinct bytes - perhaps an employee is her own manager (your business logic should prohibit this but hey, what does C care).

A lower-level example is a linked list, which goes something more like this:

typedef struct {
    int data;
    node* next;
} node;

But again, same idea. Unless you have all infinity distinct nodes ready to create at once, this won't work. Linked lists will end in a NULL value, which is possible to express with a pointer, but not a structure that can't be null since it needs to take memory.

Anyway pointers are ways for one structure to refer to another structure without physically laying out the memory again. C is a low level language but if you learn to think from the point of view of the compiler some higher level concepts will make sense. For instance, to delete the * would also mean that an employee "owns" her manager. This doesn't make sense from a real-world perspective and doesn't make sense from a memory management perspective. (Although, there are senses in which parents can own children... this isn't a perfect analogy here.)