一.引言

   链表是一种强大的数据结构，可用于快速插入或删除元素。本文将使用class实现链表，并展示一些基本的函数。

二.链表实现

class Link:
    empty=() #just a symbol, It could be "I’m empty"
    def __init__(self,first,rest=empty):  #The rest of Link is Link or empty
        assert rest is Link.empty or isinstance(rest,Link)
        self.first=first
        self.rest=rest

三.常用函数

1.展示

1.1单层

def display_link(l):
    """
    >>> b = Link(4,Link(3, Link(9, Link(1))))
    >>> display_link(b)
    '< 4 3 9 1 >'
    """
    ret='<'
    while l is not Link.empty:
        ret+=" "+str(l.first)
        l=l.rest
    return ret+" >"

1.2嵌套 

def display_link(l):
    """
    >>> a = Link(1, Link(2, Link(1)))
    >>> b = Link(3, Link(2, Link(1)))
    >>> combined = Link(a, Link(b))
    >>> display_link(combined)
    '<< 1 2 1 >< 3 2 1 > >'
    """
    ret='<'
    while l is not Link.empty:
        if isinstance(l.first,Link):
            ret+=display_link(l.first)
        else:
            ret+=" "+str(l.first)
        l=l.rest
    return ret+" >"

2.求和

def sum_link(l):
    """
    >>> b = Link(4,Link(3, Link(9, Link(1))))
    >>> sum_link(b)
    17
    """
    # ret=0       #循环版本
    # while l is not Link.empty:
    #     ret+=l.first
    #     l=l.rest
    # return ret

    #递归版本
    if l is Link.empty:
        return 0
    return l.first + sum_link(l.rest)

3.map

def map_link(l,f):
    """Given a linked list, lnk, and a one argument function, f, return 
        a new linked list obtained from applying f to each element of lnk
    >>> b = Link(4,Link(3, Link(9, Link(1))))
    >>> display_link(map_link(b,lambda x:3+x))
    '< 7 6 12 4 >'
    """
    if l is Link.empty:
        return l
    return Link(f(l.first),map_link(l.rest,f))

4.使用map修改原链表

def mutate_link(l,f):
    """Given a linked list, lnk, and a one argument function, f, mutate 
        the linked list by applying f to each element of it
    >>> b = Link(4,Link(3, Link(9, Link(1))))
    >>> mutate_link(b,lambda x:3+x)
    >>> display_link(b)
    '< 7 6 12 4 >'
    """
    # #递归版本
    # if l is Link.empty:
    #     return
    # l.first=f(l.first)
    # mutate_link(l.rest,f)

    #循环版本
    #较难理解，可以用Python tutor跑一遍辅助理解
    while l is not Link.empty:    #note thatt the original lnk will not shrink!
        l.first=f(l.first)
        l=l.rest

5.倒序

def reverse_link(l):
    """return a new linked list whose order of elements is reversed
    >>> b = Link(4,Link(3, Link(9, Link(1))))
    >>> display_link(reverse_link(b))
    '< 1 9 3 4 >'
    """
    if l is Link.empty or l.rest is Link.empty:
        return l
    rest=reverse_link(l.rest)
    p=rest
    while p.rest is not Link.empty:
        p=p.rest
    p.rest=Link(l.first)
    return rest