Python timings of linked list vs Python list operations

perf.py

class Link:
    """A linked list."""
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

def link_insert_head(r):
    rr = reversed(r)
    link = Link(next(rr))
    for i in rr:
        link = Link(i, link)
    return link

def list_insert_head(r):
    l = []
    for i in reversed(r):
        l.insert(0, i)
    return l

def link_insert_end(r):
    it = iter(r)
    start = Link(next(it))
    for i in it:
        p = start
        while not p.rest == Link.empty:
            p = p.rest
        p.rest = Link(i)
    return start

def list_insert_end(r):
    l = []
    for i in r:
        l.append(i)
    return l

def link_insert_mid(r):
    it = iter(r)
    start = Link(next(it))
    length = 0
    for v in it:
        p = start
        position = length // 2
        i = 0
        while not p.rest == Link.empty and i < position:
            p = p.rest
            i += 1
        p.rest = Link(v, p.rest)
        length += 1
    return start

def list_insert_mid(r):
    l = []
    for i in r:
        l.insert(len(l) // 2, i)
    return l

def link_search(r):
    midpoint = (r.stop - r.start) // 2
    start = link_insert_head(r)
    p = start
    while not p.rest == Link.empty:
        if p.first == midpoint:
            return True
        p = p.rest
    return False

def list_search(r):
    midpoint = (r.stop - r.start) // 2
    l = list(r)
    return midpoint in l

def link_index(r):
    midpoint = (r.stop - r.start) // 2
    start = link_insert_head(r)
    p = start
    i = 0
    while not p.rest == Link.empty and i < midpoint:
        p = p.rest
        i += 1
    return p.first

def list_index(r):
    midpoint = (r.stop - r.start) // 2
    l = list(r)
    return l[midpoint]

def link_len(r):
    start = link_insert_head(r)
    p = start
    i = 0
    while not p.rest == Link.empty:
        p = p.rest
        i += 1
    return i

def list_len(r):
    return len(list(r))

def link_sum(r):
    start = link_insert_head(r)
    acc = 0
    while not start.rest == Link.empty:
        acc += start.first
        start = start.rest
    return acc

def list_sum(r):
    return sum(list(r))

# Best insert for each
def link_push(r):
    return link_insert_head(r)
def list_push(r):
    return list_insert_end(r)

# Best case removal for each
def link_pop(r):
    link = link_push(r)
    while link:
        link = link.rest
    return link
def list_pop(r):
    l = list_push(r)
    while l:
        l.pop()

l = locals()
import timeit
from itertools import product
def timings(r = 10000, n = 10):
    timings = {}
    for op in ['insert_head', 'insert_mid', 'insert_end', 'search', 'index', 'len', 'sum', 'push', 'pop']:
        for t in ['link', 'list']:
            k = f"{t}_{op}"
            f = l[k]
            timings[k] = timeit.timeit(lambda: f(range(r)), number=n)
            print(f"{k}: {timings[k]}")
        adv = timings[f"link_{op}"] / timings[f"list_{op}"]
        print(f"- List advantage: {adv}")
    return timings
if __name__ == '__main__':
    import argparse
    parser = argparse.ArgumentParser(description="Compare Linked List vs Python list operation timings")
    parser.add_argument('-n', type=int, default=timings.__defaults__[0], help=f"How much data to use; note that some operations scale exponentially in n (default: {timings.__defaults__[0]})")
    parser.add_argument('-t', type=int, default=timings.__defaults__[1], help=f"How many times to repeat the timing code (default: {timings.__defaults__[1]})")
    args = parser.parse_args()
    timings(args.n, args.t)