How to implement a SingleLinkedList in Julia

user_14391680 0
Viewed 226

I'm learning about TAD but, I don't understand so much the syntax, that's why its too difficult to me to create a single list, but i understand how it works such as TAD, please, someone can tell how to implement this TAD(Linked List), with basic instructions and describing them

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)

I'm trying this, but i don't know why it doesn't works, I'm getting confused because i was reading many posts about the instructions that I used, but I don't understand Nodo{T}() where T =(x=new();x;x.next=x) this instruction at all, I need help.

julia
2 Answers

There is a mix of concepts in your code therefore in order to help you I will use one of them to show you how you can implement your linked list. Here is the code:

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

and this is how you can use it:

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))))

Some comments:

  • I use Union to show that an object can either hold no reference (Nothing) or some reference to the next object (Nodo{T})
  • In LList{T}() where T = new{T}(nothing) we define only one inner constructor, as it takes no arguments, I use new{T} that is available only in inner constructors to create an instance of LList{T} object with value set to nothing (as it has no nodes yet)
  • I use Base.push! as this is a standard name for a function to add an item to a collection; Base. is needed to add a method to a standard function; also therefore later I write lista::LList to make sure that this method is specific to your LList{T} type
  • as you can see in the code there is no need for "dummy" node (as was present in your code), as you simply keep track of an end of the list by using nothing value

I hope that starting from this point you will be able to add other methods to your LList object.

user_12695670

A slightly different version of Bogumil answer is to use undefined fields.

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

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

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

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

    return lista
end

and it works like this

julia> lista=LList{Int}()
LList{Int64}(#undef)

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

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

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

This approach doesn't introduce union fields but makes the whole code more fragile since you need to switch between nodo.next and isdefined(nodo, :next) notations.

user_14941350
Related