59 lines
1.3 KiB
Text
59 lines
1.3 KiB
Text
abstract type AbstractNode{T} end
|
|
|
|
struct EmptyNode{T} <: AbstractNode{T} end
|
|
mutable struct Node{T} <: AbstractNode{T}
|
|
data::T
|
|
next::AbstractNode{T}
|
|
end
|
|
Node{T}(x) where T = Node{T}(x::T, EmptyNode{T}())
|
|
|
|
mutable struct LinkedList{T}
|
|
head::AbstractNode{T}
|
|
end
|
|
LinkedList{T}() where T = LinkedList{T}(EmptyNode{T}())
|
|
LinkedList() = LinkedList{Any}()
|
|
|
|
Base.isempty(ll::LinkedList) = ll.head isa EmptyNode
|
|
function lastnode(ll::LinkedList)
|
|
if isempty(ll) throw(BoundsError()) end
|
|
nd = ll.head
|
|
while !(nd.next isa EmptyNode)
|
|
nd = nd.next
|
|
end
|
|
return nd
|
|
end
|
|
|
|
function Base.push!(ll::LinkedList{T}, x::T) where T
|
|
nd = Node{T}(x)
|
|
if isempty(ll)
|
|
ll.head = nd
|
|
else
|
|
tail = lastnode(ll)
|
|
tail.next = nd
|
|
end
|
|
return ll
|
|
end
|
|
function Base.pop!(ll::LinkedList{T}) where T
|
|
if isempty(ll)
|
|
throw(ArgumentError("list must be non-empty"))
|
|
elseif ll.head.next isa EmptyNode
|
|
nd = ll.head
|
|
ll.head = EmptyNode{T}()
|
|
else
|
|
nx = ll.head
|
|
while !isa(nx.next.next, EmptyNode)
|
|
nx = nx.next
|
|
end
|
|
nd = nx.next
|
|
nx.next = EmptyNode{T}()
|
|
end
|
|
return nd.data
|
|
end
|
|
|
|
lst = LinkedList{Int}()
|
|
push!(lst, 1)
|
|
push!(lst, 2)
|
|
push!(lst, 3)
|
|
pop!(lst) # 3
|
|
pop!(lst) # 2
|
|
pop!(lst) # 1
|