List methods
Lists are sequences of objects, such as numbers, strings, or generally whatever you want to put into a sequence.
You create an empty list like this:
L = []
and you can then manipulate it by adding and removing elements to your hearts desire.
The range() method that you have used several times by now actually creates a list of numbers, so that is another way of creating a list.
Indexing
To get the ith element of a list, you can index it as L[i]. Indexing starts at zero, so L[0] is the first element, and if the list is n elements long, the last element is L[n-1].
You can index from the back by using negative numbers, so L[-1] is the last element in the list, L[-2] is the second last element and so on.
Slicing
You can get the sub-list starting at index i and ending at index j-1 using something called slicing, that looks like this L[i:j]. This can be handy at times.
Methods
Operations on lists are through something called "methods", which are essentially functions, but with a slight twist.
Where you would call a function on a list like this:
function(L)
you call a method on a list like this:
L.method()
so the only difference is really that you use the "dot notation" that you have seen for modules.
The clever thing about methods, as opposed to functions, is that you are explicit about which object (the list) you are manipulating, since it is part of the syntax for calling the method. Methods are an important part of something called Object Oriented Programming, a technique that has revolutionized programming back in the eighties and is pretty much dominant in programming these days. Unfortunately we do not have time in this course to cover Object Oriented Programming, so that is all I will say about it, except that you must use this different notation for manipulating lists.
Read the documentation for lists in the reading material to get a feeling for what you can do with lists.
The methods you are most likely to need for the exercises are:
- reverse() — reverses the order of a list, so [1,2,3] becomes [3,2,1]. If you want to remove an element from a list, it is much faster to remove elements at the end than from the beginning — for reasons we won't come into here — so sometimes it makes sense to first reverse the string and then pop() from the reversed string rather than from the original. That being said, it is typically easier to create new lists than modifying existing ones.
- pop() — removes an element from the back of a list.
- sort() — does exactly that, it sorts the elements in the list.
- append() — adds an element to the list.
List exercises
Remove multiples of a number
Write a function, removeMultiples(L,n), that returns a list of the elements of the list L that are not multiples of n. Remember that you can use the % operator to check if a number m is a multiple of n.
Example usage:
print removeMultiples([2, 3, 7, 5, 8, 9, 6], 3)
[2, 7, 5, 8]
Useful methods:
- append()
Sieve of Eratosthenes
Write a function, primes(n), that returns a list of all primes p such that p <= n.
You can use the following algorithm, called Sieve of Eratosthenes: Start with a list of all numbers from 2 up to and including n. We will manipulate the list as follows: take out the first, k, number and keep it in your list of primes to return later. Remove all multiples of k in the list, since these cannot be primes. The first element in the list will always be a prime if we follow this strategy, because we have removed all elements that are multiples of smaller numbers. When your initial list is empty, you are done, and you can remove all those elements that were, at one point, the first element in the list.
Example usage:
print primes(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Useful methods:
- append()
- reverse()
- pop()
Remove duplicates
Write a function, removeDuplicates(L), that takes a list L of numbers and returns a list R with the same numbers, but if L contains the same number more than once, R should only contain it once.
You can approach this problem in two different ways, and I suggest you try both.
- Sort the list and now any possible duplicates in the list will be neighbors, so you can just iterate through the list and remove elements that are next to their next neighbor.
- Put the elements in as keys in a dictionary, D. Any duplicates will not appear as duplicates when they are keys, so getting the D.keys() will give you the list you want.
Depending on which technique you use, you might end up modifying the input string using the sort approach. This is because sorting modifies the list, and it also means that if you call the method with a list, that list will be modified outside of the function as well.
This might seem a bit different from what you are used to, where changing a variable in a function doesn't change it outside, but this is because something else is going on. When you assign to a variable, you make the name of the variable point to the object that is the value. Assigning to a name in a function doesn't change what names outside the function are referring to. But if two names refer to the same object, like a list, and you modify the object in some way — like sorting the list — the object has changed and both names referring to the object will see a changed object.
An alternative to using a dictionary for the second approach is to use a set — and would usually be the right choice over dictionaries — but since we are not covering sets in this course you can just use a dictionary. You can read more of that here.
Example usage:
print removeDuplicates([1,2,2,1,4,2]) [1, 2, 4] <src lang="python"> Useful methods: - append() - sort() * Dictionary methods Dictionaries are data structures that works as tables, mapping from keys to values. You create an empty dictionary like this: <src lang="python"> D = {}
and you can then assign a value to a key like this:
D[key] = value
and get the value associated with the key like this
D[key]
if there is a value associated with this key. Otherwise you will get an error.
To test if a given key is in the dictionary you can use a test like this:
if key in D: print key, "is in the dictionary."
You can get a list of all keys in the dictionary using the method keys()
for key in D.keys(): print key
and a list of all the values in the dictionary using the values() method
for value in D.values(): print value
The items() method gives you both, by giving you a list of key-value pairs:
for key, value in D.items(): print key, "points to", value
Dictionary exercises
Count letters
Write a function, countLetters(x), that, given a string x, returns a dictionary that maps each letter to the number of occurrences of that letter in x.
Example usage:
print countLetters('mississippi') {'i': 4, 'p': 2, 's': 4, 'm': 1}
Anagrams
Write a function, isAnagram(x, y), that takes two strings as input and returns True if x and y are anagrams and False otherwise.
Example usage:
print isAnagram('saltine', 'entails') True