Repository: JuliaCollections/DataStructures.jl
Pull request #450 (2018-09-23 21:04:41)

Add MutableLinkedList
I put this together in response to issue [#443](https://github.com/JuliaCollections/DataStructures.jl/issues/443). This is my first real contribution julia, so feel free to share any advice and/or feedback about how I could improve this implementation.


Patch:
diff --git a/README.md b/README.md
index 4930b3a..70c7707 100644
--- a/README.md
+++ b/README.md
@@ -24,7 +24,7 @@ This package implements a variety of data structures, including
 -   Ordered Dicts and Sets
 -   Dictionaries with Defaults
 -   Trie
--   Linked List
+-   Linked List and Mutable Linked List
 -   Sorted Dict, Sorted Multi-Dict and Sorted Set
 -   DataStructures.IntSet
 -   Priority Queue
diff --git a/docs/src/index.md b/docs/src/index.md
index f24f7c7..1cb4cbc 100644
--- a/docs/src/index.md
+++ b/docs/src/index.md
@@ -15,7 +15,7 @@ This package implements a variety of data structures, including
 -   Ordered Dicts and Sets
 -   Dictionaries with Defaults
 -   Trie
--   Linked List
+-   Linked List and Mutable Linked List
 -   Sorted Dict, Sorted Multi-Dict and Sorted Set
 -   DataStructures.IntSet
 
@@ -36,6 +36,7 @@ Pages = [
     "default_dict.md",
     "trie.md",
     "linked_list.md",
+    "mutable_linked_list.md"
     "intset.md",
     "sorted_containers.md",
 ]
diff --git a/docs/src/mutable_linked_list.md b/docs/src/mutable_linked_list.md
new file mode 100644
index 0000000..5c5596a
--- /dev/null
+++ b/docs/src/mutable_linked_list.md
@@ -0,0 +1,36 @@
+# Mutable Linked List
+
+The `MutableLinkedList` type implements a doubly linked list with mutable nodes.
+This data structure supports constant-time insertion/removal of elements
+at both ends of the list.
+
+Usage:
+
+```julia
+l = MutableLinkedList{T}()        # initialize an empty list of type T
+l = MutableLinkedList{T}(elts...) # initialize a list with elements of type T
+isempty(l)                        # test whether list is empty
+length(l)                         # get the number of elements in list
+collect(l)                        # return a vector consisting of list elements
+eltype(l)                         # return type of list
+first(l)                          # return value of first element of list
+last(l)                           # return value of last element of list
+l1 == l2                          # test lists for equality
+map(f, l)                         # return list with f applied to elements
+filter(f, l)                      # return list of elements where f(el) == true
+reverse(l)                        # return reversed list
+copy(l)                           # return a copy of list
+getindex(l, idx)                  # get value at index
+setindex!(l, data, idx)           # set value at index to data
+append!(l1, l2)                   # attach l2 at the end of l1
+append!(l, elts...)               # attach elements at end of list
+delete!(l, idx)                   # delete element at index
+delete!(l, range)                 # delete elements within range [a,b]
+push!(l, data)                    # add element to end of list
+pushfirst!(l, data)               # add element to beginning of list
+pop!(l)                           # remove element from end of list
+popfirst!(l)                      # remove element from beginning of list
+```
+
+`MutableLinkedList` implements the Iterator interface, iterating over the list
+from first to last.
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index c31d5aa..8117cc1 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -1,20 +1,17 @@
 module DataStructures
 
-    import Base: <, <=, ==, length, isempty, iterate, delete!,
+    import Base: <, <=, ==, length, isempty, iterate,
                  show, dump, empty!, getindex, setindex!, get, get!,
-                 in, haskey, keys, merge, copy, cat,
+                 in, haskey, keys, merge, copy, cat, collect,
                  push!, pop!, pushfirst!, popfirst!, insert!, lastindex,
-                 union!, delete!, similar, sizehint!, empty,
-                 isequal, hash,
-                 map, reverse,
+                 union!, delete!, similar, sizehint!, empty, append!,
+                 isequal, hash, map, filter, reverse,
                  first, last, eltype, getkey, values, sum,
                  merge, merge!, lt, Ordering, ForwardOrdering, Forward,
                  ReverseOrdering, Reverse, Lt,
-                 isless,
-                 union, intersect, symdiff, setdiff, issubset,
+                 isless, union, intersect, symdiff, setdiff, issubset,
                  searchsortedfirst, searchsortedlast, in,
                  eachindex, keytype, valtype, minimum, maximum
-    import Base: iterate
 
     using OrderedCollections
     import OrderedCollections: filter, filter!, isordered
@@ -44,6 +41,7 @@ module DataStructures
 
     export LinkedList, Nil, Cons, nil, cons, head, tail, list, filter, cat,
            reverse
+    export MutableLinkedList
     export SortedDict, SortedMultiDict, SortedSet
     export SDToken, SDSemiToken, SMDToken, SMDSemiToken
     export SetToken, SetSemiToken
@@ -76,6 +74,7 @@ module DataStructures
     include("int_set.jl")
 
     include("list.jl")
+    include("mutable_list.jl")
     include("balanced_tree.jl")
     include("tokens.jl")
 
diff --git a/src/mutable_list.jl b/src/mutable_list.jl
new file mode 100644
index 0000000..bdc44e7
--- /dev/null
+++ b/src/mutable_list.jl
@@ -0,0 +1,238 @@
+mutable struct ListNode{T}
+    data::T
+    prev::ListNode{T}
+    next::ListNode{T}
+    function ListNode{T}() where T
+        node = new{T}()
+        node.prev = node
+        node.next = node
+        return node
+    end
+    function ListNode{T}(data) where T
+        node = new{T}(data)
+        return node
+    end
+end
+
+mutable struct MutableLinkedList{T}
+    len::Int
+    front::ListNode{T}
+    back::ListNode{T}
+    function MutableLinkedList{T}() where T
+        l = new{T}()
+        l.len = 0
+        l.front = ListNode{T}()
+        l.back = ListNode{T}()
+        l.front.next = l.back
+        l.back.prev = l.front
+        return l
+    end
+end
+
+MutableLinkedList() = MutableLinkedList{Any}()
+
+function MutableLinkedList{T}(elts...) where T
+    l = MutableLinkedList{T}()
+    for elt in elts
+        push!(l, elt)
+    end
+    return l
+end
+
+iterate(l::MutableLinkedList) = begin
+    l.len == 0 ? nothing : (l.front.next.data, l.front.next.next)
+end
+iterate(l::MutableLinkedList, n::ListNode) = begin
+    n.next == n ? nothing : (n.data, n.next)
+end
+
+isempty(l::MutableLinkedList) = l.len == 0
+length(l::MutableLinkedList) = l.len
+collect(l::MutableLinkedList{T}) where T = T[x for x in l]
+eltype(l::MutableLinkedList{T}) where T = T
+function first(l::MutableLinkedList)
+    isempty(l) && throw(ArgumentError("List is empty"))
+    return l.front.next.data
+end
+function last(l::MutableLinkedList)
+    isempty(l) && throw(ArgumentError("List is empty"))
+    return l.back.prev.data
+end
+
+==(l1::MutableLinkedList{T}, l2::MutableLinkedList{S}) where {T,S} = false
+
+function ==(l1::MutableLinkedList{T}, l2::MutableLinkedList{T}) where T
+    length(l1) == length(l2) || return false
+    for (i, j) in zip(l1, l2)
+        i == j || return false
+    end
+    return true
+end
+
+function map(f::Base.Callable, l::MutableLinkedList{T}) where T
+    if isempty(l) && f isa Function
+        S = Core.Compiler.return_type(f, (T,))
+        return MutableLinkedList{S}()
+    elseif isempty(l) && f isa Type
+        return MutableLinkedList{f}()
+    else
+        S = typeof(f(first(l)))
+        l2 = MutableLinkedList{S}()
+        for h in l
+            el = f(h)
+            if el isa S
+                push!(l2, el)
+            else
+                R = typejoin(S, typeof(el))
+                l2 = MutableLinkedList{R}(collect(l2)...)
+                push!(l2, el)
+            end
+        end
+        return l2
+    end
+end
+
+function filter(f::Function, l::MutableLinkedList{T}) where T
+    l2 = MutableLinkedList{T}()
+    for h in l
+        if f(h)
+            push!(l2, h)
+        end
+    end
+    return l2
+end
+
+function reverse(l::MutableLinkedList{T}) where T
+    l2 = MutableLinkedList{T}()
+    for h in l
+        pushfirst!(l2, h)
+    end
+    return l2
+end
+
+function copy(l::MutableLinkedList{T}) where T
+    l2 = MutableLinkedList{T}()
+    for h in l
+        push!(l2, h)
+    end
+    return l2
+end
+
+function getindex(l::MutableLinkedList, idx::Int)
+    @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
+    node = l.front
+    for i = 1:idx
+        node = node.next
+    end
+    return node.data
+end
+
+function setindex!(l::MutableLinkedList{T}, data, idx::Int) where T
+    @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
+    node = l.front
+    for i = 1:idx
+        node = node.next
+    end
+    node.data = convert(T, data)
+    return l
+end
+
+function append!(l1::MutableLinkedList{T}, l2::MutableLinkedList{T}) where T
+    l1.back.prev.next = l2.front.next
+    l2.front.next.prev = l1.back.prev
+    l1.len += length(l2)
+    return l1
+end
+
+function append!(l::MutableLinkedList, elts...)
+    for elt in elts
+        push!(l, elt)
+    end
+    l.len += length(elts)
+    return l
+end
+
+function delete!(l::MutableLinkedList, idx::Int)
+    @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
+    node = l.front
+    for i = 1:idx
+        node = node.next
+    end
+    prev = node.prev
+    next = node.next
+    prev.next = next
+    next.prev = prev
+    l.len -= 1
+    return l
+end
+
+function delete!(l::MutableLinkedList, r::UnitRange)
+    @boundscheck 0 < first(r) < last(r) <= l.len || throw(BoundsError(l, r))
+    node = l.front
+    for i = 1:first(r)
+        node = node.next
+    end
+    prev = node.prev
+    len = length(r)
+    for j in 1:len
+        node = node.next
+    end
+    next = node
+    prev.next = next
+    next.prev = prev
+    l.len -= len
+    return l
+end
+
+function push!(l::MutableLinkedList{T}, data) where T
+    last = l.back.prev
+    node = ListNode{T}(data)
+    node.next = l.back
+    node.prev = last
+    l.back.prev = node
+    last.next = node
+    l.len += 1
+    return l
+end
+
+function pushfirst!(l::MutableLinkedList{T}, data) where T
+    first = l.front.next
+    node = ListNode{T}(data)
+    node.prev = l.front
+    node.next = first
+    l.front.next = node
+    first.prev = node
+    l.len += 1
+    return l
+end
+
+function pop!(l::MutableLinkedList)
+    isempty(l) && throw(ArgumentError("List must be non-empty"))
+    last = l.back.prev.prev
+    data = l.back.prev.data
+    last.next = l.back
+    l.back.prev = last
+    l.len -= 1
+    return data
+end
+
+function popfirst!(l::MutableLinkedList)
+    isempty(l) && throw(ArgumentError("List must be non-empty"))
+    first = l.front.next.next
+    data = l.front.next.data
+    first.prev = l.front
+    l.front.next = first
+    l.len -= 1
+    return data
+end
+
+function show(io::IO, node::ListNode)
+    x = node.data
+    print(io, "$(typeof(node))($x)")
+end
+
+function show(io::IO, l::MutableLinkedList)
+    print(io, typeof(l), '(')
+    join(io, l, ", ")
+    print(io, ')')
+end


Test patch:
diff --git a/test/runtests.jl b/test/runtests.jl
index 229f3c3..a9ebbf9 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -22,6 +22,7 @@ tests = ["int_set",
          "default_dict",
          "trie",
          "list",
+         "mutable_list",
          "multi_dict",
          "circular_buffer",
          "sorting",
diff --git a/test/test_mutable_list.jl b/test/test_mutable_list.jl
new file mode 100644
index 0000000..7e4137a
--- /dev/null
+++ b/test/test_mutable_list.jl
@@ -0,0 +1,160 @@
+@testset "MutableLinkedList" begin
+
+    @testset "empty list" begin
+        l1 = MutableLinkedList{Int}()
+        @test isempty(l1)
+        @test length(l1) == 0
+        @test collect(l1) == Int[]
+        @test eltype(l1) == Int
+        @test_throws ArgumentError pop!(l1)
+        @test_throws ArgumentError popfirst!(l1)
+    end
+
+    @testset "core functionality" begin
+        n = 10
+
+        @testset "push back / pop back" begin
+            l = MutableLinkedList{Int}()
+
+            @testset "push back" begin
+                for i = 1:n
+                    push!(l, i)
+                    @test last(l) == i
+                    @test length(l) == i
+                    @test isempty(l) == false
+                    for (j, k) in enumerate(l)
+                        @test j == k
+                    end
+                    cl = collect(l)
+                    @test isa(cl, Vector{Int})
+                    @test cl == collect(1:i)
+                end
+            end
+
+            @testset "pop back" begin
+                for i = 1:n
+                    x = pop!(l)
+                    @test length(l) == n - i
+                    @test isempty(l) == (i == n)
+                    @test x == n - i + 1
+                    cl = collect(l)
+                    @test cl == collect(1:n-i)
+                end
+            end
+        end
+
+        @testset "push front / pop front" begin
+            l = MutableLinkedList{Int}()
+
+            @testset "push front" begin
+                for i = 1:n
+                    pushfirst!(l, i)
+                    @test first(l) == i
+                    @test length(l) == i
+                    @test isempty(l) == false
+                    cl = collect(l)
+                    @test isa(cl, Vector{Int})
+                    @test cl == collect(i:-1:1)
+                end
+            end
+
+            @testset "pop front" begin
+                for i = 1:n
+                    x = popfirst!(l)
+                    @test length(l) == n - i
+                    @test isempty(l) == (i == n)
+                    @test x == n - i + 1
+                    cl = collect(l)
+                    @test cl == collect(n-i:-1:1)
+                end
+            end
+
+        end
+
+        @testset "append / delete / copy / reverse" begin
+            for i = 1:n
+                l = MutableLinkedList{Int}(1:n...)
+
+                @testset "append" begin
+                    l2 = MutableLinkedList{Int}(n+1:2n...)
+                    append!(l, l2)
+                    @test l == MutableLinkedList{Int}(1:2n...)
+                end
+
+                @testset "delete" begin
+                    delete!(l, n+1:2n)
+                    @test l == MutableLinkedList{Int}(1:n...)
+                    for i = n:-1:1
+                        delete!(l, i)
+                    end
+                    @test l == MutableLinkedList{Int}()
+                    l = MutableLinkedList{Int}(1:n...)
+                    @test_throws BoundsError delete!(l, n-1:2n)
+                    @test_throws BoundsError delete!(l, 2n)
+                end
+
+                @testset "copy" begin
+                    l2 = copy(l)
+                    @test l == l2
+                end
+
+                @testset "reverse" begin
+                    l2 = MutableLinkedList{Int}(n:-1:1...)
+                    @test l == reverse(l2)
+                end
+            end
+        end
+
+        @testset "map / filter" begin
+            for i = 1:n
+                @testset "map" begin
+                    l = MutableLinkedList{Int}(1:n...)
+                    @test map(x -> 2x, l) == MutableLinkedList{Int}(2:2:2n...)
+                end
+
+                @testset "filter" begin
+                    l = MutableLinkedList{Int}(1:n...)
+                    @test filter(x -> x % 2 == 0, l) == MutableLinkedList{Int}(2:2:n...)
+                end
+            end
+        end
+    end
+
+    @testset "random operations" begin
+        l = MutableLinkedList{Int}()
+        r = Int[]
+        m = 100
+
+        for k = 1 : m
+            la = rand(1:20)
+            x = rand(1:1000, la)
+
+            for i = 1 : la
+                if rand(Bool)
+                    push!(r, x[i])
+                    push!(l, x[i])
+                else
+                    pushfirst!(r, x[i])
+                    pushfirst!(l, x[i])
+                end
+            end
+
+            @test length(l) == length(r)
+            @test collect(l) == r
+
+            lr = rand(1:length(r))
+            for i = 1 : lr
+                if rand(Bool)
+                    pop!(r)
+                    pop!(l)
+                else
+                    popfirst!(r)
+                    popfirst!(l)
+                end
+            end
+
+            @test length(l) == length(r)
+            @test collect(l) == r
+        end
+    end
+end