Double linked list in Julia
I'm new to Julia's language and I wanted to improve my understanding by doing a double linked list. Unfortunately there is no good existing library for this purpose.
The only good one is the only linked list ( here ). There is one implementation of a double list ( here ). But it's 2 years old and I'm not sure if it's outdated or not. And it doesn't allow an empty list. This is just one element with a default value.
At this point, I can implement normal things like push !, pop !, which is not a problem. But I am struggling with the implementation of a double linked list that can be empty. My current approach is using Nullable for optional reference and value.
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
But it looks like it's pretty ugly and awkward to work with. My second approach would be to introduce a boolean variable (inside List {T}) that stores if the list is empty or not. Checking this boolean would allow push to be handled simply! and pop! for empty lists.
I tried to find a good solution but I couldn't find one. Can anyone give me a "julia style" solution for a double list?
Thanks, Felix
source to share
In addition to the DataStructures package , Chris Rackauckas' LinkedLists.jl by Chris Rackauckas is a good resource.
The source code is quite readable and you can always ask questions.
source to share
There is currently a library containing various data structures, DataStructures.jl. Some initial notes on this matter. At the time of this writing, the type has been malformed. Instead, a mutable structure should be used, for Julia 1.0 and up. Nullable is also decrepit, and Union of Nothing and the type in question can be used instead.
There is a DataStructures.jl package that provides what you need. You can find a DoubleLinked list containing the functions you need here: mutable_list
The code snippets from the link above defining the DoubleLinked list in Julia> = v 1.1:
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
source to share