Linked list abstraction using python arrays

1. 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]
   

2. 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)))
   

3. 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)
   

4. 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.

Looks good to me. As you probably know, there's no point building a "list abstraction" in Python, since Python already has lists that work perfectly fine. You're "building a list out of lists", which is a pessimization. However, as a learning exercise, it's fine.

Your create_linked_list function is what computer people call cons (a term inherited from the Lisp programming language). Also from Lisp, your first is usually known as car (or head) and your rest is usually known as cdr (or tail).

In Python, it would be more idiomatic to do this exercise using tuple as the underlying type of a cons cell, not list:

def cons(hd, tl):
    return (hd, tl)

def car(lst):
    assert lst is not None
    return lst[0]

def cdr(lst):
    assert lst is not None
    return lst[1]

mylist = (1, (2, (3, None)))
assert car(mylist) == 1
assert cdr(mylist) == (2, (3, None))

def count(s, value):
    def counta(s, value, acc):
       return acc if s is None else counta(cdr(s), value, acc + (car(s) == value))
    return counta(s, value, 0)

The next step would probably be to write yourself the functions map and foldl/foldr, and then implement count in terms of those functions.