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: create a list iterate through the list by calling next on a node inserting a node in the list I would love being pointed to any documentation or code of the LinkedList being used.

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) For any list list, list.tail is a pointer to the next node.

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

[image] Linked list General Usage 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] If you’re using this for production code that has performance requirements, maybe also consider not using linked list. Pointer chasing is slow

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 How would I iterate through the first three nodes and then access that value? How would I iterate through the first three nodes and then insert a new node there? 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.

[image] 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.

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

New to Julia

jling May 12, 2022, 5:36am 4

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

Topic		Replies	Views
Efficient recursive iteration over self referencing struct Performance	11	1035	June 25, 2022
Requesting code review for a mutable struct and use of pointers. (53 lines of code) New to Julia data_structures , mutable-structure	2	553	May 12, 2022
Using iterator in Julia 0.7 General Usage	2	716	June 8, 2018
Doubly linked list with initial list and mutation General Usage question , data_structures	3	531	October 7, 2022
How to remove an item from a linked list in Julia? General Usage	8	1994	January 5, 2018

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

Related topics