menu COMPSCI 2120/9642/DIGIHUM 2220 1.0 documentation

CS 2120: Topic 8

Videos for this week:

Data Structures

_images/lists.png
  • Data Structure = a particular structure which holds data

  • Your first data structure is a list

  • Lists, although simple, are one of the most useful and powerful of all data structures.

    Question

    How is a data structure different than a data type?

    A data type is a set of values with certain properties/operations (ex: int, char, boolean among others). A data structure is a collection of various types of data organized into a particular format (ex: lists which are in the form [a, b, c, d, …]).

What can we do with lists?

  • We can concatenate lists with the + operator:

    >>> a=[5,7,9,10]
    >>> b=['also','a','list']
    
    >>> a+b
    [5, 7, 9, 10, 'also', 'a', 'list']
    
  • We can concatenate a list with itself, multiple times, using the * operator:

    >>> a*3
    [5, 7, 9, 10, 5, 7, 9, 10, 5, 7, 9, 10]
    
  • We can slice lists:

    >>> a[0:2]
    [5,7]
    >>> a[1:3]
    [7,9]
    
  • We can find a list’s length:

    >>> len(a)
    4
    
  • We can check if something is in a list:

    >>> if 5 in a:
            print("yes, 5 is in a!!!")
    yes, 5 is in a!!!
    
  • We can go through each list entry:

    >>> for i in a:
          print(i)
    5
    7
    9
    10
    
  • We can create sequential lists with “range()”

    >>> list(range(1,5))
          [1, 2, 3, 4]
    
    >>> list(range(5,10))
          [5, 6, 7, 8, 9]
    

Mutability

  • Strings are kind of like a “list of characters”.. but recall that strings are immutable. What about lists?

  • Let’s try:

    >>> a=[5,7,9,10]
    >>> print(a)
    [5, 7, 9, 10]
    >>> a[2]='I changed!'
    >>> print(a)
    [5, 7, 'I changed!', 10]
    
  • Lists, unlike strings, are mutable.

  • A cleaner way to delete an element from a list is with the del statement:

    >>> a=[5,7,9,10]
    >>> a
    [5, 7, 9, 10]
    >>> del a[2]
    >>> a
    [5, 7, 10]
    

Aliasing

  • What is this code doing?
    >>> a=[1,2,3,4]
    >>> print(a)
    [1, 2, 3, 4]
    >>> b=a
    >>> b[2]='Z'
    >>> print(a)
    [1, 2, 'Z', 4]
    
  • You might imagine that b is a separate copy of a, so why does "Z" appear when you print a?

  • The code b=a creates an Alias for a called b; in other words, we are saying that "b" is another name for "a".

Warning

In Python, when you “assign” a list, you are not copying the list. You are saying ‘this is another name for the exact same list’.

  • If you want to copy your list, use slicing: b = a[:]. Slicing always creates a new list.

    >>> a=[1,2,3,4]
    >>> print(a)
    [1, 2, 3, 4]
    >>> b=a[:]
    >>> b[2]='Z'
    >>> print(a)
    [1, 2, 3, 4]
    

Looping through lists

  • Previously we used a for loop with in tp step through a list. for loops can also step through a list via an index (let’s call it i):

    >>> list=['a','b','c','d']
    
    >>> for i in range(len(list)):
          print(list[i])
    
    a
    b
    c
    d
    
  • Often we’ll want to print out the index with each list entry:

    >>> list=['a','b','c','d']
    
    >>> for i in range(len(list)):
          print(i, list[i])
    
    0 a
    1 b
    2 c
    3 d
    
  • This pattern is so common that Python has given us a built in function enumerate to do this:

    for i in enumerate(list):
            print i[0], i[1]
    
  • i[0] is the index of the item in the list

  • i[1] is the actual item itself

Using lists as parameters

  • When you pass a list as an argument in a function, that function is called a modifier and the changes it makes are called side effects

  • The function is not changing a copy of the list; rather, it is modifying the original (the list argument is an alias)

>>> def double(list):
      """ Double each element of list """
      for i in range(len(list)):
          list[i] = 2 * list[i]
>>> myList = [2, 5, 9]
>>> print(myList)
[2, 5, 9]
>>> double(myList)
>>> print(myList)
[4, 10, 18]

Side effects

  • Any function which modifies a parameter is said to have side effects

Pure functions

  • If a function has no side effects, we call it a pure function.

Nested lists

  • We can nest some number of lists inside other lists:

>>> listA = [a, b, c, d]
>>> listB = [1, 3, "horse"]
>>> listA.append(listB)
>>> print(listA)
[a, b, c, d, [1, 3, "horse"]]
  • We can continue to nest lists inside of lists inside of lists… and so on.

For next class