Linked List with Python Built-in List

Intro

I was currently reading the Composing Programs, which amazed me over and over again.

In section 2.3.7 Linked Lists, a definition of linked list was introduced by using the python built-in type list only. It used empty = 'empty' to suggest the end of the linked list, whereas I plan to use NoneType to standardize the code.

link0 = [1, [2, [3, [4, 'empty']]]]  # Linked list from book
link1 = [1, [2, [3, [4, None]]]]     # Linked list with NoneType

Construct

Firstly, we need a function to check a given list is a linked list or not:

def is_link(s):
    """return True if formal parameter s is a linked list. """
    return s == None or (len(s) == 2 and is_link(s[1]))

And naturally, the function link() can help us wrap up the head and rest two part into a new list whose length is 2.

def link(head, rest=None):
    assert is_link(rest), "The rest part must be a linked list. "
    return [head, rest]

Different from the definition I written in my previous post, this definition generates a linked list from tail side to head. But nothing changed actually. Let’s take a closer look at it.

Notice:

According to this definition, None is a legal linked list, whereas [None] is illegal.

This detail could be helpful to the functions coming ahead.

Implementation

We need some useful functions to manipulate our new data type.

def head(s):
    """Get value of current node. """
    assert is_link(s), "The function must be applied to a linked list. "
    assert s != None, "No empty linked list. "
    return s[0]

def rest(s):
    """Move onto next node. """
    assert is_link(s), "The function must be applied to a linked list. "
    assert s != None, "No empty linked list. "
    return s[1]

Except these functions unwrapping the linked list, we also need to measure it’s length and evaluate the value of arbitrary node.

Iterative

def len_link(s):
    """Return the length of the linked list. """
    length = 0
    while s:
        s, length = rest(s), length + 1
    return length

def get_item_link(s, i):
    """Return the i-th term value of given linked list s. """
    assert i >= 0, "item's index should bigger than or equal to zero. "
    assert i <= len_link(s)-1, "Given index exceeds the length of list. "
    # First item's index is zero. 
    while i > 0:
        s, i = rest(s), i - 1
    return head(s)

Based on these fuctions, we can preliminarily manipulate our linked list.

Recursive

We can also rewrite our len_link() and get_item_link() functions in a recursive manner. This concept will emerge again later and is quite significant.

def len_link_recursive(s): 
    """Return the length of the linked list. Recursive version. """
    if not s:
        return 0
    return 1 + len_link_recursive(rest(s))

def get_item_link_recursive(s, i):
    """Return the i-th term value of given linked list s. Recursive version. """
    assert i >= 0, "item's index should bigger than or equal to zero. "
    assert i <= len_link_recursive(s)-1, "Given index exceeds the length of list. "
    # First item's index is zero. 
    if i == 0: 
        return head(s)
    return get_item_link_recursive(rest(s), i-1)

Abstraction

Append

Next step, we need to append the linked list. It seems that extending a node-form linked list - by simply altering it’s Next attribute - is handy, while appending the list-form linked list sounds not so intuitive. Well, partially true.

Here is the function from Composing Programs.

def extend_link(s, t):
    """Return a list with the elements of s followed by those of t."""
    assert is_link(s) and is_link(t)
    if s == None:
        return t
    else:
        return link(first(s), extend_link(rest(s), t))

This is a quite standard recursive function. And here is the function I typed when I was first conceiving it. To make life much easier, I prefer writing them separately.

def append_link(s, item):
    """Return a new linked list which was appended with 'item' from s. """
    assert is_link(s) and is_link(item), "Input should be linked list. "
    i = len_link_recursive(s)
    if i == 0:
        # Special case for empty list
        return link(item)
    elif i == 1:
        return link(head(s), item)
    else:
        lk =  append_link(rest(s), item)
    return link(head(s), lk)

Similarly, we can manage any other function with the concepts of higher-order function and recursion.

For example, apply a function to all entries in a linked list.

Apply to all

def apply_to_all_link(f, s):
    """Apply function f to all elements of s. """
    assert is_link(s), "Only apply to a linked list. "
    if s == None:
        return s
    return link(f(first(s)), apply_to_all_link(f, rest(s)))

Conversion

So how to convert a linked list into a normal list? And vice versa?

Inherited from methods above, answers may not be very complicated.

def link_to_list(s):
    """Convert a linked list into a normal list. """
    assert is_link(s), "Should be a linked list. "
    if rest(s) and s:
        return [head(s)] + link_to_list(rest(s))
    return [head(s)]

def list_to_link(s):
    """Convert a normal list into a linked list. """
    if len(s) == 1:
        return link(s[0])
    return link(s[0], list_to_link(s[1:]))

Note

Using python built-in list to form a linked list, this probably is not a vary popular approach, and its efficiency is open to discussion.

However, what truly intriguing here is that even only one data type can be realized in various way. Also, every function in this post can be achieved in diverse manners. The possibilities in programming are always charming and charismatic.

References

1. Composing Programs by John DeNero;
2. Online Python Tutor;