# Efficient recursive iteration over self referencing struct

**URL:** <https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322>\
**Category:** Performance\
**Created:** [June 24, 2022, 9:05pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322 "2022-06-24T21:05:41Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 24, 2022, 9:05pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/1 "2022-06-24T21:05:41Z")

</div>

Suppose i have a `Node` type that may have a reference to itself on one of its fields. What is the most efficient way to implement `Base.iterate` for this `Node` type, such that at every iteration we get the next child `Node`?

```julia
julia> const Maybe{T} = Union{T, Nothing}
Union{Nothing, T} where T

julia> struct Node{T}
           name::String
           value::T
           child::Maybe{Node}
       end

julia> Base.iterate(::Node) = ??

```

Thanks in advance!

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 7:16am UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/2 "2022-06-25T07:16:51Z")

</div>

I was trying to _overengineer_ the solution for this problem, and it turns out it is more simpler than i thought, but i’m still no sure if there’s a more efficient way, however, this works for now:

```julia
julia> function Base.length(node::Node)
           len = 0
           while !isnothing(node)
               len += 1
               node = node.child
           end
           return len
       end

julia> Base.iterate(node::Node, state::Node = node) = state, state.child

julia> Base.iterate(node::Node, ::Nothing) = nothing

julia> node = Node("x", 1, Node("y", 2, Node("z", 3)))
Node{Int64}("x", 1, Node{Int64}("y", 2, Node{Int64}("z", 3, nothing)))

julia> length(node)
3

julia> collect(node)
3-element Vector{Any}:
 Node{Int64}("x", 1, Node{Int64}("y", 2, Node{Int64}("z", 3, nothing)))
 Node{Int64}("y", 2, Node{Int64}("z", 3, nothing))
 Node{Int64}("z", 3, nothing)

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [June 25, 2022, 7:31am UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/3 "2022-06-25T07:31:48Z")

</div>

When you say “more efficient”, what exactly are you imagining the inefficiency to be? There are some ways you can make a linked list more efficient cache-wise, but they require quite a few changes. Just accessing the struct member and checking whether it’s nothing is probably as good as you can get with just this approach.

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 7:48am UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/4 "2022-06-25T07:48:47Z")

</div>

By “more efficient”, i mean _fast_, a non-naive solution. I’m not good at writing efficient (_fast_) code. For most of the time in the past i didn’t care much about effiency and optimization, as long as my code was working it was fine, but now i want to be better at write efficient code. So if anybody has a better solution for the problem that i described explaining why is better it would be of much help.

(Sorry for my english: i actually speak portuguese)

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [June 25, 2022, 8:15am UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/5 "2022-06-25T08:15:28Z")

</div>

I see! Well, the inefficiency of linked lists is inherent to the datastructure. What you’re asking about is how you can make a linked list faster in and of itself, and the “proper” answer to that would be “don’t use a linked list” (assuming you want to make reading faster). Another complication is that linked lists truly are better for some workloads, but this depends on how you want to use them. There is no One-size-fits-all perfect datastructure.

Are you familiar with Big-O notation?

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [June 25, 2022, 3:26pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/6 "2022-06-25T15:26:45Z")

</div>

I do not remember seeing a fast linked list implementation, I should write a package with one, but I believe I do not have the time for now.

The fastest way I know to implement a linked list is with two `Vector`, it works very well if the list starts populated and mostly suffer removals, and/or the insertions are few and distributed among the whole list. However, if you need to insert a lot of elements between other elements already present you either do your way or maybe go for `OrderedCollections.jl`.

The two-`Vector` way consists in a _data_ `Vector{T}` which will keep the elements (no initialization is necessary) and a _next_ `Vector{Int}` which points to the next position from the current position. If you want to start with everything populated you just create a data Vector with the elements in order, and `1:length(data)` as the _next_. It can be circular (the last _next_ can be one) or not (use `0` or other sentinel value in the last _next_ position). If you think you will add elements, you can make it double the size, initialize only the odd data positions, and have _next_ be `[3, 0, 5, 0, 7, ...]`. So if you can put new elements between each pair of current elements and future shifts will the the smallest possible. Is this understandable? This is just a very bare-bones explanation.

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 3:57pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/7 "2022-06-25T15:57:29Z")

</div>

> [@Sukera](#):
>
> answer to that would be “don’t use a linked list”

Interesting, i’m know about Data Structures, but i’m still noob when it comes to choose which one is better for the job.

> [@Sukera](#):
>
> Are you familiar with Big-O notation?

Yes, i’m familiar.

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 4:04pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/8 "2022-06-25T16:04:35Z")

</div>

I think i understand what you mean. One day i watched a video about implementing a GUI library in Rust using Data-Oriented Programming, so instead of creating a wigdet structure with references to its children and parents, there was another structure that behaves as a ‘manager’ which stored each widget on a `Vector` and the child of each widget as indices on another `Vector`. At the time i did not understanded correctly, but now it starting to make sense. Thanks for your answer.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [June 25, 2022, 5:08pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/9 "2022-06-25T17:08:31Z")

</div>

Not my best work, but supports sparsity, circularity (given one or more starting elements), and iteration. May implement removal and insertion after.

```julia
module FastLinkedLists

struct SingleLL{T, N}
	data :: Vector{T}
	next :: Vector{N}
end

"""
    function SingleLL(data, ::Type{N} = Int; kwargs...) where {T, N}

Create a linked list with unidirectional links (forward). NOTE: starting
with an empty circular buffer is no supported.
"""
function SingleLL(
	data :: Vector{T}, ::Type{N} = Int;
	copy_data = true, sparsity_factor :: Int = 1,
	circular = false
) where {T, N}
	if sparsity_factor < 1
		throw(ArgumentError("sparsity_factor should be one or more"))
	end
	if !copy_data && sparsity_factor > 1
		throw(ArgumentError(
			"You cannot disable copy_data and have sparsity_factor greater than one" *
			", use the default constructor for this kind of fiddling."
		))
	end
	if circular && isempty(data)
		throw(ArgumentError(
			"You cannot start with an empty circular buffer, the circularity is " *
			"engraved into the elements, not the list itself."
		))
	end
	sparsity_factor = convert(N, sparsity_factor)

	isempty(data) && return SingleLL{T, N}(copy_data ? copy(data) : data, N[])

	if isone(sparsity_factor)
		data = copy_data ? copy(data) : data
		next = collect(convert(N, 2):convert(N, length(data)))
		next[end] = circular ? one(N) : zero(N)
		return SingleLL{T, N}(data, next)
	end

	n = length(data)
	m = n * sparsity_factor
	data_ = Vector{T}(undef, m)
	next = zeros(N, m)
	j :: Int, i :: Int = 1, 1
	while i <= n
		data_[j] = data[i]
		next[j] = j + sparsity_factor
		j = next[j]
		i += 1
	end
	next[j - sparsity_factor] = circular ? one(n) : zero(n)

	return SingleLL{T, N}(data_, next)
end

import Base.iterate
function Base.iterate(l :: SingleLL{T, N}) where {T, N}
	isempty(l.next) && return nothing
	i = 1
	while iszero(l.next[i]); i += 1; end
	return (l.data[i], l.next[i])
end

function Base.iterate(l :: SingleLL{T, N}, i) where {T, N}
	iszero(i) && return nothing
	return (l.data[i], l.next[i])
end

end # module

```

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 5:46pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/10 "2022-06-25T17:46:25Z")

</div>

Thanks for your answer, this works for me too!

---

<div class="post-metadata">

**Author:** ![pitsianis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pitsianis/32/26588_2.png) [@pitsianis](https://discourse.julialang.org/u/pitsianis)\
**Post date:** [June 25, 2022, 10:39pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/11 "2022-06-25T22:39:47Z")

</div>

Is the output of `collect` correct? I was expecting to see a list of `(String, Integer)` pairs.

---

<div class="post-metadata">

**Author:** ![dylanxyz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dylanxyz/32/36646_2.png) [@dylanxyz](https://discourse.julialang.org/u/dylanxyz)\
**Post date:** [June 25, 2022, 11:48pm UTC](https://discourse.julialang.org/t/efficient-recursive-iteration-over-self-referencing-struct/83322/12 "2022-06-25T23:48:47Z")

</div>

Well, the iteration returns the current `Node`, but if you want to return only the `name` and `value`, you do something like:

```julia
julia> Base.iterate(node::Node, state::Node = node) = state.name => state.value, state.child

julia> collect(node)
3-element Vector{Any}:
 "x" => 1
 "y" => 2
 "z" => 3

```

For my specific use case, i realized that having an `Array` where every _next_ `Node` is a child of the _previous_ `Node` is much better than having a linked list, because my situation is much more simpler, since every `Node` can only have one and only one child or no child.