If all data types are made non-recursive using tricks like a table of node IDs linking to data and data uses only other node IDs to form a graph, then can all memory be managed using just Reference Counting?
Furthermore is it possible to express a immutable list with the standard set of Haskell-like functions for the list in a language like C++ and guarantee no memory leaks using only reference counting?
Reference counting requires you to be more aware of object lifetimes. When creating a graph in a reference counting environment, you would create a parent object that owns all nodes in the graph. If the nodes in the graph have some concept of direction, then references from the top to the bottom can also be strong references. However, undirected connections or backlinks need to be weak refs that do not increment the reference counting. This is fine, since the graph-owning object ensures all nodes live long enough. This doesn't even need reference counting: C++- or Rust-style lifetime management is sufficient.
This prevents memory leaks in the sense that all nodes managed through this graph are eventually deallocated (when the whole graph is deallocated). However, if any particular node in the graph is not referenced by other nodes, it will still stay alive. Of course, that might be intentional (not all graphs are connected graphs). You also cannot remove a node from this graph, unless you sweep all nodes to make sure it isn't referenced. This means you are essentially re-implementing your own GC.
(Proper memory management is needed to ensure memory safety: that data cannot be referenced if it was deallocated.)
Even outside of mathematical graphs, such owning collections are actually quite common in many practical problems. E.g. with the repository pattern, the repository would own all entities that it manages. Other code only borrows references to each entity. Relations between entities do not need to use strong refs.
So while reference counting is an acceptable solution to nearly all memory management problems (the exceptions being relations with unclear ownership, or the need to remove unreferenced nodes), the technique has a number of significant drawbacks:
In reality, the only reasons to use reference counting instead of GC are:
You will still have to keep track of which nodes of your graph are reachable. This could be done with a sequence of "live node" collections ordered by "generation", where as part of construction of new nodes you store what is reachable from that node, and then when you drop a generation the reference counting will collect them.
This is however basically re-implementing an "eagerly evaluating" generational GC, where it does the collection work as things are allocated, rather than before they are destroyed.
Once you have your immutable graph, you also have your immutable list (as a restricted case).
If all data types are made non-recursive using tricks like a table of node IDs linking to data and data uses only other node IDs to form a graph, then can all memory be managed using just Reference Counting?
Moving from pointers as references to ID-based references doesn't change the problem. In fact it can make it worse!
The properties of immutable data are pretty strong, and even with recursive data types, immutable data suppresses pointer reference cycles, because an old object/data could not have known a future created object reference when it was created (thus it can't reference future objects) and also cannot later be changed to reference a new object. Therefore, immutable data is always directed and acyclic with respect to pointer-based references.
However, using ID's or names as a referencing mechanism, an immutable object can be created that references future immutable object, which references the old immutable object, and thus, using names for references instead of pointers, we can create cycles with immutable data.
Furthermore is it possible to express a immutable list with the standard set of Haskell-like functions for the list in a language like C++ and guarantee no memory leaks using only reference counting?
A singly linked list, yes. However, for a doubly linked list: A doubly linked list is a recursive data type that also creates cycles with pointer-based references.
Simple or naive reference counting would fail to release any nodes of the list, if the list as a whole became unreferenced. The only way to collect the items would be to delete each and every one from the list.
Smart reference counting would be required to handle that, which is to say that the various references need to be differentiated, as @amon describes, say, as strong vs. weak. The strong ones count and the weak ones don't. Some systems attempt strong vs. weak differentiation at runtime, dynamically and automatically; other systems tag the references at compile time via the type system; some mix the two.
Have a look at Objective C and Swift, they use Automatic Reference Counting (automatic as compiler-supplied assistance) for their memory management. Also note problematic areas for ARC, especially around closures.
And yet still, in garbage collected languages, like Java and C#, we easily and commonly "leak" memory. All you need is a long lived collection or data structure that grows over time but isn't properly shrunk over time. This is a slightly different notion of memory leak, but has the same effect in that if the program runs long enough, it will run out of memory. This can even happen in functional languages that enforce immutable data, say like Erlang.
