8 Lists¶
Topics¶
- list data structure
- syntax to create lists
- methods or operations provided to list objects
- list operators
- list traversal
- list applications and problems
8.1 Lists¶
- a type of sequence or container
- ordered collection of values called elements or items
- lists are similar to strings (ordered collections of characters) except that elements of a list can be of any type
8.2 Creating lists¶
- several ways; the simplest is to enclose the elements in square brackets [ ]
In [15]:
alist = [] # an empty list
In [16]:
blist = list() # an empty list
In [17]:
type(alist)
Out[17]:
list
In [18]:
# creating lists with some elements of same type
list1 = [10, 20, 30, 40]
list2 = ['spam', 'bungee', 'swallow']
In [6]:
# lists with elements of different types
list3 = ["hello", 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [20]:
# print list
print(list3)
['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [21]:
# quickly create a list of range of numbers between 1 and 19
list4 = list(range(1, 20, 1))
In [22]:
print(list4)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
In [23]:
# print multiple lists
print(alist, list1, list2, list3)
[] [10, 20, 30, 40] ['spam', 'bungee', 'swallow'] ['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [11]:
# Exercise: create a list of even numbers between 1 and 20 inclusive
In [12]:
# Exercise: create a list of odd numbers between 1 and 20 inclusive
In [13]:
# Exercise: create a list of numbers from 20 to 1 inclusive
8.3 Accessing elements¶
- same syntax for accessing characters of a string, the index operator: ['index']
In [14]:
# let's see what elements are in list1
list1
Out[14]:
[10, 20, 30, 40]
In [15]:
# access an element, which one?
list1[0]
Out[15]:
10
In [16]:
list3
Out[16]:
['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [17]:
list3[2-2]
Out[17]:
'hello'
In [18]:
# list index can be variable as well
index = 0
print(list3[index])
hello
In [19]:
# can you use float value as an index?
list3[1.0]
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-19-1fc6b2fe2f36> in <module>() 1 # can you use float value as an index? ----> 2 list3[1.0] TypeError: list indices must be integers or slices, not float
In [20]:
# how many elements are there in list3?
len(list3)
Out[20]:
5
In [21]:
# what happens if you access an index equal to the size of the list
list3[5]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-21-207cd7e1c880> in <module>() 1 # what happens if you access an index equal to the size of the list ----> 2 list3[5] IndexError: list index out of range
In [3]:
list3
Out[3]:
['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [24]:
# Exercise: access and print the last element of list3
In [4]:
# Can we use negative index?
# Can you guess the output of the following code?
print(list3[-1])
(1, 'uno')
In [32]:
# Exercise - access and print 'world' in list3
8.4 Membership¶
- checking if some data/object is a member/element in the given list
- in and not in boolean operators let's you check for membership
In [1]:
horsemen = ["war", "famine", "pestilence", ["death"]]
'death' in horsemen
Out[1]:
False
In [2]:
'War' not in horsemen
Out[2]:
True
In [3]:
["death"] in horsemen
Out[3]:
True
8.5 Traversing lists¶
- for or while loop can be used to traverse through each element of a list
In [29]:
list3
Out[29]:
['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [5]:
# common technique; use for loop
for item in list3:
print(item)
hello
2.0
10
[10, ('hi', 'world'), 3.5]
(1, 'uno')
In [6]:
for item in list3:
if isinstance(item, list) or isinstance(item, tuple):
for l in item:
print(l)
else:
print(item)
hello
2.0
10
10
('hi', 'world')
3.5
1
uno
In [8]:
horsemen = ["war", "famine", "pestilence", "death"]
for i in [0, 1, 2, 3]:
print(horsemen[i])
# better way to do the same thing?
war famine pestilence death
In [10]:
print("traversing using indices")
for i in range(len(horsemen)):
print(horsemen[i])
traversing using indices war famine pestilence death
In [11]:
print('traversing each element')
for ele in horsemen:
print(ele)
traversing each element war famine pestilence death
8.6 list operators¶
- + operator concatenates two lists and gives a bigger list
- * operator repeats a list elements a given number of times
In [24]:
list2
Out[24]:
['spam', 'bungee', 'swallow']
In [26]:
list3
Out[26]:
['hello', 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]
In [27]:
list4 = list2 + list3
In [28]:
list4
Out[28]:
['spam',
'bungee',
'swallow',
'hello',
2.0,
10,
[10, ('hi', 'world'), 3.5],
(1, 'uno')]
In [29]:
[0]*10
Out[29]:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
In [30]:
a = [1, 2, 3]*4
In [31]:
a
Out[31]:
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
In [32]:
b = [a]*3
In [33]:
b
Out[33]:
[[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3], [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3], [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]]
In [42]:
# 2-D list or matrix
matrix = [[1, 2], [3, 4], [5, 6]]
In [43]:
print(matrix)
[[1, 2], [3, 4], [5, 6]]
In [44]:
matrix
Out[44]:
[[1, 2], [3, 4], [5, 6]]
In [45]:
# How do you replace 5 with 50 in matrix?
matrix[2][0] = 50
In [46]:
matrix
Out[46]:
[[1, 2], [3, 4], [50, 6]]
8.7 Slicing lists¶
- all the slice operations that work with strings also work with lists
- syntax: [startIndex : endIndex : step]
- startIndex is inclusive; endIndex is exclusive; step is optional by default 1
In [36]:
# create a list of lower-case alphabets
alphas = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] # add the rest...
In [37]:
alphas
Out[37]:
['a', 'b', 'c', 'd', 'e', 'f', 'g']
In [38]:
# there's better way to create lists of all lowercase ascii
import string
alphas = list(string.ascii_lowercase)
In [39]:
print(alphas[:])
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [40]:
print(alphas[::3])
['a', 'd', 'g', 'j', 'm', 'p', 's', 'v', 'y']
In [41]:
print(alphas[1:3])
['b', 'c']
In [42]:
print(alphas[::-1])
['z', 'y', 'x', 'w', 'v', 'u', 't', 's', 'r', 'q', 'p', 'o', 'n', 'm', 'l', 'k', 'j', 'i', 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a']
8.8 Lists and strings¶
- match made in heaven - work together really well :)
In [44]:
# convert string to list of characters
alphaList = list(string.ascii_lowercase)
In [45]:
alphaList
Out[45]:
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [46]:
# convert list to string by joining pairs of chars with a delimiter
alphaStr = '|'.join(alphaList)
In [47]:
alphaStr
Out[47]:
'a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z'
8.9 lists are mutable¶
- we can change/replace/update list elements in place
In [48]:
names = ["john", "David", "Alice"]
names[0] = "jake"
In [49]:
names
Out[49]:
['jake', 'David', 'Alice']
In [50]:
# How to correct spelling of jake?
names[0][0]
Out[50]:
'j'
In [51]:
names[0][0] = 'J'
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-51-0442e9474c4b> in <module> ----> 1 names[0][0] = 'J' TypeError: 'str' object does not support item assignment
In [52]:
names[0] = 'Jake'
In [53]:
names
Out[53]:
['Jake', 'David', 'Alice']
In [54]:
alphas
Out[54]:
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [55]:
alphas[:4] = ['A', 'B', 'C', 'D']
In [56]:
alphas
Out[56]:
['A', 'B', 'C', 'D', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [57]:
alphas[:4] = []
In [58]:
alphas
Out[58]:
['e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
8.10 Deleting list elements¶
- del statement removes an element from a list given its index
In [59]:
alphas
Out[59]:
['e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [60]:
del alphas[0]
In [61]:
alphas
Out[61]:
['f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [62]:
del alphas[26]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-62-80e1a19bb44c> in <module> ----> 1 del alphas[26] IndexError: list assignment index out of range
In [63]:
alphas.index('z')
Out[63]:
20
In [64]:
alphas.index(alphas[-1])
Out[64]:
20
In [65]:
del alphas[1:3]
In [66]:
alphas
Out[66]:
['f', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
In [67]:
indexOfZ = alphas.index('z')
del alphas[indexOfZ]
In [68]:
print(alphas)
['f', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y']
8.11 Objects and references¶
- is operator can be used to test if two objects are referencing the same memory location
- meaning they're essentially the same object with the same values
In [78]:
# even though a and b are two separate objects is still evaluates to True
a = 'apple'
b = 'apple'
a is b
Out[78]:
True
In [69]:
# even though c and d are two separate objects is still evaluates to True
c = 10
d = 10
c is d
Out[69]:
True
In [73]:
# what abut tuple?
e = (1, 2)
f = (1, 2)
print(e == f)
print(e is f)
True False
In [79]:
# What about lists?
l1 = [1, 2, 3]
l2 = [1, 2, 3]
print(l1 == l2)
print(l1 is l2)
True False
8.12 Copying lists (Shallow copy vs Deep copy)¶
- see PythonTutor.com to visualize aliasing
- assignment = operator does shallow copy
In [80]:
a = [1, 2, 3]
b = a
print(a is b)
print(a == b)
True True
In [81]:
b[0] = 10
print(a)
print(b)
[10, 2, 3] [10, 2, 3]
In [82]:
# How do you actually clone lists - do a deep copy?
c = a[:] # easy way shallow copy
d = a.copy() # shallow copy
import copy
e = copy.deepcopy(b)
In [83]:
c is a
Out[83]:
False
In [84]:
d is a
Out[84]:
False
In [85]:
b is e
Out[85]:
False
8.13 List methods¶
- list objects have a bunch methods that can be invoked to work with list
- run help(list)
In [86]:
help(list)
Help on class list in module builtins: class list(object) | list(iterable=(), /) | | Built-in mutable sequence. | | If no argument is given, the constructor creates a new empty list. | The argument must be an iterable if specified. | | Methods defined here: | | __add__(self, value, /) | Return self+value. | | __contains__(self, key, /) | Return key in self. | | __delitem__(self, key, /) | Delete self[key]. | | __eq__(self, value, /) | Return self==value. | | __ge__(self, value, /) | Return self>=value. | | __getattribute__(self, name, /) | Return getattr(self, name). | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __gt__(self, value, /) | Return self>value. | | __iadd__(self, value, /) | Implement self+=value. | | __imul__(self, value, /) | Implement self*=value. | | __init__(self, /, *args, **kwargs) | Initialize self. See help(type(self)) for accurate signature. | | __iter__(self, /) | Implement iter(self). | | __le__(self, value, /) | Return self<=value. | | __len__(self, /) | Return len(self). | | __lt__(self, value, /) | Return self<value. | | __mul__(self, value, /) | Return self*value. | | __ne__(self, value, /) | Return self!=value. | | __repr__(self, /) | Return repr(self). | | __reversed__(self, /) | Return a reverse iterator over the list. | | __rmul__(self, value, /) | Return value*self. | | __setitem__(self, key, value, /) | Set self[key] to value. | | __sizeof__(self, /) | Return the size of the list in memory, in bytes. | | append(self, object, /) | Append object to the end of the list. | | clear(self, /) | Remove all items from list. | | copy(self, /) | Return a shallow copy of the list. | | count(self, value, /) | Return number of occurrences of value. | | extend(self, iterable, /) | Extend list by appending elements from the iterable. | | index(self, value, start=0, stop=9223372036854775807, /) | Return first index of value. | | Raises ValueError if the value is not present. | | insert(self, index, object, /) | Insert object before index. | | pop(self, index=-1, /) | Remove and return item at index (default last). | | Raises IndexError if list is empty or index is out of range. | | remove(self, value, /) | Remove first occurrence of value. | | Raises ValueError if the value is not present. | | reverse(self, /) | Reverse *IN PLACE*. | | sort(self, /, *, key=None, reverse=False) | Stable sort *IN PLACE*. | | ---------------------------------------------------------------------- | Static methods defined here: | | __new__(*args, **kwargs) from builtins.type | Create and return a new object. See help(type) for accurate signature. | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | __hash__ = None
In [87]:
a = []
a.append(1)
a.append(2)
a.append([2, 3])
In [88]:
a
Out[88]:
[1, 2, [2, 3]]
In [89]:
a.extend([3, 4])
In [90]:
a
Out[90]:
[1, 2, [2, 3], 3, 4]
In [91]:
a.append([5, 6])
In [92]:
a
Out[92]:
[1, 2, [2, 3], 3, 4, [5, 6]]
In [93]:
a.insert(0, 'hi')
In [94]:
a
Out[94]:
['hi', 1, 2, [2, 3], 3, 4, [5, 6]]
In [95]:
a.reverse()
In [96]:
a[0].reverse()
In [97]:
a
Out[97]:
[[6, 5], 4, 3, [2, 3], 2, 1, 'hi']
In [98]:
a.sort()
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-98-2ed0d7de6146> in <module>() ----> 1 a.sort() TypeError: '<' not supported between instances of 'int' and 'list'
In [99]:
blist = list(range(10, 0, -1))
In [100]:
blist
Out[100]:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
In [101]:
blist.sort()
In [102]:
print(blist)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In [103]:
blist.sort(reverse=True)
In [104]:
blist
Out[104]:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
In [105]:
m = max(blist)
mI = blist.index(m)
In [106]:
print(mI)
0
In [107]:
min(blist)
Out[107]:
1
In [108]:
print(blist.count(100))
0
In [4]:
nums = input('Enter 5 numbers separated by space: ')
Enter 5 numbers separated by space: 1 2 100 5
In [5]:
nums
Out[5]:
'1 2 100 5'
In [76]:
nums = nums.split(' ')
In [77]:
nums
Out[77]:
['1', '2', '100', '5']
In [78]:
intNums = []
for n in nums:
intN = int(n)
intNums.append(intN)
In [79]:
intNums
Out[79]:
[1, 2, 100, 5]
In [80]:
intNums.sort()
In [81]:
intNums
Out[81]:
[1, 2, 5, 100]
convert list of integers to string¶
In [94]:
' '.join(intNums)
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-94-0dd63a44d5ec> in <module> ----> 1 ' '.join(intNums) TypeError: sequence item 0: expected str instance, int found
In [99]:
strNum = []
for n in intNums:
strNum.append(str(n))
In [100]:
strNum
Out[100]:
['1', '2', '5', '100']
In [101]:
strNum = ' '.join(strNum)
In [102]:
strNum
Out[102]:
'1 2 5 100'
8.15 Passing list to function - pass-by-reference¶
- mutable types such as list are passed-by-reference
- an alias or reference is passed instead of a copy of the data
In [84]:
def getData(someList):# someList is formal parameter
for i in range(5):
a = int(input('enter a number: '))
someList.append(a)
In [85]:
alist = []
getData(alist) # alist is actual argument
enter a number: 1 enter a number: 10 enter a number: 4 enter a number: 6 enter a number: 90
In [86]:
# when formal parameter is updated, actual parameter is also updated
alist
[1, 10, 4, 6, 90]
8.16 return list from functions¶
- lists can be returned from functions
In [121]:
def getMaxMin(alist):
m = max(alist)
minVal = min(alist)
return [m, minVal]
In [122]:
alist = list(range(-1000, 2000000))
print(getMaxMin(alist))
[1999999, -1000]
In [123]:
assert getMaxMin(alist) == [1999999, -1000]
8.17 Casting list into tuple and back¶
- since tuples are immutable it may be benefitial to cast them into lists and update
- can convert list back to tuple again
In [88]:
atuple = (1, 2, 3)
alist = list(atuple)
print(alist)
[1, 2, 3]
In [89]:
btuple = tuple(alist)
In [90]:
print(btuple)
(1, 2, 3)
In [91]:
atuple == btuple
Out[91]:
True
In [93]:
# eventhough the elements are equal; the types of two objects are not
print(atuple, alist)
print(atuple == alist)
(1, 2, 3) [1, 2, 3] False
8.18 Exercises¶
- Practice with the rest of the methods of list
- Draw memory state snapshot for a and b after the following Python code is executed:
a = [1, 2, 3]
b = a[:]
b[0] = 5
- Lists can be used to represent mathematical vectors. Write a function
add_vectors(u, v)that takes two lists of numbers of the same length, and returns a new list containing the sums of the corresponding elements of each. The following test cases must pass once the add_vectors is complete.
In [124]:
def add_vectors(a, b):
pass
In [125]:
# test cases
assert add_vectors([1, 1], [1, 1]) == [2, 2], 'vectors not added correctly'
assert add_vectors([1, 2], [1, 4]) == [2, 6], 'vectors not added correctly'
assert add_vectors([1, 2, 1], [1, 4, 3]) == [2, 6, 4], 'vectors not added correctly'
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-125-f13d12d55331> in <module>() 1 # test cases ----> 2 assert add_vectors([1, 1], [1, 1]) == [2, 2], 'vectors not added correctly' 3 assert add_vectors([1, 2], [1, 4]) == [2, 6], 'vectors not added correctly' 4 assert add_vectors([1, 2, 1], [1, 4, 3]) == [2, 6, 4], 'vectors not added correctly' AssertionError: vectors not added correctly
Kattis problems¶
- the following Kattis problems can be solved using list
- Dice Game - https://open.kattis.com/problems/dicegame
- Height Ordering - https://open.kattis.com/problems/height
- What does the fox say? - https://open.kattis.com/problems/whatdoesthefoxsay
- Army Strength (Easy) - https://open.kattis.com/problems/armystrengtheasy
- Army Strength (Hard) - https://open.kattis.com/problems/armystrengthhard
- Black Friday - https://open.kattis.com/problems/blackfriday
List sorting with two keys¶
- Roll Call - https://open.kattis.com/problems/rollcall
- Cooking Water - https://open.kattis.com/problems/cookingwater
In [ ]: