When is a circular reference to a parent pointer acceptable?

Question

This Stack Overflow question is about a child having reference to its parent, through a pointer.

Comments were pretty critical initially of the design being a horrible idea.

I understand this is probably not the best idea in general. From a general rule of thumb it seems fair to say, "don't do this!"

However, I am wondering what sorts of conditions would exist where you would need to do something like this. This question here and associated answers/commentary suggests even for graphs to not do something like this.

Answer 1

The key here is not whether two objects have circular references, but whether those references indicate ownership of each other.

Two objects cannot "own" each other: this causes an intractable dilemma for initialization and deletion order. One must be an optional reference, or otherwise indicate that one object will not manage the other's lifetime.

Consider a doubly-linked list: two nodes link back and forth to each other, but neither "owns" the other (the list owns them both). This means neither node allocates memory for the other or is otherwise responsible for the identity or lifetime management of the other.

Trees have a similar relationship, although nodes in a tree may allocate children and parents do own children. The link from a child to parent helps with traversal, but again does not define ownership.

In most OO designs, a reference to another object as an object's data member implies ownership. For example, suppose we have classes Car and Engine. Neither one is very useful on its own. We can say that these objects depend on each other: they require the presence of the other in order to perform useful work. But which "owns" the other? In this case we would say that Car owns Engine because the car is the "container" in which all of the automotive components live. In both an OO and real-world design, the car is the sum of its parts, and all of those parts are connected together within the context of the car. Engine may have a reference back to Car, or it may have a reference to TorqueConverter, but no component inside of Car owns Car even if said component has a reference to the Car.

Circular references can be a bad design smell, but not necessarily. When used judiciously and documented correctly, they can make using data structures easier.

Try traversing a tree without references going both ways between parents and children. Sure, you could come up with a stack-based approach that is brittle and complex, or you could use the reference-based approach that is trivially simple.

Answer 2

There are several aspects to consider in such a design:

• the structural dependencies
• the ownership relation (i.e.composition vs. other kind of associaton)
• the navigation needs

Structural dependency between classes:

If you aim at reusing component classes, you should avoid unnecessary dependency and avoid such closed circular structures.

Nevertheless sometimes two classes are conceptually strongly interlinked. In this case, avoiding dependency is not a real option. Example: a tree and its leafes, or more generally a composite and its components.

Ownership of objects:

Does one object owns the other ? Or otherwise stated: if one object is destroyed, shall the other be destroyed as well ?

THis topic was addressed in depth by Snowman, so I'll not going to address it here.

Navigation needs between objects:

A last issue is navigation need. Let's take my favourite example, the composite design pattern of the Gang of four.

Gamma & al. explictely mention the potential need to have an explicit parent reference: "Maintaining reference from child componenents to their parent can simplify traversal and management of a composite structure" Of course you could imagine a systematic top-down traversal, but for very large composite objects it can significantly slow down the operations and in an exponential manner. A direct reference, even circular can significantly ease manipulation of your composites.

An example could be a graphical model of an electronic system. A composite structure could represent the electronic boards, circuits, elements. To display and manipulate the model, you'd need some geometrical proxies in a GUI view. It is then certainly much easier to navigate from the GUI element selected by the user to the component, to find out which is the parent and with are the related brother/sister elements, than to start a top down search.

Of course, as Gamma & al pointed out, you have to ensure the invarients of the circular relationship. This can be tricky, as the SO question you refer to has shown. But it's perfectly manageable and in a safe manner.

Conclusion

The navigation need shall not be understimated. It is not without reason that UML has explicitely adressed it in the modelling notation. And yes, there are perfectly valid situation where circular references are needed.

The only point is that sometimes people tend to go into such a direction to quickly. So it's worth to consider all the 3 aspects involved before taking the decision to go for it or not.

Answer 3

Usually, circular references are a very bad idea because they mean circular dependencies. You probably already know why circular depedencies are bad, but for completeness' sake, the tl;dr version is that whenever classes A and B both depend on each other, it's impossible to understand/fix/optimize/etc either A or B without also understanding/fixing/optimizing/etc the other class at the same time. Which quickly leads to codebases where you can't change anything without changing everything.

However, it is possible to have a circular reference without creating evil circular dependencies. This works as long as the reference is strictly optional in a functional sense. By that I mean you could easily remove it from the classes and they would still work, even if they happen to work slower. The main use case I'm aware of for such circular non-dependency-creating references is enabling quick traversal of node-based data structures such as linked lists, trees and heaps. For instance, in principle any operation you can perform on a doubly-linked list you can also perform on a singly-linked list, there just happen to be a few operations (like moving backwards through the list) that have a much better big-O with the doubly-linked version.

Answer 4

The reason it's usually not a good idea to do this is because it violates the Dependency Inversion Principle. People have written a lot about this in much more detail than I can cover adequately in this post, but it boils down to making it difficult to maintain, because the coupling is so tight. Changing either class almost always necessitates a change in the other, whereas if the dependencies only point one way, changes on one side of the interface are isolated. If both classes point to an abstract interface, even better.

The one main exception is when you don't have two different classes at different abstraction levels, but two nodes of the same class, such as in a tree, a doubly-linked list, etc. Here it's more of a structural relationship than an abstraction relationship. Circular references for the sake of algorithmic efficiency are acceptable and even encouraged in these sorts of cases.

Answer 5

[...] suggests even for graphs to not do something like this.

Sometimes you just need to access things in a bottom-up fashion from a different data structure than the tree, while the tree needs to access things in a top-down way.

As an example, a quadtree might store elements in a vector graphics software. However, the user's selection is stored in a separate selection list of vector element references/pointers. When the user wants to delete that selection, we have to update the quadtree, and there it might be a whole lot more efficient to update the tree in a bottom-up fashion starting from the leaves rather than top-down. Otherwise you'd have to, for each element, work from root to leaf and then back up again.

Answer 6

Doom 3 has an example of a child object with a pointer to a parent object. Specifically it uses intrusive lists. To summarize, an intrusive list is like a linked list except each node contains a pointer to the list itself.

Advantages:

• When objects can exist in several lists simultaneously, the memory for the list nodes needs to be allocated and deallocated only once.

• When a object needs to be destroyed, you can easily remove it from all of the lists it's in without searching through each list linearly.

I think this is a pretty specific scenario, but if I understand your question, it's an example of an acceptable use of a child object containing a pointer to its parent object.