Having circular references is a logic bug.
I don't believe there's any algorithm in existence that requires circular references.
I don't believe there's any algorithm in existence that requires circular references.
This isn't the point though. A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Even if such a restriction was in place it would have to be enforced at runtime which doesn't sound like a trivial problem from a performance point of view.
But that's not really the question here. Any linked list is not an algorithm, it's a data structure.
The question is what operations can you do using circular references cannot be done without. I think otabdeveloper1 is right, because you can use a garbage collection type process to 'run' any other algorithm on a graph with cycles in it, using temporary lists and stacks to do whatever the algorithm would use circular references for.
The question is whether it's a reasonable constraint for real-world programs. In theory, Malbolge can be used to perform any algorithm, but few people would actually want to.
Circular references are really convenient in many cases. For example, view hierarchies typically have a pointer from a view back to its parent view. This means you can walk up the view hierarchy as well as down, so you can find sibling views, remove a view from its parent, invalidate a parent's layout when the view's sizing needs change, and stuff like that. Without circular references you could still accomplish all this, it just becomes slower and more painful.
In practice, reference cycles are a big problem for ARC. One of the most common questions I see with Objective-C and Swift programmers is when it's necessary to use a weak reference to self in a block, and when it's necessary to use a strong reference. It's difficult enough that I've seen a lot of people just punt on the entire question and go for "always capture self as a weak reference no matter what." Which works most of the time, and occasionally creates entertaining bugs. Even for experienced developers it's easy to miss a spot occasionally, and end up with a silent leak or a subtle bug.
Not really, no. There's no reason why the backlink should increment the reference count.
Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. E.g., circular references are never a problem in C++.
> A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this.
Really? Why not? "We don't support refcounted circular references, please rewrite your code if you use them" is a perfectly valid design decision. Personally, I'd rather have that than some rube-goldberg type monstrocity of a memory management system just to support a very obscure corner case.
How so?
If the weak references are safe (as in, their pointer is assigned to 0 when the target object is collected) then I think there can be performance issues (compared to the competition of a tracing GC).
If the weak references aren't safe, then you have a data structure that's more in the realm of manual memory management, so it's hard to draw a fair comparison with fully memory-managed objects.
With an eager implementation, you need to ensure that deallocation and zeroing is atomic. The entire operation of decrement refcount -> deallocate -> zero weak references can't be interrupted by looking up a weak reference. In a multithreaded environment that means there's locking needed.
However, you can do a lazy implementation which doesn't suffer so much. Here, you keep a separate weak reference count in the object itself. When the normal reference count reaches zero, you deinitialize the object (decrement the refcount of anything it refers to, run custom deinitialization code if any), but leave the memory for the object itself intact. Then, upon accessing a weak reference, you can just check to see if the target is in this "zombie" state, and zero out the weak reference at that point. Once the weak reference count also reaches zero, the object memory can be deallocated.
Objective-C uses the eager approach for weak references, which is necessary because of compatibility concerns. Swift uses the lazy approach with native Swift objects, although it still has to use the eager approach for subclasses of Objective-C classes.
Assume you have an algorithm that does make use of circular references. Then, you could replace all pointers by integers. And you could put all referenced data into a large array.
That way you would have "broken up" all circular references. However, from another point of view, you could argue that your algorithm still makes use of circular references, they are just expressed differently.
(Also, now no garbage collector will help you cleaning up that thing, other than releasing that large array at once. So that's not really an improvement.)
Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.