Linked list abstraction using python arrays Building linked list abstraction using class 'list' data model.

##################
#   Linked List  #
##################



#Representation - start
empty = 'empty'
def is_link(s):
    """ s is a linked list if it is empty or a (first, rest) pair."""
    return s == empty or (isinstance(s, list) and len(s) == 2 and is_link(s[1]))
#Constructor
def link(first, rest):
    """Construct a linked list from its first element and the rest."""
    assert is_link(rest), "rest must be a linked list"
    return [first, rest]
#Selector 1
def first(s):
    """Return a first element of a linked list s"""
    assert is_link(s), "first only applies to linked lists."
    assert s != empty, "empty linked list has no first element."
    return s[0]
#Selector 2
def rest(s):
    """Return the rest of the elements of a linked list s."""
    assert is_link(s), "rest only applies to linked lists."
    assert s != empty, "empty linked list has no rest."
    return s[1]

def isempty(s):
    return s == 'empty'

#Representation - end

###  +++ === Abstraction barrier === +++ ###

#Use(interface) -  start
def create_linked_list(first, rest):
    return link(first, rest)

def len_rlist(s):
    """Compute the length of the recursive list s"""
    def compute_length(s, length):
        if isempty(s):
            return length
        else:
            return compute_length(rest(s), length + 1)
    return compute_length(s, 0)

def getitem_rlist(s, i):
    """Return the element at index i of recursive list s"""
    if i == 1:
        return first(s)
    else:
        return getitem_rlist(rest(s), i-1)

def count(s, value):
    """Count the occurence of value in the list s """
    def count_occurence(s, value, count):
        if isempty(s):
           return count
        else:
           if first(s) == value:
              return count_occurence(rest(s), value, count + 1)
           else:
              return count_occurence(rest(s), value, count)
    return count_occurence(s, value, 0)

#Use - end


#Constructor and Selector constitutes Abstract Data Type that supports below invariants:
#If a recursive list s is constructed from a first element f and a recursive list r, then
#   • first(s) returns f, and
#   • rest(s) returns r, which must be a list or 'empty'.

#Code using this abstraction
Lst = empty
Lst = create_linked_list(4, Lst)   #  Representation [4, 'empty']
Lst = create_linked_list(3, Lst)   #  Representation [3, [4, 'empty']]
Lst = create_linked_list(1, Lst)   #  Representation [1, [3, [4, 'empty']]]
Lst = create_linked_list(1, Lst)   #  Representation [1, [1, [3, [4, 'empty']]]]
print(count(Lst, 1))


Intention is to build a single linked list abstraction that has no correctness issues.

Are there any limitations in building this abstraction?
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.