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 `T`

and 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
function LinkedList(v::T) where {T}
LinkedList{T}(Node(v))
end
function LinkedList(node::Node{T}) where {T}
LinkedList{T}(node)
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
function tail(lst::LinkedList)
return LinkedList(lst.root.next)
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
lst = LinkedList(4)
@test lst isa LinkedList
@test lst.root.val == 4
addnode!(lst, 6)
@test lst.root.next.val == 6
addnode!(lst, -4)
addnode!(lst, 23)
@test length(lst) == 4
@test (4 in lst) == true
@test (6 in lst) == true
@test head(lst) == 4
@test head(tail(lst)) == 6
@test sum(lst) == (4 + 6 + -4 + 23)
lst2 = LinkedList(1)
addnode!(lst2, 2)
addnode!(lst2, 3)
addnode!(lst2, 10)
@test prod(lst2) == 60
end
> Test Summary: | Pass Total
> LinkedList Operations | 10 10
```

© Daniel Marvin. Last modified: July 03, 2021.