Julia Intrusive Doubly Linked List

intrusivelist.jl

mutable struct IntrusiveLinkedList{T}
    # T is required to have fields prev and next in order to
    # be managed by the IntrusiveLinkedList
    head::Union{T, Nothing}
    tail::Union{T, Nothing}
    IntrusiveLinkedList{T}() where {T} = new{T}(nothing, nothing)
end

eltype(::Type{<:IntrusiveLinkedList{T}}) where {T} = @isdefined(T) ? T : Any

iterate(q::IntrusiveLinkedList) = (h = q.head; h === nothing ? nothing : (h, h))
iterate(q::IntrusiveLinkedList{T}, v::T) where {T} = (h = v.next; h === nothing ? nothing : (h, h))

Base.isempty(q::IntrusiveLinkedList) = (q.head === nothing)

function length(q::IntrusiveLinkedList)
    i = 0
    head = q.head
    while head !== nothing
        i += 1
        head = head.next
    end
    return i
end

function list_append!!(q::IntrusiveLinkedList{T}, q2::IntrusiveLinkedList{T}) where T
    q === q2 && error("can't append list to itself")
    head2 = q2.head
    if head2 !== nothing
        tail2 = q2.tail::T
        q2.head = nothing
        q2.tail = nothing
        tail = q.tail
        q.tail = tail2
        if tail === nothing
            q.head = head2
        else
            tail.next = head2
            head2.prev = tail
        end
    end
    return q
end

function push!(q::IntrusiveLinkedList{T}, val::T) where T
    if (val.next !== nothing) || (val.prev !== nothing)
        error("val already in list")
    end
    tail = q.tail
    if tail === nothing
        q.head = q.tail = val
    else
        tail.next = val
        val.prev = tail
        q.tail = val
    end
    return q
end

function pushfirst!(q::IntrusiveLinkedList{T}, val::T) where T
    if (val.next !== nothing) || (val.prev !== nothing)
        error("val already in list")
    end

    head = q.head
    if head === nothing
        q.head = q.tail = val
    else
        val.next = head
        head.prev = val
        q.head = val
    end
    return q
end

# pops the last item in the list
function pop!(q::IntrusiveLinkedList{T}) where {T}
    val = q.tail::T
    val !== nothing || return
    
    q.tail = val.prev
    q.tail.next = nothing
    val.prev = nothing
    val.next = nothing

    return val
end

function popfirst!(q::IntrusiveLinkedList{T}) where {T}
    val = q.head::T
    val !== nothing || return
    q.head = val.next
    val.next = nothing
    val.prev = nothing

    return val
end

function remove!(q::IntrusiveLinkedList{T}, val::T) where {T}
    # cannot remove nothing
    if (val === nothing)
        return
    end


    # value not in list, do nothing
    if (val.next === nothing) && (val.prev === nothing)
        # the head may be the last item in the list
        # and the head and tail point at the same element
        if val === q.head
            q.head = q.tail = nothing
        end
        return
    end

    if val.prev !== nothing
        val.prev.next = val.next
    end

    if val.next !== nothing
        val.next.prev = val.prev
    end

    if val === q.head
        q.head = val.next
    elseif val === q.tail
        q.tail = val.prev
    end

    val.prev = val.next = nothing
end

;

here is a small driver program to create a list and add a few items

`include("intrusivelist.jl")

mutable struct MyStruct
data::Int64
prev::Union{Nothing, MyStruct}
next::Union{Nothing, MyStruct}
MyStruct(data) = new(data, nothing, nothing)
end

myll = IntrusiveLinkedList{MyStruct}()

ms1 = MyStruct(10)
ms2 = MyStruct(19)
ms3 = MyStruct(29)
ms4 = MyStruct(999)
push!(myll, ms1)
push!(myll, ms2)
push!(myll, ms3)
push!(myll, ms4)

remove!(myll, ms3)`