This is an implementation of a floyd cycle detection algorithm on a linked list. My goal is just to learn from the exercise.
Is my mutable struct and constructor with two helper functions an acceptable way to approach this problem in Julia. In python I’d create a class with methods to access the member data. I’m not sure what I did is inline with Julia best practices.
Is my use of pointer_from_objref safe? I don’t know much about garbage collection and how Juilia uses memory.
Any other critiques are welcome and encouraged!
using DataStructures
# constructs a linked list of integers of a set length
# and randomly chooses a place in the list (the last node
# will be assigned this place later creating a loop in the list)
mutable struct LoopableList
base_list::Cons{Int64}
list_length::Int64
loop_target::Cons{Int64}
last_node::Union{Cons{Int64},Nil{Int64}}
function LoopableList(list_len::Int64)
# create the list
base_list = nil(Int64)
# add nodes to the list starting at the last number
# and counting down to 1
for i in list_len:-1:1
base_list = cons(i,base_list)
end
# construct our length value
list_length = list_len
# random number between 1st and 2nd to last node
# this index will be the location we create the
# loop at
rand_index = Base.rand(1: (list_len-1) )
# loop through the entire list
list = base_list
loop_target = nothing
for i in 1:(list_len-1)
if(i==rand_index)
# save the node that we will want to loop to
loop_target = list
end
item, list = iterate(list)
end
# save the last node so we can point it to the loop_target later
last_node = list
new(base_list,list_length,loop_target,last_node)
end
end
# turn a list constructed from LoopableList
# into a list with a loop in it
function loop_list(ll::LoopableList)
ll.last_node.tail = ll.loop_target
end
# take the loop out of the list so the program
# doesn't hang when it completes
function unloop_list(ll::LoopableList)
ll.last_node.tail = nil(Int64)
end
# create a list 64 digits in length
sample_loop_list = LoopableList(64)
# detect if there is a cycle in the linked list
# using the floyd cycle detection algorithm
function floyd_cycle_detection(list::Cons{Int64})
if(list == nil(Int64))
return false
end
slow_pointer = list
fast_pointer = list
# loop until the end of the list
# or a cycle is confirmed
while(true)
if(fast_pointer.tail == nil(Int64) || fast_pointer.tail.tail == nil(Int64))
return false
end
fast_pointer = fast_pointer.tail.tail
slow_pointer = slow_pointer.tail
# if the fast pointer has been able to
# come back around and equal the slow pointer
# there must be a loop in the list
# edited with goerch's suggestion (and fixed a typo)
if(fast_pointer===slow_pointer)
return true
end
end
end
# create a loop in the list
loop_list(sample_loop_list)
# run the loop detection function
println(floyd_cycle_detection(sample_loop_list.base_list))
# unloop the list so the program doesn't hang when ending
unloop_list(sample_loop_list)
print("done!")
Thank you, and if this post isn’t inline with community preferences I’m open to that feedback as well.
