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

**URL:** <https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929>\
**Category:** New to Julia\
**Tags:** data\_structures\
**Created:** [May 12, 2022, 3:47am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929 "2022-05-12T03:47:28Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![ao222](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ao222/32/36175_2.png) [@ao222](https://discourse.julialang.org/u/ao222)\
**Post date:** [May 12, 2022, 3:47am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/1 "2022-05-12T03:47:28Z")

</div>

Looking to code a linked list and add a cycle to the list so that I can implement the [Floyd cycle detection algorithm](https://www.geeksforgeeks.org/floyds-cycle-finding-algorithm/).

I found [LinkedList from DataStructures.jl](https://juliacollections.github.io/DataStructures.jl/latest/linked_list/#Linked-List-1)

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.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [May 12, 2022, 4:20am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/2 "2022-05-12T04:20:29Z")

</div>

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](https://docs.julialang.org/en/v1/base/collections/#lib-collections-iteration)

---

<div class="post-metadata">

**Author:** ![Sijun](https://avatars.discourse-cdn.com/v4/letter/s/b2d939/32.png) [@Sijun](https://discourse.julialang.org/u/Sijun)\
**Post date:** [May 12, 2022, 5:03am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/3 "2022-05-12T05:03:13Z")

</div>

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:

```julia
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
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"

```

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [May 12, 2022, 5:36am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/4 "2022-05-12T05:36:08Z")

</div>

> [@Linked list](https://discourse.julialang.org/t/linked-list/6633/3):
>
> I updated Lists.jl awhile ago to make this: (it was a PR to fix, update, and “conciseify” but it wasn’t looked at for months so it became a fork, but it all worked so I just registered it). Don’t assume that. [[Bjarne Stroustrup: Why you should avoid Linked Lists] ](https://www.youtube.com/watch?v=YQs6IC-vgmo)

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

---

<div class="post-metadata">

**Author:** ![ao222](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ao222/32/36175_2.png) [@ao222](https://discourse.julialang.org/u/ao222)\
**Post date:** [May 12, 2022, 5:51am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/5 "2022-05-12T05:51:07Z")

</div>

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:

```julia
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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [May 12, 2022, 8:11am UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/6 "2022-05-12T08:11:56Z")

</div>

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,

1. 

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

```

1. 

```julia
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.

---

<div class="post-metadata">

**Author:** ![davidavdav](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidavdav/32/1065_2.png) [@davidavdav](https://discourse.julialang.org/u/davidavdav)\
**Post date:** [October 23, 2022, 12:56pm UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/7 "2022-10-23T12:56:58Z")

</div>

> [@jling](#):
>
> [Linked list - #3 by ChrisRackauckas](https://discourse.julialang.org/t/linked-list/6633/3)
> 
> If you’re using this for production code that has performance requirements, maybe also consider not using linked list. Pointer chasing is slow

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

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [October 23, 2022, 3:18pm UTC](https://discourse.julialang.org/t/how-do-i-code-a-simple-linked-list-using-datastructures-jl/80929/8 "2022-10-23T15:18:12Z")

</div>

> [@gustaphe](#):
>
> don’t know why it’s called that, there’s probably a reason

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.