Requesting code review for a mutable struct and use of pointers. (53 lines of code)

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.

You could use egal instead:

if(fast_pointer===slow_pointer)
    return true
end
1 Like

Thanks!

I would mark solution on your reply if you feel the rest of the code is decent.

Thanks for all your help, I’ve learned a lot on this exercise and have found, I think a better way to learn Julia than to mock up these problems. That way I won’t have to request outside help! :slight_smile: