Linked list abstraction using python arrays
asserts are not run if you use Python's optimized bytecode mode. And while nobody uses the -O switch, because the benefits are really meager, it still is not a good practice to you assert to validate user input. It is typically used to document invariants or assumptions, which roughly translates to it validating input that other parts of your code have generated, not users. Instead, you should raise an adequate exception, e.g.:

def first(s):
    """Return a first element of a linked list s"""
    if not is_link(s):
        raise TypeError("first only applies to linked lists.")
    if s == empty:
        raise IndexError("empty linked list has no first element.")
    return s[0]

Your is_link function, which is called by most of your other functions, has to scan the full list to validate it. That means that, especially with functions like count, which already need to scan the whole list, performance is going to end up being \$O(n^2)\$. That is not a good thing! You should probably go for a lazier is_link, that defers erroring until possible non-compliant items are actually used, e.g.:

def is_link(s)
    return s == empty or (isinstance(s, list) and len(s) == 2 and
                          (s[1] == empty or isinstance(s[1], list)))

You can simplify your count code a lot, by letting the recursion stack keep track of the number of items, rather than doing it yourself explicitly:

def count(s, value):
    if isempty(s):
        return 0
    return count(rest(s), value) + (1 if first(s) == value else 0)

While obviously doable, this reusing a list to make a linked list doesn't seem like a very good choice. It is very typical to use a dict of lists to represent a graph, rather than creating an explicit new class. And heaps also fit very well into a bare list with some helper functions, that's e.g. how the heapq module is implemented. But in your case, while it would be ok for a quick and dirty implementation where you directly accessed s[0] and s[1], if you are going to go through the trouble of writing all those helper functions, it is infinitely clearer to actually create a new class that embodies the abstraction.