data structures – review (slides)

CSc 110 - Data Structures

Data Structures in Python

• lists (mutable)
• dictionaries (mutable)
• tuples (immutable)

A comparison - fill in the missing cells

use i to represent index, v to represent value:

Method	List	Dictionary	Tuple
Create	my_l = []		my_t = ()
Retrieve	my_l[i]	my_d[k]
Update
Add		my_d[k] = v
Delete	my_l.pop(i) my_l.remove(v)

A comparison

Other ways for update: my_l[i] += v, my_d[i] += v

Method	List	Dictionary	Tuple
Create	my_l = []	my_d = {}	my_t = ()
Retrieve	my_l[i]	my_d[k]	my_t[i]
Update	my_l[i] = v	my_d[k] = v	-
Add	my_l.insert(i, v) my_l.append(v)	my_d[k] = v	-
Delete	my_l.pop(i) my_l.remove(v)	my_d.pop(k)	-

Lists

• store:
  • ordered items
  • elements of different types
• use square brackets ([]) syntax for creating a list
• allow indexing (integers starting at 0) with square brackets ([]) as well
• are mutable

Lists

Indexing to retrieve values:

my_list = ["a", 1, "b", 2]
my_list[0]

'a'

Indexing to mutate values:

my_list[0] = 5
my_list

[5, 1, 'b', 2]

List methods

• .append(value)
• .insert(index, value)
• .pop(index)
• .remove(value)

Tuples

• store:
  • ordered items
  • elements of different types
• use parentheses (()) syntax for creating a tuple
• allow indexing (integers starting at 0) with square brackets ([])
• are immutable

Tuples

Indexing to retrieve values:

my_tuple = ("a", 1, "b", 2)
my_tuple[0]

'a'

Not possible to mutate/change values in tuples

No methods to change it (because tuples are immutable)

Dictionaries

• store pairs of items key: value
• use curly brackets ({}) with key and value separated by colon (:)
• allow value retrieval through key with square brackets ([])
• are mutable

Dictionaries

Use key to retrieve values:

my_dict = {"banana": 10, "apple": 3, "orange": 40}
my_dict["banana"]

10

Use key to add key: value pairs:

my_dict["pear"] = 5
my_dict

{'banana': 10, 'apple': 3, 'orange': 40, 'pear': 5}

Use key to mutate value associated with key:

my_dict["pear"] += 5
my_dict

{'banana': 10, 'apple': 3, 'orange': 40, 'pear': 10}

Dictionary methods

• .values()
• .items()
• .pop()

Submit attendance - part one

Write ERROR when errors are thrown.

my_list = [2, 3, 1, 2]
my_list.append(3)
my_list.insert(0, 1)
my_list[3] = 4
my_list[2] # evaluate

my_tuple = (3, 4, 1)
my_tuple.append(3) # evaluate

my_dictionary = {3: 4, 1: 2, 5: 4}
my_dictionary[5] = 10
my_dictionary[5] + my_dictionary[1] # evaluate

my_dictionary.append(4: 5) # evaluate

Iterating over data structures

Use for x in data_structure to retrieve values/keys (cannot make changes with this type of loop)

my_list = [3, 5, 5]
for value in my_list:
  print(value)

3
5
5

my_tuple = (3, 5, 5)
for value in my_tuple:
  print(value)

3
5
5

Iterating over dictionaries

my_dictionary = {3: "a", 5: "b"}
for key in my_dictionary:
  print(key)

3
5

You can change values in a dictionary with for key in dictionary

my_dictionary = {"a": 2, "b": 3}
for key in my_dictionary:
  my_dictionary[key] += 1
my_dictionary

{'a': 3, 'b': 4}

Iterating over dictionaries

Use for x in data_structure.method() for dictionaries

my_dictionary = {3: "a", 5: "b"}
for value in my_dictionary.values():
  print(value)

a
b

my_dictionary = {3: "a", 5: "b"}
for key, value in my_dictionary.items():
  print(value)
  print(key)

a
3
b
5

Submit attendance - part two

1. Its name is count_names that opens in read mode a file that contains a name per line, with repeated names
2. It counts how many unique names there are in the file
3. It returns an integer with the count
4. Use a list for this

Name file names.py and submit your attendance - part two.

assert count_names("names.txt") == 11

Write a function – solution

def count_names(file_name):
  f = open(file_name, "r")
  name_list = []
  for line in f:
    name = line.strip()
    if name not in name_list and name != "":
      name_list.append(name)
  f.close()
  return len(name_list)

def main():
  assert count_names("names.txt") == 11
  
main()

Write a function

1. Its name is count_names
2. It opens in read mode a file that contains a name per line, with repeated names
3. It counts how many unique names there are in the file
4. It returns an integer with the count
5. Use a dictionary for this

assert count_names("names.txt") == 11

Write a function – solution

def count_names(file_name):
  f = open(file_name, "r")
  name_dict = {}
  for line in f:
    name = line.strip()
    if name not in name_dict and name != "":
      name_dict[name] = ""
  f.close()
  return len(name_dict)

def main():
  assert count_names("names.txt") == 11
  
main()

Submit attendance - part three

Go to Python Tutor, visualize the execution, and submit your attendance.

• Remove values using for x in list:

my_list = [2, 3, 1, 2]
for value in my_list:
  my_list.remove(value)

• Append values using for x in list:

my_list = [2, 3, 1, 2]
for value in my_list:
  my_list.append(value + 1) 

Cannot change size while iterating

It’s not possible to remove or add items to a list/dictionary inside a for x in data_structure loop:

Weird behavior:

my_list = [2, 3, 1, 2]
for value in my_list:
  my_list.remove(value)
my_list

[3, 2]

Infinite loop:

my_list = [2, 3, 1, 2]
for value in my_list:
  my_list.append(value + 1) # this causes an infinite loop

Cannot change size while iterating

It’s not possible to remove or add items to a list/dictionary inside a for x in data_structure loop:

Error:

my_dict = {2: 0, 3: 1, 1: 0}
for key in my_dict:
  my_dict.pop(key) # this causes an error