Advanced Data Structures

A second kind of sequence: the list

A list in Python is very similar to a string with two important differences:

• a list can contain any type of elements (and not only characters like strings)
• a list is mutable (unlike strings which are immutable)

Strings and lists are both called sequences or linear containers.

Lists are introduced in chapter 9 of the book. Go through the examples and make sure you properly understand:

• creating a list
• empty and nested lists
• indexing, slices, the in operator
• the range() function
• changing and deleting elements
• cloning a list (read about object, values and aliasing before)
• Traversing a list
• Converting a list of characters into a string and vice-versa

Sections 9.14 (List parameters) to 9.19 (Test-driven development) are advanced topics and can be skipped initially.

Work out exercises 1-6 and 17-18 in section 9.22.

An advanced data structure: the dictionary

Dictionaries (which are basically key-value pairs) are described in chapter 12 of the book. It is important to understand:

• creating a dictionary (empty or non-empty)
• adding a key-value pair
• obtain a value given a key
• using keys(), values(), has_key() and get()
• using a dictionary to speed up fibonacci() (section 12.5)
• counting letters (section 12.7)

Sections 12.4 (Sparse Matrices) and 12.8 (Robots) can be skipped on a first reading.

Work out exercises 1 and 2 in section 12.10. Can you think of a way to solve the problems without using dictionaries? Most modern programming languages have dictionaries. Can you see why?