How do I code a simple linked list using DataStructures.jl

New to Julia
1

Looking to code a linked list and add a cycle to the list so that I can implement the Floyd cycle detection algorithm.

I found LinkedList from DataStructures.jl

However I can’t figure out how to:

  1. create a list
  2. iterate through the list by calling next on a node
  3. inserting a node in the list

I would love being pointed to any documentation or code of the LinkedList being used.

1 Like
2

The documentation is in your link. Create a linked list: l = nil(). Add to the list: l = cons(l, item) (don’t know why it’s called that, there’s probably a reason). Iterate the list: for x in l. If you want to iterate it specifically with next you’ll need to define next as iterate - like here

https://docs.julialang.org/en/v1/base/collections/#lib-collections-iteration

3

In case that you like to built it from the ground up, typical implementation of linked list needs two data structures:

  • A data structure, usually called Node, which wraps an actual data and has two pointers to point to previous and next nodes.
  • Another data structure, usually called LinkedList that has pointers to the head and tail of the list

One such example could be:

module MyDataStructures

export LinkedList, Node, push!, pop!, show

const null = nothing

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

mutable struct LinkedList{T}
    head::Union{Nothing,Node{T}}
    tail::Union{Nothing,Node{T}}
    n::Int
end

LinkedList{T}() where {T} = LinkedList{T}(null, null, 0)

function Base.push!(ll::LinkedList{T}, el::T) where {T}
    if ll.head === ll.tail === null
        ll.head = ll.tail = Node{T}(el, null, null)
    else
        ll.tail.next = Node{T}(el, null, null)
        ll.tail.next.prev = ll.tail
        ll.tail = ll.tail.next
    end
    ll.n += 1
    ll
end

function Base.pop!(ll::LinkedList{T}) where {T}
    ll.n == 0 && throw(ArgumentError("LinkedList must be non-empty"))
    el = ll.tail.el
    ll.tail = ll.tail.prev
    ll.n -= 1
    ll.n == 0 && (ll.head = null)
    el
end

Base.length(ll::LinkedList{T}) where {T} = ll.n

function Base.iterate(ll::LinkedList{T}, node::Union{Node{T},Nothing}=ll.head) where {T}
    node === null ? null : (node.el, node.next)
end

function Base.show(io::IO, ll::LinkedList)
    for el in ll
        print(el, " ")
    end
end

end

so that:

julia> ll = LinkedList{Int}()


julia> push!(ll, 2)
2 

julia> push!(ll, 3)
2 3 

julia> ll = LinkedList{Any}()


julia> push!(ll, 1)
1 

julia> push!(ll, "abc")
1 abc 

julia> [a for a in ll]
2-element Vector{Any}:
 1
  "abc"
5 Likes
4

If you’re using this for production code that has performance requirements, maybe also consider not using linked list. Pointer chasing is slow

1 Like
5

Thanks. I have some follow up questions. So, how would I code a linked list of 15 numbers 1 through 15? The best I could come up with was:

using DataStructures

l1 = nil()

for i in 15:-1:1
    l1 = cons(i,l1)
end

I know I can iterate through the whole list by:

for x in l1
    println(x)
end
  1. How would I iterate through the first three nodes and then access that value?
  2. How would I iterate through the first three nodes and then insert a new node there?
  3. How do I access the pointers of the individual nodes?

I have more questions but don’t want to overload the thread.

Later in this thread Sijun shows some code on how to write up a linked list from scratch and his code seems to be close to what I was hoping to find in a library.

6

I think the reason you don’t find these in a library is that, as mentioned above, linked lists are more of a programming exercise concept than something anyone would use in serious deployment. That said,

julia> list = l1
julia> item = nothing
julia> for i=1:3
item, list = iterate(list)
end
julia> item
3

julia> list = l1
julia> for i=1:(3-1)
item, list = iterate(list)
end
julia> list.tail = cons(100, list.tail)
julia> l1
list(1, 2, 3, 100, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
  1. For any list list, list.tail is a pointer to the next node.
1 Like
7

So, what then is the Julian way of dealing with a data structure that classically would require a linked list? Just use a Vector?

8

Historically in LISP cons was the way to CONStruct a list by instantiating what is usually called a cons cell. Aka a node in the list.

1 Like