- Creating Lists
- Empty List
print("Two standard ways to create an empty list:")
a = [ ]
b = list()
print(type(a), len(a), a)
print(type(b), len(b), b)
print(a == b)
- List with One Element (Singleton)
a = [ "hello" ]
b = [ 42 ]
print(type(a), len(a), a)
print(type(b), len(b), b)
print(a == b)
- List with Multiple Elements
a = [2, 3, 5, 7]
b = list(range(5))
c = ["mixed types", True, 42]
print(type(a), len(a), a)
print(type(b), len(b), b)
print(type(c), len(c), c)
- Variable-Length List
n = 10
a = [0] * n # creates a list with n 0s
b = list(range(n))
print(type(a), len(a), a)
print(type(b), len(b), b)
- List Functions and Operations
a = [ 2, 3, 5, 2 ]
print("a = ", a)
print("len =", len(a))
print("min =", min(a))
print("max =", max(a))
print("sum =", sum(a))
# Create some lists
a = [ 2, 3, 5, 3, 7 ]
b = [ 2, 3, 5, 3, 7 ] # same as a
c = [ 2, 3, 5, 3, 8 ] # differs in last element
d = [ 2, 3, 5 ] # prefix of a
print("a =", a)
print("b =", b)
print("c =", c)
print("d =", d)
print("------------------")
print("a == b", (a == b))
print("a == c", (a == c))
print("a != b", (a != b))
print("a != c", (a != c))
print("------------------")
print("a < c", (a < c))
print("a < d", (a < d))
- Accessing Elements (Indexing and Slicing)
# Indexing and slicing for lists works the same way as it did for strings!
a = [2, 3, 5, 7, 11, 13]
print("a =", a)
# Access non-negative indexes
print("a[0] =", a[0])
print("a[2] =", a[2])
# Access negative indexes
print("a[-1] =", a[-1])
print("a[-3] =", a[-3])
# Access slices a[start:end:step]
print("a[0:2] =", a[0:2])
print("a[1:4] =", a[1:4])
print("a[1:6:2] =", a[1:6:2])
- List Mutability and Aliasing
Unlike strings, lists are mutable. This means that they can be changed, without creating a new list.
This also forces us to better understand aliases, when two variables reference the same value. Aliases are only interesting (and challenging) for mutable values like
lists.
Note: it will be especially helpful to use the Visualize feature in the following examples.
- Example:
# Create a list
a = [ 2, 3, 5, 7 ]
# Create an alias to the list
b = a
# We now have two references (aliases) to the SAME list
a[0] = 42
b[1] = 99
print(a)
print(b)
- Function Parameters are Aliases:
def f(a):
a[0] = 42
a = [2, 3, 5, 7]
f(a)
print(a)
# Note that the parameter alias can still be broken by re-assigning the variable
a = [3, 2, 1]
def foo(a):
a[0] = 1
a = [5, 2, 0] # we break the alias here!
a[0] = 4
foo(a)
print(a)
- Another Example:
# Create a list
a = [ 2, 3, 5, 7 ]
# Create an alias to the list
b = a
# Create a different list with the same elements
c = [ 2, 3, 5, 7 ]
# a and b are references (aliases) to the SAME list
# c is a reference to a different but EQUAL list
print("initially:")
print(" a==b :", a==b)
print(" a==c :", a==c)
print(" a is b:", a is b) # the is operation tells if two values are aliases, or basic datatypes
print(" a is c:", a is c)
# Now changes to a also change b (the SAME list) but not c (a different list)
a[0] = 42
print("After changing a[0] to 42")
print(" a=", a)
print(" b=", b)
print(" c=", c)
print(" a==b :", a==b)
print(" a==c :", a==c)
print(" a is b:", a is b)
print(" a is c:", a is c)
- Copying Lists
- Copy vs Alias
# Because of aliasing, we have to be careful if we share a reference
# to a list in the same way we might for number or a string,
# by simply setting b = a, like so:
import copy
# Create a list
a = [ 2, 3 ]
# Try to copy it
b = a # Error! Not a copy, but an alias
c = copy.copy(a) # Ok
# At first, things seem ok
print("At first...")
print(" a =", a)
print(" b =", b)
print(" c =", c)
# Now modify a[0]
a[0] = 42
print("But after a[0] = 42")
print(" a =", a)
print(" b =", b)
print(" c =", c)
- Other ways to copy
import copy
a = [2, 3]
b = copy.copy(a)
c = a[:]
d = a + [ ]
e = list(a)
a[0] = 42
print(a, b, c, d, e)
- Destructive and Non-destructive Functions
Because lists are mutable, we can change them in two ways:
destructively (which modifies the original value directly), and
non-destructively (which creates a new list and does not modify the original value).
This also affects how we write functions that use lists.
- Destructive functions
# A destructive function is written to directly change the provided list
# It does not need to return anything, as the caller can access the original list
def fill(a, value):
for i in range(len(a)):
a[i] = value
a = [1, 2, 3, 4, 5]
print("At first, a =", a)
fill(a, 42)
print("After fill(a, 42), a =", a)
- Non-destructive function
import copy
## First, a quick primer on modifying lists ##
## We'll talk about these more in a bit ##
a = [1, 2, 3, 4]
# .remove() DESTRUCTIVELY removes the given value from the list
a.remove(2)
print(a) # [1, 3, 4]
# .append() DESTRUCTIVELY adds the given value to the end of the list
a.append(70)
print(a) # [1, 3, 4, 70]
## Now, on to NON-DESTRUCTIVE functions! ##
def destructiveRemoveAll(a, value):
while (value in a):
a.remove(value)
def nonDestructiveRemoveAll(a, value):
# Typically, we write non-destructive functions by building a new list
# instead of changing the original
result = []
for element in a:
if (element != value):
result.append(element)
return result # non-destructive functions still need to return!
def alternateNonDestructiveRemoveAll(a, value):
# We can write the same function by breaking the alias,
# then using the destructive approach
a = copy.copy(a)
destructiveRemoveAll(a, value)
return a
a = [ 1, 2, 3, 4, 3, 2, 1 ]
print("At first")
print(" a =", a)
destructiveRemoveAll(a, 2)
print("After destructiveRemoveAll(a, 2)")
print(" a =", a)
b = nonDestructiveRemoveAll(a, 3)
print("After b = nonDestructiveRemoveAll(a, 3)")
print(" a =", a)
print(" b =", b)
c = alternateNonDestructiveRemoveAll(a, 1)
print("After c = alternateNonDestructiveRemoveAll(a, 1)")
print(" a =", a)
print(" c =", c)
- Finding Elements
- Check for list membership: in
a = [ 2, 3, 5, 2, 6, 2, 2, 7 ]
print("a =", a)
print("2 in a =", (2 in a))
print("4 in a =", (4 in a))
-
Check for list non-membership: not in
a = [ 2, 3, 5, 2, 6, 2, 2, 7 ]
print("a =", a)
print("2 not in a =", (2 not in a))
print("4 not in a =", (4 not in a))
-
Count occurrences in list: list.count(item)
a = [ 2, 3, 5, 2, 6, 2, 2, 7 ]
print("a =", a)
print("a.count(1) =", a.count(1))
print("a.count(2) =", a.count(2))
print("a.count(3) =", a.count(3))
-
Find index of item: list.index(item) and list.index(item, start)
-
Example
a = [ 2, 3, 5, 2, 6, 2, 2, 7 ]
print("a =", a)
print("a.index(6) =", a.index(6))
print("a.index(2) =", a.index(2))
print("a.index(2,1) =", a.index(2,1))
print("a.index(2,4) =", a.index(2,4))
-
Problem: crashes when item is not in list
a = [ 2, 3, 5, 2 ]
print("a =", a)
print("a.index(9) =", a.index(9)) # crashes!
print("This line will not run!")
-
Solution: use (item in list)
a = [ 2, 3, 5, 2 ]
print("a =", a)
if (9 in a):
print("a.index(9) =", a.index(9))
else:
print("9 not in", a)
print("This line will run now!")
- Adding Elements
- Destructively (Modifying Lists)
- Add an item with list.append(item)
a = [ 2, 3 ]
a.append(7)
print(a)
- Add a list of items with list += list2 or list.extend(list2)
a = [ 2, 3 ]
a += [ 11, 13 ]
print(a)
a.extend([ 17, 19 ])
print(a)
- Insert an item at a given index
a = [ 2, 3, 5, 7, 11 ]
a.insert(2, 42) # at index 2, insert 42
print(a)
- Non-Destructively (Creating New Lists)
- Add an item with list1 + list2
a = [ 2, 3 ]
b = a + [ 13, 17 ]
print(a)
print(b)
- Insert an item at a given index (with list slices)
a = [ 2, 3 ]
b = a[:2] + [5] + a[2:]
print(a)
print(b)
- Destructive vs Non-Destructive Example
print("Destructive:")
a = [ 2, 3 ]
b = a
a += [ 4 ]
print(a)
print(b)
print("Non-Destructive:")
a = [ 2, 3 ]
b = a
a = a + [ 4 ] # this overwrites a, but not the alias of b
print(a)
print(b)
- Removing Elements
- Destructively (Modifying Lists)
- Remove an item with list.remove(item)
a = [ 2, 3, 5, 3, 7, 6, 5, 11, 13 ]
print("a =", a)
a.remove(5)
print("After a.remove(5), a=", a)
a.remove(5)
print("After another a.remove(5), a=", a)
- Remove an item at a given index with list.pop(index)
a = [ 2, 3, 4, 5, 6, 7, 8 ]
print("a =", a)
item = a.pop(3)
print("After item = a.pop(3)")
print(" item =", item)
print(" a =", a)
item = a.pop(3)
print("After another item = a.pop(3)")
print(" item =", item)
print(" a =", a)
# Remove last item with list.pop()
item = a.pop()
print("After item = a.pop()")
print(" item =", item)
print(" a =", a)
- Non-Destructively (Creating New Lists)
- Remove an item at a given index (with list slices)
a = [ 2, 3, 5, 3, 7, 5, 11, 13 ]
print("a =", a)
b = a[:2] + a[3:]
print("After b = a[:2] + a[3:]")
print(" a =", a)
print(" b =", b)
- Looping Over Lists
- Looping with a normal for loop:
a = [ 2, 3, 5, 7 ]
print("Here are the items in a with their indexes:")
for index in range(len(a)):
print("a[", index, "] =", a[index])
- Looping with a for each loop
# Lists and strings are both iterable types.
# This means that we can iterate (loop) over them directly!
a = [ 2, 3, 5, 7 ]
print("Here are the items in a:")
for item in a:
print(item)
- Hazard: modifying inside a for loop
# IMPORTANT: don't change a list inside a for loop! The indexes will behave unpredictably.
# This isn't a problem for strings because they aren't mutable.
a = [ 2, 3, 5, 3, 7 ]
print("a =", a)
# Failed attempt to remove all the 3's
for index in range(len(a)):
if (a[index] == 3): # this eventually crashes!
a.pop(index)
print("This line will not run!")
- Also Hazard: modifying inside a for-each loop
# If we remove items in a for-each loop, the loop won't crash,
# but it won't behave as we would expect either!
a = [3, 3, 2, 3, 4]
for item in a: # this won't reach every item in the list!
if (item == 3):
a.remove(item)
print(a) # should be [2, 4], but there's still a 3 in there!
- Better: modifying inside a while loop
# Modify the list in a while loop instead of a for loop,
# to control how indexes
a = [ 2, 3, 5, 3, 7 ]
print("a =", a)
# Successful attempt to remove all the 3's
index = 0
while (index < len(a)):
if (a[index] == 3):
a.pop(index)
else:
index += 1
print("This line will run!")
print("And now a =", a)
- List Methods: Sorting and Reversing
Lists have many built-in methods. It's common for these methods to be implemented both destructively and non-destructively.
- Destructively with list.sort() or list.reverse()
a = [ 7, 2, 5, 3, 5, 11, 7 ]
print("At first, a =", a)
a.sort()
print("After a.sort(), a =",a)
a = [ 2, 3, 5, 7 ]
print("Here are the items in reverse:")
a.reverse()
for item in a:
print(item)
print(a)
- Non-Destructively with sorted(list) and reversed(list)
a = [ 7, 2, 5, 3, 5, 11, 7 ]
print("At first")
print(" a =", a)
b = sorted(a)
print("After b = sorted(a)")
print(" a =", a)
print(" b =", b)
a = [ 2, 3, 5, 7 ]
print("Here are the items in reverse:")
for item in reversed(a):
print(item)
print(a)
- More list methods
For most list methods, see
this
table and
this
list of list methods.
- Tuples (Immutable Lists)
Tuples are exactly like lists, except they are immutable.
We cannot change the values of a tuple.
- Tuple syntax
t = (1, 2, 3)
print(type(t), len(t), t)
a = [1, 2, 3]
t = tuple(a)
print(type(t), len(t), t)
- Tuples are immutable
t = (1, 2, 3)
print(t[0])
t[0] = 42 # crash!
print(t[0])
- Parallel (tuple) assignment
(x, y) = (1, 2)
print(x)
print(y)
# tuples are useful for swapping!
(x, y) = (y, x)
print(x)
print(y)
- Singleton tuple syntax
t = (42)
print(type(t), t*5)
t = (42,) # use a comma to force the type
print(type(t), t*5)
- List Comprehensions
List comprehensions are a handy way to create lists using simple loops
all in one line.
# Long way
a = []
for i in range(10):
a.append(i)
print(a)
# Short way
a = [i for i in range(10)]
print(a)
# We can also add conditionals at the end (but keep it simple!)
a = [(i*100) for i in range(20) if i%5 == 0]
print(a)
- Converting Between Lists and Strings
# use list(s) to convert a string to a list of characters
a = list("wahoo!")
print(a) # prints: ['w', 'a', 'h', 'o', 'o', '!']
# use s1.split(s2) to convert a string to a list of strings delimited by s2
a = "How are you doing today?".split(" ")
print(a) # prints ['How', 'are', 'you', 'doing', 'today?']
# use "".join(a) to convert a list of characters to a single string
print("".join(a)) # prints: Howareyoudoingtoday?
# "".join(a) also works on a list of strings (not just single characters)
a = ["parsley", "is", "gharsley"] # by Ogden Nash!
print("".join(a)) # prints: parsleyisgharsley
print(" ".join(a)) # prints: parsley is gharsley
- Worked Examples Using Lists
- The Locker Problem
- Anagrams
- The Sieve of Eratosthenes
- The Prime Counting Function
- The Locker Problem
def lockerProblem(lockers):
isOpen = [ False ] * (lockers+1)
students = lockers
for student in range(1,students+1):
for locker in range(student, lockers+1, student):
isOpen[locker] = not isOpen[locker]
openLockers = [ ]
for locker in range(1, lockers+1):
if isOpen[locker]:
openLockers.append(locker)
return openLockers
print(lockerProblem(2000))
- Anagrams
def letterCounts(s):
counts = [0] * 26
for ch in s.upper():
if ((ch >= "A") and (ch <= "Z")):
counts[ord(ch) - ord("A")] += 1
return counts
def isAnagram(s1, s2):
# First approach: same #'s of each letter
return (letterCounts(s1) == letterCounts(s2))
def isAnagram(s1, s2):
# Second approach: sorted strings must match!
return sorted(list(s1.upper())) == sorted(list(s2.upper()))
def testIsAnagram():
print("Testing isAnagram()...", end="")
assert(isAnagram("", "") == True)
assert(isAnagram("abCdabCd", "abcdabcd") == True)
assert(isAnagram("abcdaBcD", "AAbbcddc") == True)
assert(isAnagram("abcdaabcd", "aabbcddcb") == False)
print("Passed!")
testIsAnagram()
- The Sieve of Eratosthenes
# Sieve of Eratosthenes
# This function returns a list of prime numbers
# up to n (inclusive), using the Sieve of Eratosthenes.
# See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def sieve(n):
isPrime = [ True ] * (n+1) # assume all are prime to start
isPrime[0] = isPrime[1] = False # except 0 and 1, of course
primes = [ ]
for prime in range(n+1):
if (isPrime[prime] == True):
# we found a prime, so add it to our result
primes.append(prime)
# and mark all its multiples as not prime
for multiple in range(2*prime, n+1, prime):
isPrime[multiple] = False
return primes
print(sieve(100))
- The Prime Counting Function
# Sieve of Eratosthenes
# More complete example, showing one reason why we might
# care to use the sieve rather than the simple isPrime function
# we already learned how to write.
# We'll be computing the prime counting function, pi(n):
# See http://en.wikipedia.org/wiki/Prime-counting_function
# We'll do it two different ways: once using the simple isPrime
# function, and again using the sieve. We'll time each way
# and see how it goes.
####################################################
###################
## sieve(n)
###################
# This function returns a list of prime numbers
# up to n (inclusive), using the Sieve of Eratosthenes.
# See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def sieve(n):
isPrime = [ True ] * (n+1) # assume all are prime to start
isPrime[0] = isPrime[1] = False # except 0 and 1, of course
primes = [ ]
for prime in range(n+1):
if (isPrime[prime] == True):
# we found a prime, so add it to our result
primes.append(prime)
# and mark all its multiples as not prime
for multiple in range(2*prime, n+1, prime):
isPrime[multiple] = False
return primes
# Here we will use the sieve to compute the prime
# counting function. The sieve will return a list
# of all the primes up to n, so the prime counting
# function merely returns the length of this list!
def piUsingSieve(n):
return len(sieve(n))
###################
## piUsingisPrime(n)
###################
# Here we will use the isPrime function to compute
# the prime counting function.
def piUsingIsPrime(n):
primeCount = 0
for counter in range(n+1):
if (isPrime(counter)):
primeCount += 1
return primeCount
def isPrime(n):
if (n < 2): return False
if (n == 2): return True
if (n % 2 == 0): return False
for factor in range(3, 1+int(round(n**0.5)), 2):
if (n % factor == 0):
return False
return True
####################################################
###################
## test code
###################
# Before running the timing code below, let's run
# some test code to verify that the functions above
# seemingly work. Test values are from:
# http://en.wikipedia.org/wiki/Prime-counting_function
def testCorrectness():
print("First testing functions for correctness...", end="")
assert(piUsingSieve(10) == 4)
assert(piUsingIsPrime(10) == 4)
assert(piUsingSieve(100) == 25)
assert(piUsingIsPrime(100) == 25)
assert(piUsingSieve(1000) == 168)
assert(piUsingIsPrime(1000) == 168)
print("Passed!")
testCorrectness()
####################################################
###################
## timing code
###################
# Finally we can time each version for a large value of n
# and compare their runtimes
import time
def testTiming():
n = 1000 # Use 1000 for Brython, 1000*1000 for Python
print("***************")
print("Timing piUsingIsPrime(" + str(n) + "):")
startTime = time.time()
result1 = piUsingIsPrime(n)
endTime = time.time()
time1 = endTime - startTime
print(" result = " + str(result1))
print(" time = " + str(time1) + " sec")
print("***************")
print("Timing piUsingSieve(" + str(n) + "):")
startTime = time.time()
result2 = piUsingSieve(n)
endTime = time.time()
time2 = endTime - startTime
print(" result = " + str(result2))
print(" time = " + str(time2) + " sec")
print("***************")
print("Comparison:")
print(" Same result: " + str(result1 == result2))
print(" (time of isPrime) / (time of sieve) = " + str(time1 / time2))
print("And this only gets worse, and quickly, for larger values of n.")
testTiming()