linked-list - Julia 中的双链表

Question

我是 Julia 语言的新手，我想通过实现一个双链表来提高我的理解。
不幸的是，似乎没有用于此目的的良好现有库。

唯一好的一个是单链表( here )。
有一种双链表的实现( here )。但这是 2 岁，我不确定它是否已经过时。并且它不允许真正的空列表。它只是具有默认值的单个元素。

目前，我将能够实现诸如 push!、pop! 之类的常见东西，这不是问题。
但是我正在努力实现一个可能为空的双链表。
我当前的方法使用 Nullable 作为引用和值的可选值。

type ListNode{T}
    prev::Nullable{ListNode{T}}
    next::Nullable{ListNode{T}}
    value::Nullable{T}
    ListNode(v) = (x=new(); x.prev=Nullable{x}; x.next=Nullable{x}; x.value=Nullable(v); x)
    ListNode(p, n, v) = new(p, n, v)
end

type List{T}
    node::Nullable(ListNode{T})
    List() = (start=new(Nullable(ListNode{T}())); node=start; start)
    List(v) = (start=new(Nullable(ListNode{T}(v))); node=start; start)
end

但这似乎非常丑陋且不方便使用。
我的第二种方法是引入一个 bool 变量(在 List{T} 中)，用于存储列表是否为空。检查这个 bool 值可以让我简单地处理推送!和流行!到空列表。

我试图用谷歌搜索一个很好的解决方案，但我没有找到。
谁能给我一个双链表的“ Julia 风格”解决方案？

谢谢，
菲利克斯

Answer 1

现在有一个包含各种数据结构的库，DataStructures.jl关于这个问题的一些初步说明。在撰写本文时，类型已破旧。相反，对于 Julia 1.0 及更高版本，应该使用可变结构。 Nullable 也被废弃了，可以改用空的联合和有问题的类型。

存在一个名为 DataStructures.jl 的包，可以提供您所需要的。
您可以在此处找到包含所需功能的 DoubleLinked 列表:
mutable_list

上面链接中的代码片段，在 Julia >= v 1.1 中定义了一个 DoubleLinked 列表:

mutable struct ListNode{T}
    data::T
    prev::ListNode{T}
    next::ListNode{T}
    function ListNode{T}() where T
        node = new{T}()
        node.next = node
        node.prev = node
        return node
    end
    function ListNode{T}(data) where T
        node = new{T}(data)
        return node
    end
end

mutable struct MutableLinkedList{T}
    len::Int
    node::ListNode{T}
    function MutableLinkedList{T}() where T
        l = new{T}()
        l.len = 0
        l.node = ListNode{T}()
        l.node.next = l.node
        l.node.prev = l.node
        return l
    end
end