One of the simplest data structures is the linked list.

It consists of a collection of individual nodes, each containing a value of type, T, and a pointer to the next node. The last node's pointer is a null pointer.

In C, we would define each Node in the following way.

struct Node {
int data;
struct Node *next;
}

We'll roll our own in Julia for the sake of outlining the fundamentals. Initially, we'll define EmptyNode to represent a pointer to an empty node. Also, in order to leverage the isnothing method, we import Base.isnothing and implement a method where the argument is anything with a type of EmptyNode.

struct EmptyNode end

import Base.isnothing
Base.isnothing(::EmptyNode) = true

Next we implement the Node struct, using generic type of T to allow more flexibility. Each struct, contains a val field of type Tand a next field of type Union{EmptyNode, Node{T}}. We'll also define an inner constructor so we can pass in a value and it will create a new Node with the value and pointing to an EmptyNode.

mutable struct Node{T}
val::T
next::Union{EmptyNode, Node{T}}

Node(v::T) where {T} = new{T}(v, EmptyNode())
end

We'll also define another struct called LinkedList which will act as a wrapper for the collection of nodes. We'll also define two outer contructors, one which accepts a single value of type T and another which accepts a node of type Node{T}.

struct LinkedList{T}
root::Node{T}
end

end

end

Now we want to define some operations so we can, you know, actually do some stuff with these linked lists.

We'll define addnode! which will iterate over the nodes until we find an empty one at which point we will replace the EmptyNode object with a Node object containing a value we are adding.

function addnode!(lst::LinkedList, v::T) where {T}
node = lst.root
while !isnothing(node.next)
node = node.next
end
node.next = Node(v);
end

Next, we will often want to know how many elements are in a list, so we'll define length which follows a similar approach as addnode! but we initially define a count and then with each iteration we increment the count. Once we reach an EmptyNode, then we'll return the count.

function length(lst::LinkedList)
node = lst.root
ncount = 1
while !isnothing(node.next)
node = node.next
ncount += 1
end
return ncount
end

Another thing we'll often want to know is if a particular value is in the collection or not, so we'll define in. We'll iterate over each node and return true if we find a value match. If we reach the end, then we return false.

function in(val::T, lst::LinkedList) where {T}
node = lst.root
node.val == val && return true
while !isnothing(node.next)
if node.next.val == val
return true
end
node = node.next
end
return false
end

The linked list is one of the most fundamental structures in functional programming and they are often manipulated using head and tail functions, so we'll define both of these. head simply returns the first value and tail returns a LinkedList object where the second Node becomes the root.

function head(lst::LinkedList)
return lst.root.val
end

end

When we're working with numeric values, we may want to quickly take the sum or product of all nodes, so we'll also define sum and prod functions.

function sum(lst::LinkedList{T}) where {T <: Real}
node = lst.root
result = node.val
while !isnothing(node.next)
result += node.next.val
node = node.next
end
return result
end

function prod(lst::LinkedList{T}) where {T <: Real}
node = lst.root
result = node.val
while !isnothing(node.next)
result *= node.next.val
node = node.next
end
return result
end
@testset "LinkedList Operations" begin
@test lst.root.val == 4

@test lst.root.next.val == 6

@test length(lst) == 4

@test (4 in lst) == true
@test (6 in lst) == true

> LinkedList Operations |   10     10