15-110 PRINCIPLES OF COMPUTING – S19

LECTURE 6:
LISTS AND TUPLES DATA STRUCTURES
TEACHER:
GIANNI A. DI CARO
Tuple and Lists: Generalization and extension of strings
§ String: (non-scalar type) ordered sequence of characters, immutable

H e l l o J o e
§ Indexing: access (read) individual characters
0 1 2 3 4 5 6 7 8
s =“Hello Joe”
print(s[0], s[4], s[-2])
H e l l o J o e § Slicing, Striding: access subsequences of characters
-9 -8 -7 -6 -5 -4 -3 -2 -1 s =“Hello Joe”
print(s[0:3], s[2:4], s[0::2], s[::-1])
§ Immutable: cannot change its value(s) § Concatenation (+ operator), Duplication (* operator)
s =“Hello Joe”
s[3] = ’L’ X s =“Hello Joe”
ü
s[1:4] = ‘abc’ Not allowed s = “New hello” Generalization of strings

§ Tuple: (non-scalar type) ordered sequence of objects (any type, not need same type), immutable

§ List: (non-scalar type) ordered sequence of objects (any type, not need same type), mutable
2
Tuple type
§ Tuple: (non-scalar type) ordered sequence of objects (any type, not need same type), immutable

§ Purpose: group items together in the same (immutable) object

§ Syntax: (a,b,c, …, )
Ø Examples of tuple variables assigned with tuple literals
prime_numbers = (1, 3, 5, 7, 11)
irrational_numbers = (2.71828, 3.14159, 1.41421)
fruits = (‘apple’, ‘pear’, ‘banana’, ‘orange’)
colors = (‘red’, ‘blue’, green’)
person_info = (‘Donald’, ‘Trump’, 14, ‘June’, 1946, ‘President’)
fruit_info = (‘melon’, 3.6, ‘yellow’, 12.5)
logical_values = (True, False, True, 255)
empty_sequence = ()
one_element_sequence = (5, ) → one_integer_var = (5) 3
Tuple type
§ Syntax: (a,b,c, …, )
§ … but also any comma-separated sequence of objects: a, b, c, d

prime_numbers = 1, 3, 5, 7, 11
irrational_numbers = 2.71828, 3.14159, 1.41421
fruits = ‘apple’, ‘pear’, ‘banana’, ‘orange’
colors = ‘red’, ‘blue’, green’
person_info = ‘Donald’, ‘Trump’, 14, ‘June’, 1946, ‘President’
fruit_info = ‘melon’, 3.6, ‘yellow’, 12.5
logical_values = True, False, True, 255
one_element_sequence = 5,

a,b,c = 1,3,6. → three variables of int type

a = 1,3,6 → one variable of tuple type
4
List type
§ List: (non-scalar type) ordered sequence of objects (any type, not need same type), mutable
§ Purpose: group items together in the same (mutable) object
§ Syntax: [a,b,c, …, ]
Ø Examples of list variables assigned with list literals
prime_numbers = [1, 3, 5, 7, 11]
irrational_numbers = [2.71828, 3.14159, 1.41421]
fruits = [‘apple’, ‘pear’, ‘banana’, ‘orange’]
colors = [‘red’, ‘blue’, green’]
person_info = [‘Donald’, ‘Trump’, 14, ‘June’, 1946, ‘President’]
fruit_info = [‘melon’, 3.6, ‘yellow’, 12.5]
logical_values = [True, False, True, 255]
empty_list = []
one_element_list = [5] or one_element_list = [5,]
list_of_lists = [1, ‘sedan’, [‘Toyota’, ‘Corolla’, 1.8, 2012], 52000] 5
List and tuples: fundamental data structures in python
§ Data structure: Container used to to store data (information) in a specific organized form, a layout
§ A given layout determines a data structure to be efficient in some operations and/or effective in the
representation of parts of information, and maybe inefficient / ineffective in others
§ E.g., the layout affects how we access access / find / change / add / remove / sort/organize data

6
List and tuples data structures: basic operations
§ Data structure: Container used to to store data (information) in a specific organized form, a layout
§ List/tuple layout is linear: based on a sequential arrangement of the data → position indexes

§ Access (read) operations, at any position, for both lists and tuples:
Ø get data by index (in 2 steps time)
Ø find data by content (linear number steps for scanning the list, depending on item’s position)

List/tuple items

Position index
0 1 2 3 4 5 6 7

7
List data structures: basic operations
§ Update operations, at any position, only for lists:
Ø change the value of an item
Ø remove one item
Ø add a new item anywhere (at the end, at the beginning, in between)

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6

0 1 2 3 4 5 6
0 1 2 3 4 5 6 8
Other data structures in python (building on lists)

9
Accessing tuple / list values: [], [:], [::]
§ Syntax: the same used for strings
Ø Single tuple/list element: [index]
Ø Subsequence of the tuple/list: [start : end]
Ø Subsequence with a stride: [start : end : step]
tuple list

prime_numbers = (1, 3, 5, 7, 11) or prime_numbers = [1, 3, 5, 7, 11]

x = prime_numbers[0] → x is of type int and has value 1
x = prime_numbers[2] → x is of type int and has value 5
x = prime_numbers[-3] → x is of type int and has value 5
x = prime_numbers[1:3] → x is of type tuple/list and has value (3,5)
corresponding to the tuple/list elements of index 1 and 2
x = prime_numbers[1:4:2] → x is of type tuple/list and has value (3,7)
corresponding to the tuple/list elements of index 1 and 3
10
Accessing tuple/list values that are inside tuples/lists
cars = [1, ‘sedan’, [‘Toyota’, ‘Corolla’, 1.8, 2012], 52000]

list
§ How do we access the item Corolla in the list variable cars? model = cars[2][1]

Equivalent to: list list[1]

model = (cars[2])[1] [‘Toyota’, ‘Corolla’, 1.8, 2012]
‘Corolla’

§ How do we access to the 4rd character in the model variable? (of type str)

Equivalent to: model3 = cars[2][1][3]

model = ((cars[2])[1])[3]
list list[1] list[1][3]
[‘Toyota’, ‘Corolla’, 1.8, 2012]
‘Corolla’
‘o’
11
Updating tuple values: No!
§ Updating tuple values: No! tuples are immutable types, like strings
§ Invalid operations:
prime_numbers = (1, 3, 5, 7, 11)
prime_numbers[4] = 13 → an existing element cannot be modified
prime_numbers[5] = 13 → it cannot be extended to an additional element

§ “Update” the tuple by creating a new tuple from the existing one
prime_numbers = (1, 3, 5, 7, 11)
new_prime_numbers = (1, 3, 5, 7, 13)
new_prime_numbers = prime_numbers[0:4] + (13, )
new_prime_numbers = prime_numbers + (13, 17)

12
Updating list values: [], [:], [::]
§ Updating list values: yes, they are mutable types, syntax is L[index] = new_value

colors = [‘red’, ‘green’, ‘blue’, ‘cyan’]

colors[1] = ‘yellow’ → same colors list, with modified value, ‘yellow’, for item in position 1
colors[0] = None → same colors list, with modified value and type, None, for item in position 0

colors[4] = ‘purple’ → error! the list doesn’t include an item at position 4 and the list cannot be
extended in this way

numbers = [] → defines an empty list, numbers[0] does not exist (yet)!

numbers[1] → error! the list doesn’t include an item at position 1 and the list cannot be extended in this way

colors[0:3] = (‘brown’, ‘magenta’, ‘pink’) → updating a subsequence of adjacent items

colors[0:3:2] = (‘brown’, ‘magenta’) → updating a subsequence of non-adjacent items
13
Mutable vs. Immutable types: int
1. In the high-level program: x 3
x = 2 meaning that variable x has (int) value 2
§ Internal to pyhton / computer: 2
variable x holds the reference (the address) to the memory
location to where its value 2 is currently stored (the reference
is associated to the identity id() of the variable)
print( id(x) )

2. Next instruction in the high-level program:

x = 3 meaning that variable x has changed its (int) value to 3

§ Internal to pyhton / computer:

variable x is of immutable type int, meaning that its value in memory cannot
be changed → A new memory location is allocated to hold the integer literal 3.
x now holds the reference to the new memory location (check id(x)!)
14
Mutable vs. Immutable types: int
3. Next instruction in the high-level program: x 3
y = x meaning that variable y gets the y 2
same value of x, and vice versa!
5
§ Internal to pyhton / computer:
variable y gets the reference held by x, y and x are
bound to the same memory location for their value

§ int is an immutable type, such that any further change in the values of either x or y brakes their
bound, creating a new variable
4. Next instruction in the high-level program: § Internal to pyhton / computer:
variable x gets the new reference associate to 5’s
x = 5 meaning that variable x now gets a
new value, which is allocated to a new, memory location
different memory location
15
Mutable vs. Immutable types: list
1. In the high-level program:
x
x = [1,2] meaning that list x has value [1,2]
[1,2]
§ Internal to pyhton / computer:
variable x holds the reference (address) to the memory
location to where the list values are stored (head of the list)

2. Next instruction in the high-level program:

x[0] = 3 meaning that the value at index 0 has changed to 3
x
§ Internal to pyhton / computer: [3,2]
variable x is of mutable type list, meaning that its values
in memory can be changed → The value at the memory
location holding x[0] is updated with the value 3.
x holds the same reference as prior this instruction

16
Mutable vs. Immutable types: list
3. Next instruction in the high-level program: x
[3,2]
y = x meaning that list variable y gets y
the same value of x, and vice versa!

§ Internal to pyhton / computer:

variable y gets the reference held by x, y and x are
bound to the same memory location for their value
x
[3,5]
§ list is a mutable type, such that any further y
change in the values of either x or y will be
reflected in the other list because of their bound

4. Next instruction in the high-level program:

§ Internal to pyhton / computer:
x[1] = 5 meaning that variable x the memory location referenced by both x and y gets
updates to 5 its value at index 1 updated in value à both x and y now have value [3,5]
17
Cloning vs. Aliasing: Issues and opportunities of mutability

§ What about initializing a list with § What about initializing a list with the
another list? contents of another list using a range?
primes = [1, 3, 5, 7] primes = [1, 3, 5, 7]
numbers = primes numbers = primes[0:3]

primes[1] = 29 primes[1] = 29

what about numbers? what about numbers?

print(“Do the lists have the same contents?”, numbers == primes)

print(“Primes:”, primes)
print(“Numbers:”, numbers)
print(“Are the two lists the ‘same’ list?”, id(primes) == id(numbers))

18
Cloning vs. Aliasing: Issues and opportunities of mutability
Two different ways of copying between data variables ( transfer data from one variable to another)
primes = [1, 3, 5, 7]
numbers = primes primes
Variables are passed by identity, 1 3 5 7
by reference address à Aliasing 0 1 2 3

Ø numbers and primes are alias for the numbers

same mutable list in memory!
ü numbers[1] = 29 has the same
effects than primes[1]=29 primes

primes = [1, 3, 5, 7] 1 3 5 7 1 3 5

numbers = primes[0:3] 0 1 2 3 Slicing 0 1 2

Slicing extracts content from one list, makes a copy of it, Pay attention to statements resulting
and pass it to the receiving list à Cloning, shallow copy in cloning vs. aliasing!
19
Cloning vs. Aliasing: Issues and opportunities of mutability

§ Previous reasoning apply also when we create list of lists:

p = [1, 3, 5, 7]
pp = [11, 13, 17]
n = [p, pp]

Any (in-place) change to either p or pp is reflected on n, and vice versa

20
Cloning vs. Aliasing: Issues and opportunities of mutability

What about the following piece of code with int variables?

p = 1
n = p
print(n, p, id(n), id(p))
p = 29
print(p, n)
n = -1
print(p, n)

int (float, bool, str) variables are immutable: we don’t update the content at
the same memory location, every time a change is made, a new memory variable (memory
location) is potentially generated, that potentially has a new identity
21