# Chained Lists in Julia¶

Using mutable structs in this version.

## Definitions¶

In [15]:
abstract type ChainedList{T} end

In [16]:
struct EmptyList{T} <: ChainedList{T}
end # "singleton" : no data at all

In [17]:
mutable struct NonEmptyList{T} <: ChainedList{T}
first::T
rest::ChainedList{T}
end


## Easy construction¶

We define --> so that a --> L adds a (of type T) in the front of L, and a --> b creates a list with two elements. So a --> b --> c creates a list with three elements, and so on.

In [18]:
function -->(a::T, L::ChainedList{T}) where {T}
return NonEmptyList{T}(a, L)
end

Out[18]:
--> (generic function with 2 methods)
In [19]:
function -->(a::T, b::T) where {T}
empty= EmptyList{T}()
return NonEmptyList{T}(a, NonEmptyList(b, empty))
end

Out[19]:
--> (generic function with 2 methods)

## Pretty printing¶

In [20]:
function inner_string(L::EmptyList)
return ""
end

Out[20]:
inner_string (generic function with 2 methods)
In [21]:
function inner_string(L::NonEmptyList{T}) where {T}
if L.rest == EmptyList{T}()
return string(L.first)
else
return string(L.first) * " --> " * inner_string(L.rest)
end
end

Out[21]:
inner_string (generic function with 2 methods)
In [22]:
function Base.string(L::ChainedList)
return "(" * inner_string(L) * ")"
end

function Base.print(L::ChainedList)
print(string(L))
end

In [23]:
# the following does not work :
function Base.show(io,mime::MIME"text/plain",L::ChainedList{T}) where {T}
println(io, string(L))
end


## Efficient concatenation¶

Without any copying!

In [24]:
function extend!(L1::NonEmptyList{T}, L2::ChainedList{T}) where {T}
if L1.rest == EmptyList{T}()
L1.rest= L2
else
extend!(L1.rest, L2)
end
end

Out[24]:
extend! (generic function with 1 method)

## Examples¶

In [25]:
L= 5 --> 4 --> 3 --> 2 --> 1;
print(L)

(5 --> 4 --> 3 --> 2 --> 1)
In [26]:
L2= 5 --> 4 --> 3 --> 2 --> 1;
print(L2)

(5 --> 4 --> 3 --> 2 --> 1)
In [27]:
L == L2

Out[27]:
false
In [28]:
extend!(L, L2) # no output since the new Base.show does not work

Out[28]:
In [30]:
print(L)

(5 --> 4 --> 3 --> 2 --> 1 --> 5 --> 4 --> 3 --> 2 --> 1)