尝试使用Julia实现一个单链表…

昨天一边看着官网docs一边学习Julia的产物,用到了复合类型、参数化类型和迭代器
不知道写法是否合适,总之发上来欢迎指正

module SinglyLinkedList

export Node,HeadNode,DataNode

abstract type Node{T} end

mutable struct DataNode{T}<:Node{T}
    next::Union{DataNode{T},Nothing}
    data::T
end

DataNode{T}(data::T) where T=DataNode{T}(nothing,data)

mutable struct HeadNode{T}<:Node{T}
    next::Union{DataNode{T},Nothing}
    size::Integer

    HeadNode{T}() where T=new{T}(nothing,0)
end

function Base.pushfirst!(head::HeadNode{T},x::T) where T
    nextnode=head.next
    head.next=DataNode{T}(nextnode,x)
    head.size+=1
    return head
end

function Base.push!(head::HeadNode{T},x::T) where T
    cur=head
    while cur.next!=nothing
        cur=cur.next
    end
    cur.next=DataNode{T}(x)
    head.size+=1
    return head
end

function Base.popfirst!(head::HeadNode)
    first=head.next
    if first==nothing
        throw(ArgumentError("list must be non-empty"))
    end
    head.next=head.next.next
    head.size-=1
    return first.data
end

function Base.pop!(head::HeadNode)
    cur=head
    prev=nothing
    while cur.next!=nothing
        prev=cur
        cur=cur.next
    end
    if prev==nothing
        throw(ArgumentError("list must be non-empty"))
    end
    prev.next=nothing
    head.size-=1
    return cur.data
end

function Base.insert!(head::HeadNode{T},pos::Node{T},x::T) where T
    nextnode=pos.next
    pos.next=DataNode{T}(x)
    head.size+=1
    pos.next.next=nextnode
end

function Base.reverse!(head::HeadNode)
    cur=head.next
    if cur==nothing
        return
    end
    while cur.next!=nothing
        nextnode=cur.next.next
        cur.next.next=head.next
        head.next=cur.next
        cur.next=nextnode
    end
    return head
end

Base.length(head::HeadNode)=head.size

Base.eltype(head::HeadNode{T}) where T=T

function Base.iterate(head::HeadNode)
    first=head.next
    if first==nothing
        return nothing
    else
        return (first.data,first)
    end
end

function Base.iterate(head::HeadNode,cur::Node)
    cur=cur.next
    if cur==nothing
        return nothing
    else
        return (cur.data,cur)
    end
end

Base.show(io::IO,head::HeadNode)=Base.show_delim_array(io,head,"[","->","]",false)

end

使用

julia> using SinglyLinkedList

julia> h=HeadNode{Int}()
[]

julia> push!(h,2,3,5)
[2-> 3-> 5]

julia> pushfirst!(h,1)
[1-> 2-> 3-> 5]

julia> let
       next=iterate(h)
       while next!=nothing
           (x,s)=next
           if x==3
               insert!(h,s,4)
           end
           next=iterate(h,s)
       end
       end

julia> h
[1-> 2-> 3-> 4-> 5]

julia> reverse!(h)
[5-> 4-> 3-> 2-> 1]

julia> popfirst!(h)
5

julia> while !isempty(h)
           println(pop!(h))
       end
1
2
3
4

另外REPL里面如果我不用let包起来语句的话会报错next未定义,不太清楚成因

1 个赞

next 是一个 Base 函数,试着改成别的名字。
另外

DataNode(data::T) where T 

就好了, 不需要{T}

2 个赞
module SingleList
export Node,HeadNode,DataNode
abstract type Node{T} end
mutable struct DataNode{T}<:Node{T}
    data::T
    tail::Node{T}
end

mutable struct HeadNode{T}<:Node{T}
    size::Int
    tail::Node{T} #Tail接下来就是DataNode构成的单链表
    last::Node{T} #存放最后一个 DataNode (尾部)
    function HeadNode{T}() where T
	x = new{T}(0)
	x.tail = x		
        x.last = x
   end
end


function isHeadNode(::HeadNode{T}) where T
	true 
end
function isHeadNode(::DataNode{T}) where T
	false 
end


function Base.pushfirst!(head::HeadNode{T},x::T) where T
	if isHeadNode(head.tail)
		newNode = DataNode(x,head)
		head.tail = newNode
		head.last = newNode
	else
		newNode = DataNode(x,head.tail)
		head.tail = newNode
	end
    head.size+=1
    return head
end
#pushfirst还可以写的更短
function Base.push!(head::HeadNode{T},x::T) where T
	newNode = DataNode(x,head)
	head.last.tail = newNode
	head.last = newNode
	head.size+=1
    return head
end
#push的实现很巧妙,没有用条件判断
end

我是这么写的。我觉得不要用太多的nothing(毕竟Julia的类型系统很丰富,不用搞这么多nothing出来,就好像滥用空指针一样)。我的方法和你的略有不同,我写了两个类型DataNode与HeadNode,其抽象类型为Node。HeadNode里存放了长度,以及链表的第一项和最后一项(便于push!),列表最后一项回指列表的HeadNode(循环表),目前我只写了push!和pushfirst!两个函数,iterate函数有点麻烦,因为是循环表,要正确终止循环不太容易(直观的说,当该节点的tail是一个HeadNode的时候就要终止了),另外我不知道iterate的接口是什么,所以我没有写,要不你看看怎么写好了。另外pop还是要遍历列表,除非是双链的。

1 个赞

虽然链表在插入节点上面很有优势,但是经常遍历花费时间可不小。
感觉Array,试了下随机插入删除,速度好像也是刚刚的。

分开处理 data node 跟 control node 我觉得比较合理。我之前也写了一个简单的实现,但是偷懒所以就没有像你一样用类型分开处理。

mutable struct Node{T}
    payload :: Union{T, Nothing}
    next :: Union{Node{T}, Nothing}
end

mutable struct List{T}
    head :: Node{T}
    tail :: Node{T}
    size :: Int
end

function List{T}() where {T}
    tail = Node{T}(nothing, nothing)
    head = Node{T}(nothing, tail)
    List{T}(head, tail, 0)
end

下面是针对 Node 的操作,参数跟返回都是 Node 类型。

function Base.iterate(node :: Node{T}, this :: Union{Node{T}, Nothing} = node) where {T}
    this == nothing ? nothing : (this, this.next)
end

function Base.getindex(node :: Node{T}, index :: Integer) where {T}
    i :: Union{Integer, Nothing} = nothing
    for e in zip(0 : index, node)
        i, node = e 
    end
    i == index ? node : nothing
end

function Base.setindex!(node :: Node{T}, new :: Node{T},  index :: Integer) where {T}
    previous = node[index - 1]
    new.next = node[index].next
    previous.next = new
end

function Base.insert!(node :: Node{T}, index :: Integer, new :: Node{T}) where {T}
    previous = node[index - 1]
    new.next = node[index]
    previous.next = new
end

function Base.deleteat!(node :: Node{T}, index :: Integer) where {T}
    previous = node[index - 1]
    next = node[index + 1]
    previous.next = next
end

接下来就是用 Node 实现一个 List,参数跟返回值都是 T 类型,同时记录长度。

function Base.iterate(list :: List{T}, this :: Node{T} = list.head.next) where {T}
    this == list.tail ? nothing : (this.payload, this.next)
end

function Base.length(list :: List{T}) where {T}
    list.size
end

function checkbound(list :: List{T}, index :: Integer) where {T}
    index >= 1 && index <= length(list)
end

function Base.insert!(list :: List{T}, index :: Integer, value :: T) where {T}
    checkbound(list, index) || index == length(list) + 1 ? (insert!(list.head, index, Node{T}(value, nothing)); list.size = list.size + 1) : throw(BoundsError())
end

function Base.append!(list :: List{T}, value :: T) where {T}
    insert!(list, length(list) + 1, value)
end

function Base.deleteat!(list :: List{T}, index :: Integer) where {T}
    checkbound(list, index) ? (deleteat!(list.head, index); list.size = list.size - 1) : throw(BoundsError())
end

function Base.getindex(list :: List{T}, index :: Integer) where {T}
    checkbound(list, index) ? list.head[index].payload : throw(BoundsError())
end

function Base.setindex!(list :: List{T}, value :: T, index :: Integer) where {T}
    checkbound(list, index) ? list.head[index] = Node{T}(value, nothing) : throw(BoundsError())
end

function Base.firstindex(list :: List{T}) where {T}
    1
end

function Base.lastindex(list :: List{T}) where {T}
    length(list)
end

自己写的module怎么引用,我自己写了一个模块,然后在另外一个文件using那个模块,一直报错没有找到not found

如果你的 module 写在另外一个文件里你可能需要用 include() 载入。

同文件夹下的话你可以先把当前路径加入LOAD_PATH,这只对当前会话有效
或者你把源代码丢到某个常用目录,然后在startup.jl里加入LOAD_PATH,这是永久性的

push!(LOAD_PATH,pwd())

文件名和模块名一致

按照docs的意思,Julia用Nothing和实际类型做Union实现可空类型好像是惯用法

我知道,julia库里代码里也用了很多nothing,毕竟nothing可能有特别的优化之类的吧,用作失败的表示确实可以(特别是表示一些空值,没有成功的值之类的)而且nothing有自己的类型,比较安全。不过你看楼主本来的这个表示里面有很多nothing,要做很多的检查,nothing再有效率,检查做多了也会变得很慢。我觉得这个nothing和python中的None一样,像一种空指针,最好也别滥用了(而且我这里特别说的是他设计的这个数据结构,数据结构是一种类型,应该更好的利用Julia的类型系统)。

试过了,直接Include不行,要把路径加入LOAD_PATH

其实你可以分开这样写:
mutable struct ListElmt{T}
value::T
next::Union{Nothing,ListElmt}
end

mutable struct
size::Int
head::Union{Nothing,ListElmt}
tail::Union{Nothing,ListElmt}
end

顺便说一下在List中不用指定ListElmt为ListElmt{T}
因为ListElmt为ListElmt{T}的父类,操作时不需要考虑泛型类型
另外,最好不要改写Base里的函数内容,记得把module里的东西export出来

另外,最好不要改写Base里的函数内容,记得把module里的东西export出来

哪里改写了…这不是添加方法吗?你可能对Julia有什么误解
另外JL不是OOP语言,这个不是父子类的问题,ListElmt不是某一个具体的DataType,是一个UnionAll。你可以理解为它是所有的ListElmt{T}的Union,所以它是所有ListElmt{T}的supertype,即ListElmt{T} <: ListElmt。
不知道你是不是从Java过来的,由于历史原因JVM并不支持泛型,Java里面的ListElmt是游离于泛型类型系统外的raw type,它opt-out了编译时泛型类型检查(所以不安全),和这个概念不同。Julia并没有类型擦除,所以限定同一个T还是有用的(否则你为什么不用Any)

你这种写法是错误的(或者说不是best practice)有这样几个原因

  1. 你的这个类型声明由于使用了非concrete type作为类型成员的类型标注会影响到type inference,编译器无法在编译时期将你的类型specialize为concrete type应当写为
mutable struct ListElmt{T}
value::T
next::Union{Nothing,ListElmt{T}}
end

mutable struct
size::Int
head::Union{Nothing,ListElmt{T}}
tail::Union{Nothing,ListElmt{T}}
end
  1. 不存在匿名类型这种说法,你的第二个声明完全是错误的。

  2. Julian写法恰好是应该用用户类型重载标准接口,这是Julia能够比很多其它语言在实践里更多的复用代码的原因。Base中有大量现成的generic函数,你只要重载少量的函数就可以获得fallback的支持。

最后,代码请使用markdown code block

如果是这样,那么如何初始化一个空列表呢

https://juliacollections.github.io/DataStructures.jl/latest/linked_list.html