Lists

A list is a data structure that can hold an ordered collection of items. These items, known as elements, can be of any data type, including numbers, strings, or even other lists. A comma-separated list of expressions in square brackets creates a list:

>>> list_of_values = [2, 1, 3, True, 3]
>>> nested_list = [2, [1, 3], [True, [3]]]

Each position in a list has an index, with the left-most element indexed 0.

>>> list_of_values[0]
2
>>> nested_list[1]
[1, 3]

A negative index counts from the end, with the right-most element indexed -1.

>>> nested_list[-1]
[True, [3]]

Adding lists creates a longer list containing the elements of the added lists.

>>> [1, 2] + [3] + [4, 5]
[1, 2, 3, 4, 5]

List Comprehensions

A list comprehension describes the elements in a list and evaluates to a new list containing those elements.

There are two forms:

[<expression> for <element> in <sequence>]
[<expression> for <element> in <sequence> if <conditional>]

Here's an example that starts with [1, 2, 3, 4], picks out the even elements 2 and 4 using if i % 2 == 0, then squares each of these using i*i. The purpose of for i is to give a name to each element in [1, 2, 3, 4].

>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

This list comprehension evaluates to a list of:

• The value of i*i
• For each element i in the sequence [1, 2, 3, 4]
• For which i % 2 == 0

In other words, this list comprehension will create a new list that contains the square of every even element of the original list [1, 2, 3, 4].

We can also rewrite a list comprehension as an equivalent for statement, such as for the example above:

>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]

List Slicing

To create a copy of part or all of a list, we can use list slicing. The syntax to slice a list lst is: lst[<start index>:<end index>:<step size>].

This expression evaluates to a new list containing the elements of lst:

• Starting at and including the element at <start index>.
• Up to but not including the element at <end index>.
• With <step size> as the difference between indices of elements to include.

If the start, end, or step size are not explicitly specified, Python has default values for them. A negative step size indicates that we are stepping backwards through a list when including elements.

>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[:3]     # Start index defaults to 0
[6, 5, 4]
>>> lst[3:]     # End index defaults to len(lst)
[3, 2, 1, 0]
>>> lst[:]      # Creates a copy of the list
[6, 5, 4, 3, 2, 1, 0]
>>> lst[:] == lst
True
>>> lst[:] is lst
False
>>> lst[::-1]   # Make a reversed copy of the entire list
[0, 1, 2, 3, 4, 5, 6]
>>> lst[::2]    # Skip every other; step size defaults to 1 otherwise
[6, 4, 2, 0]

Dictionaries

A dictionary contains key-value pairs and allows the values to be looked up by their key using square brackets. Each key must be unique.

>>> d = {2: 4, 'two': ['four'], (1, 1): 4}
>>> d[2]
4
>>> d['two']
['four']
>>> d[(1, 1)]
4

The sequence of keys or values or key-value pairs can be accessed using .keys() or .values() or .items().

>>> for k in d.keys():
...     print(k)
...
2
two
(1, 1)
>>> for v in d.values():
...     print(v)
...
4
['four']
4
>>> for k, v in d.items():
...     print(k, v)
...
2 4
two ['four']
(1, 1) 4

You can check whether a dictionary contains a key using in:

>>> 'two' in d
True
>>> 4 in d
False

A dictionary comprehension is an expression that evaluates to a new dictionary.

>>> {3*x: 3*x + 1 for x in range(2, 5)}
{6: 7, 9: 10, 12: 13}

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

A path is a sequence of trees in which each is the parent of the next.

A tree is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a folder, you have folders separating your projects, lab assignments, and homework. The next level is folders that separate different assignments, hw01, lab01, hog, etc., and inside those are the files themselves, including the starter files and ok. Below is an incomplete diagram of what your cs61a directory might look like.

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

For a tree t:

• Its root label can be any value, and label(t) returns it.
• Its branches are trees, and branches(t) returns a list of branches.
• An identical tree can be constructed with tree(label(t), branches(t)).
• You can call functions that take trees as arguments, such as is_leaf(t).
• That's how you work with trees. No t == x or t[0] or x in t or list(t), etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree t1, for which its branch branches(t1)[1] is t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])