The Original LinkedList

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

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