[轮子]单链表 写吐了

综合讨论区
1

你没有看错，我又无聊到写单链表了，这个写完以后，我他娘的再也不写链表了，都写吐了

1. 先上链表定义

# TODO: List struct
mutable struct ListNode{T}
    value::T
    next::Union{Nothing,ListNode{T}}

    ListNode{T}() where T = (x=new();x.next=nothing;x)
    ListNode{T}(value::T,next::Union{Nothing,ListNode{T}}) where T = new(value,next)
end


@enum ListMode begin
    LIST = 0
    QUEUE = 1
    STACK = 2
end

mutable struct List{T}
    head::ListNode{T}
    tail::ListNode{T}
    
    size::Int
    mode::ListMode
end

function List{T}(mode::ListMode=LIST) where T
    head = tail = ListNode{T}()
    size = 0
    List{T}(head,tail,0,mode)
end

# TODO: next of node
function next(node::ListNode{T}) where T
    node.next
end

ListMode ------- 把List,Queue,Stack三个的行为整合在一起

2. 链表基本操作

2.1 push

# TODO: list push --- push_back
function push_next(node_1::ListNode{T},node_new::ListNode{T}) where T
    node_2 = node_1.next
    node_new.next = node_2
    node_1.next = node_new
end

function push_back(list::List{T},node::ListNode{T}) where T
    list.tail = push_next(list.tail,node)
    list.size += 1
    list
end

function push_back(list::List{T},value::T) where T 
    list.tail = push_next(list.tail,ListNode{T}(value,nothing))
    list.size += 1
    list
end

function push_front(list::List{T},node::ListNode{T}) where T
    push_next(list.head,node)
    list.size += 1
    list
end

function push_front(list::List{T},value::T) where T
    push_next(list.head,ListNode{T}(value,nothing))
    list.size += 1
    list
end

整合push

function push(list::List{T},node::ListNode{T}) where T
    if list.mode == LIST || list.mode == QUEUE
        push_back(list,node)
    elseif list.mode == STACK
        push_front(list,node)
    end
end

function push(list::List{T},value::T) where T
    push(list,ListNode{T}(value,nothing))
end

2.2 pop

# TODO: list pop --- pop_back
function pop_next(node_1::ListNode{T}) where T
    node_2 = node_1.next
    if node_2 != nothing
        node_3 = node_2.next
        node_1.next = node_3
    end

    node_1
end

function pop_back(list::List{T}) where T
    current_node = list.head
    while current_node.next != list.tail
        current_node = next(current_node)
    end

    list.size -= 1
    list.tail = pop_next(current_node)
end
# TODO: list pop --- pop_front
function pop_front(list::List{T}) where T
    list.size -= 1
    pop_next(list.head)
end

整合 pop

function pop(list::List{T}) where T
    if list.size != 0
        if list.mode == QUEUE || list.mode == STACK
            pop_front(list)
        elseif list.mode == LIST
            pop_back(list)
        end
    end
end

特殊情况

function pop(list::List{T},node::ListNode{T}) where T
    current_node = list.head
    while current_node.next != node
        current_node = next(current_node)
    end

    list.size -= 1
    pop_next(current_node)
end

怎么没有pop(list,value)的函数定义？我觉得这个放在高阶函数remove里更合适

3.高阶函数

3.1 filter

function Base.filter(fn::Function,list::List{T}) where T
    __filter = function __filter(node::Union{Nothing,ListNode{T}},res::List{T}) where T
        # edge
        if node == nothing
            res
        else
            if fn(node.value)
                __filter(node.next,push(res,node))
            else
                __filter(node.next,res)
            end

        end
    end


    __filter(list.head.next,List{T}())
end

3.2 map

function Base.map(fn::Function,list::List{T}) where T
    __map = function __map(node::Union{Nothing,ListNode{T}},res::List{T}) where T
        if node == nothing
            res
        else
            new_node = ListNode{T}(fn(node.value),nothing)
            __map(node.next,push(res,new_node))
        end

    end

    __map(list.head.next,List{T}())
end

3.3 reduce

function Base.reduce(fn::Function,list::List{T};init=0::T) where T
    __reduce = function __reduce(node::Union{Nothing,ListNode{T}},res::T) where T
        if node == nothing
            res
        else
            __reduce(node.next,fn(res,node.value))
        end
    end

    __reduce(list.head.next,init)
end

3.4 remove

function remove(fn::Function,list::List{T}) where T
    __remove = function __remove(node::Union{Nothing,ListNode{T}},res::List{T}) where T
        if node == nothing
            res
        else
            if fn(node.value)
                __remove(node.next,res)
            else
                __remove(node.next,push(res,node))
            end
        end
    end

    __remove(list.head.next,List{T}())
end

3.5 foreach

function Base.foreach(fn::Function,list::List{T}) where T
    __foreach = function  __foreach(node::Union{Nothing,ListNode{T}}) where T
        if node != nothing
            fn(node.value)
            __foreach(node.next)
        end
    end

    __foreach(list.head.next)
end

4.迭代器 iterate

function Base.iterate(list::List{T}) where T
    list.head.next.value,list.head.next
end

function Base.iterate(list::List{T},state::ListNode{T}) where T
    state.next == nothing ? nothing : (state.next.value,state.next)
end

写在最后

有哪位能把我的链表用Iterator这个库实现惰性，我实在力不从心了

1 个赞
2

为啥写链表啊，学习数据结构吗？
不是有DataStructures吗？还有感觉Vector贼快，虽然是连续地址，但是append很快。不知道是啥原理，就是快，可以当List用了。而且序号索引肯定比list快。

3

练个手，还有不喜欢他的书写格式，像Java一样，给你个大写的List，然后
List.add(value)
相比之下，我更喜欢C++的list.push_back(value)

我也不知道DataStrures这个包有没有编写高阶函数，有空fork过来修改好了