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

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

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.

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

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

tail::Union{Nothing,Node{T}}
n::Int
end

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

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

node === null ? null : (node.el, node.next)
end

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> push!(ll, 1)
1

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

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

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

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?

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.

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