CS61A: Lecture 21

Lecture

Composition

• A linked list is a recursive data structure that represents a sequence.

  List Efficiency - Fast

• Appending, assigning, and list comprehensions are fast
  • The reason that appending is so fast, is because of the way that lists are represented in the python interpreter.
  • A list is a contiguous block of memory that actually has some additional reserved space within it for list appending
    • When this space runs out, python will move the list contents to a memory space with more capacity.
• Assiging is also very fast, because we can very quickly calculate the memory address to update a value through the list index.
• List comprehension is fast because the python interpreter pre-allocates the amount of memory required for the list, and just fills in the values.

List Efficiency - Slow

• Inserting (beginning/middle), slicing, and adding lists are slow:
• Slicing lists is slow because it creates a copy of a list.
• Inserting is slow as well. Whenever an element is inserted into a list, every value after the element must be shifted forward once in the list, which slows down the program.
• Adding two lists also does not change the original lists, it makes a new list instead, which requires us to reconstruct both lists again.

Linked List Structure

• Linked Lists are not built into python, so we must create it ourselves.
• A linked list is either:
  • Empty
  • The first value and the rest of the linked list. Thus, a linked list is a pair of values.
• The reason that we would use a linked-list is because operations such as insertion are much faster than a regular list, because we could just adjust the attributes of the Link instances.
• Implementation:

class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

• To move forward in a linked list, we just set the linked list to the rest.

from linked_list import Link
s = Link(1, Link(2, Link(3)))
print("Before moving:", s)
s = s.rest
print("After moving:", s)

Before moving: (1->2->3)
After moving: (2->3)

• We may also embed a linked list within a linked list

s = Link(3, Link(Link(4, Link(5)), Link(6)))

print(s.rest.first.rest.first)

5

• Ex: Create a function that inserts a v after each v in a linked list ll.

def double(ll, v):
    """Insert another v after each v in linked list ll.
    
    >>> ll = Link(2, Link(7, Link(1, Link(8, Link(2, Link(8))))))
    >>> double_link(s, 8)
    >>> print(ll)
    (2->7->1->8->8->2->8->8)
    """
    while ll is not Link.empty:
        if ll.first == v:
            ll.rest = Link(v, ll.rest)
            ll = ll.rest.rest
        else:
            ll = ll.rest

ll1 = Link(2, Link(7, Link(1, Link(8, Link(2, Link(8))))))
double(ll1, 8)
print(ll1)

(2->7->1->8->8->2->8->8)

• Ex: Create a copy of a linked list

def copy_linked_list(ll):
    if ll is Link.empty:
        return ll
    return Link(ll.first, copy_linked_list(ll.rest))

s = Link(3, Link(Link(4, Link(5)), Link(6)))
t = copy_linked_list(s)
s is t

False

• Ex: Create a slice of a linked list

def slice_linked_list(ll, start, end):
    assert start >= 0 and end >= 0
    if start == end or ll is Link.empty:
        return Link.empty
    elif start == 0:
        return Link(ll.first, slice_linked_list(ll.rest, start, end-1))
    return slice_linked_list(ll.rest, start-1, end-1)


s = Link(1, Link(2, Link(3, Link(4))))
t = slice_linked_list(s, 2, 4)
t
    

Link(3, Link(4))