data structures – review (class slides)

CSc 110 - Data Structures

Data Structures in Python

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

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()

Evaluate the code

Indicate 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 # evaluate what this list holds at this point

my_list[6] = 10

my_tupple = (3, 4, 1)
my_tupple.append(3)
my_tupple # evaluate what this tuple holds at this point

my_dictionary = {3: 4, 1: 2, 5: 4}
my_dictionary[5] = 10
my_dictionary # evaluate what this dictionary holds at this point

my_dictionary.append(4: 5)
my_dictionary # evaluate what this dictionary holds at this point

Evaluate the code

Indicate 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 # evaluate what this list holds at this point
[1, 2, 3, 4, 2, 3]
# error --- my_list[6] = 10

my_tupple = (3, 4, 1)
# error --- my_tupple.append(3)
my_tupple # evaluate what this tuple holds at this point
(3, 4, 1)
my_dictionary = {3: 4, 1: 2, 5: 4}
my_dictionary[5] = 10
my_dictionary # evaluate what this dictionary holds at this point
{3: 4, 1: 2, 5: 10}
# error --- my_dictionary.append(4: 5)
my_dictionary # evaluate what this dictionary holds at this point
{3: 4, 1: 2, 5: 10}

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

Cannot change size of data structure

It is not possible to remove or add items to a list or a dictionary inside a for x in data_structure loop. This is what happens when you try to do so:

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 of data structure

It is not possible to remove or add items to a list or a dictionary inside a for x in data_structure loop. This is what happens when you try to do so:

Error:

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

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 list for this
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:
      name_list.append(name)
  f.close()
  return len(name_list)

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

Submit code for attendance

Submit your count_names functions to Gradescope for attendance.

Name your file names.py

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 functionn – 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:
      name_dict[name] = ""
  f.close()
  return len(name_dict)

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