如何在 Julia 中实现 SingleLinkedList

Question

我正在学习 TAD 但是，我不太了解语法，这就是为什么我很难创建单个列表，但我理解它是如何工作的，例如 TAD，请有人能告诉我如何实现这一点TAD（链表），带有基本说明和描述

abstract type AbstractList{T} end
abstract type AbstractNode{T} end

mutable struct Nodo{T} <: AbstractNode{T}
    value ::T
    next ::Nodo{T}
    Nodo{T}() where T =(x=new();x;x.next=x)
    Nodo{T}(v,n) where T =new(v,n)
end

mutable struct LList{T} <: AbstractList{T}
    first ::Nodo{T}
    LList{T}() where T =new(Nodo{T}())
end

Lista=LList;

function Append(lista,value)
    current=Nodo(value,new(Nodo()))
    if Lista.size==0
        lista.head=current
    else
        MyNode=Lista.first;
        while MyNode.next!=nothing
            MyNode=MyNode.next;
        MyNode.next=current;
        end
    end
    Lista.size+=1
end

Append(Lista,2)

我正在尝试这个，但我不知道为什么它不起作用，我很困惑，因为我阅读了很多关于我使用的说明的帖子，但我根本不理解Nodo{T}() where T =(x=new();x;x.next=x)这个说明，我需要帮助。

Answer 1

您的代码中有多种概念，因此为了帮助您，我将使用其中一个概念来向您展示如何实现链表。这是代码：

abstract type AbstractList{T} end
abstract type AbstractNode{T} end

mutable struct Nodo{T} <: AbstractNode{T}
    value::T
    next::Union{Nodo{T}, Nothing}
end

mutable struct LList{T} <: AbstractList{T}
    head::Union{Nodo{T}, Nothing}
    LList{T}() where T = new{T}(nothing)
end

function Base.push!(lista::LList, value)
    new_nodo = Nodo(value, nothing)
    if isnothing(lista.head)
        lista.head = new_nodo
    else    
        current_nodo = lista.head
        while !isnothing(current_nodo.next)
            current_nodo = current_nodo.next
        end
        current_nodo.next = new_nodo
    end
    return lista
end

这就是您可以使用它的方式：

julia> lista=LList{Int}()
LList{Int64}(nothing)

julia> push!(lista, 1)
LList{Int64}(Nodo{Int64}(1, nothing))

julia> push!(lista, 2)
LList{Int64}(Nodo{Int64}(1, Nodo{Int64}(2, nothing)))

julia> push!(lista, 3)
LList{Int64}(Nodo{Int64}(1, Nodo{Int64}(2, Nodo{Int64}(3, nothing))))

一些评论：

• 我Union用来证明一个对象既可以不持有引用 ( Nothing)也可以持有对下一个对象的引用 ( Nodo{T})
• 在LList{T}() where T = new{T}(nothing)我们定义只有一个内部的构造，因为它不带任何参数，我用的new{T}是只在内部构造可用于创建实例LList{T}对象与值设置为nothing（因为它没有节点还）
• 我使用，Base.push!因为这是将项目添加到集合的函数的标准名称；Base.需要向标准函数添加方法；也因此稍后我写信lista::LList以确保此方法特定于您的LList{T}类型
• 正如您在代码中看到的，不需要“虚拟”节点（如您的代码中所示），因为您只需使用nothingvalue跟踪列表的末尾

我希望从这一点开始，您将能够向您的LList对象添加其他方法。