Why is no explicit reference required in this linked list?

Question

In this mutable linked list implementation, there is no Ref{ListNode{T}}:

mutable struct ListNode{T}
    data::T
    prev::ListNode{T}
    next::ListNode{T}
end

To edit the list, it uses code like next.prev = prev.

My ordinary understanding is that structs are embedded in place (like the would be in C). This does not allow editing the list without recreating it in its entirety. To have a reference/pointer to a struct instead, one would use Ref{ListNode{T}}.

From the code, this understanding is clearly wrong: prev::ListNode{T} is already a pointer that can be changed easily. But I don't see why this is the case. Are structs in Julia embedded as pointers by default? Possibly only if they are mutable?

I could not really find a concrete description of the behavior in the docs. It talks about heap/stack allocation, but not the much more fundamental issue of direct vs. pointer allocation.

Answer 1

TL;DR: immutable structs in Julia are "embedded" like in C. mutable structs are heap-allocated and stored as pointers internally. Self-referential initialization is required to avoid the incomplete initialization problem, and instead of checking for null pointers like you would in C, you have to check for circular references.

structs in Julia are in general similar to C structs, i.e. embedded in-place as you describe it. Such types are called isbitstypes in Julia. When inside a function, constructors of such types result in "allocation on the stack", i.e. similar to structs in C.

help?> isbitstype
search: isbitstype

  isbitstype(T)

  Return true if type T is a "plain data" type, meaning it is immutable
  and contains no references to other values, only primitive types and
  other isbitstype types. Typical examples are numeric types such as
  UInt8, Float64, and Complex{Float64}. This category of types is
  significant since they are valid as type parameters, may not track
  isdefined / isassigned status, and have a defined layout that is
  compatible with C.

  See also isbits, isprimitivetype, ismutable.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> isbitstype(Complex{Float64})
  true

  julia> isbitstype(Complex)
  false

Mutable structs on the other hand, are heap-alloc'd. From the Composite Types section of the manual.

In order to support mutation, such objects are generally allocated on the heap, and have stable memory addresses. A mutable object is like a little container that might hold different values over time, and so can only be reliably identified with its address. In contrast, an instance of an immutable type is associated with specific field values –- the field values alone tell you everything about the object. In deciding whether to make a type mutable, ask whether two instances with the same field values would be considered identical, or if they might need to change independently over time. If they would be considered identical, the type should probably be immutable.

So, the main reason for heap-allocating them is that in the most general case, even the types of the struct members can change, as shown in the example.

julia> mutable struct Bar
           baz
           qux::Float64
       end

julia> bar = Bar("Hello", 1.5);

julia> bar.qux = 2.0
2.0

julia> bar.baz = 1//2
1//2

Coming to the struct that you defined:

julia> isbitstype(ListNode{Int64})
false

julia> sizeof(ListNode{Int64}) # 8 + 2*8 = 24 bytes
24

julia> sizeof(ListNode{Tuple{Int64,Int64}})  # 2*8 + 2*8 = 32 bytes
32

Does this mean that the default ListNode{T} constructor uses a pointer/reference internally? Yes, but the value semantics do not allow you to use those internal references as pointers for your linked list. You cannot just assign null pointers to them.

julia> ListNode{Int}(1, Ptr{ListNode{Int}}(), Ptr{ListNode{Int}}())
ERROR: MethodError: Cannot `convert` an object of type Ptr{ListNode{Int64}} to an object of type ListNode{Int64}
Closest candidates are:
  convert(::Type{T}, ::T) where T at Base.jl:61
  ListNode{T}(::Any, ::Any, ::Any) where T at REPL[1]:2
Stacktrace:
 [1] ListNode{Int64}(data::Int64, prev::Ptr{ListNode{Int64}}, next::Ptr{ListNode{Int64}})
   @ Main ./REPL[1]:2
 [2] top-level scope
   @ REPL[26]:1

in your particular case you will run into the incomplete initialization problem The docs have a section on this (Incomplete Initialization). Julia allows you to call new in the inner constructor using fewer values to leave the recursive members uninitialized.

mutable struct ListNode{T}
    data::T
    prev::ListNode{T}
    next::ListNode{T}
    
    # inner constructor
    ListNode(data::T) where T = new{T}(data)
end

julia> head = ListNode(1)
ListNode{Int64}(1, #undef, #undef)

julia> head.next = ListNode(2)
ListNode{Int64}(2, #undef, #undef)

julia> head
ListNode{Int64}(1, #undef, ListNode{Int64}(2, #undef, #undef))

So, to answer your question:

Are structs in Julia embedded as pointers by default? Possibly only if they are mutable?

Yes, they are embedded as pointers only if they are mutable. Although, you should really not be using this detail to hack together pointers of a linked list node.

julia> head.next.next === undef
ERROR: UndefRefError: access to undefined reference
Stacktrace:
 [1] getproperty(x::ListNode{Int64}, f::Symbol)
   @ Base ./Base.jl:38
 [2] top-level scope
   @ REPL[11]:1

julia> typeof(head.prev)
ERROR: UndefRefError: access to undefined reference
Stacktrace:
 [1] getproperty(x::ListNode{Int64}, f::Symbol)
   @ Base ./Base.jl:38
 [2] top-level scope
   @ REPL[8]:1

Accessing undefined fields tries to dereference these pointers directly, so you cannot really check for null pointers like you would in C. Either use Ref and friends instead, or you can make this particular struct work by completely initializing using circular references instead of returning incompletely initialized objects.

mutable struct ListNode{T}
    data::T
    prev::ListNode{T}
    next::ListNode{T}

   ListNode(data::T) where T = (n = new{T}(data); n.prev = n; n.next=n)
end

istail(l::ListNode{T}) where T = l === l.next

julia> head = ListNode(1)
ListNode{Int64}(1, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))

julia> head.next = ListNode(2)
ListNode{Int64}(2, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))

julia> head.next.next = ListNode(3)
ListNode{Int64}(3, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))

julia> istail(head.next.next)
true

julia> istail(head.next)
false

As it turns out, DataStructures.MutableLinkedList does exactly this. If you look at their implementation of the iteration interface (that allows you to write for x in list for you type), the termination condition is implemented by checking for a circular reference.

Base.iterate(l::MutableLinkedList, n::ListNode) = n === l.node ? nothing : (n.data, n.next)