1
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$
  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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ we cannot enhance above abstraction for any mutable operation, if we use tuple as repre. python list [1, 2, 3, 4] are array of references which is different from linked list [1, [2, [3, [4, 'empty']]] which has only two elements data element and rest of the list. \$\endgroup\$ Commented Jul 21, 2015 at 8:08
  • \$\begingroup\$ Inserting/deleting at the front of a Python list is an \$O(n)\$ operation, you could do it into a linked list like the OP's in \$O(1)\$. \$\endgroup\$
    – Jaime
    Commented Jul 21, 2015 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.