Data Structures

Data structures are basically just that - they are structures which can hold some data together. In other words, they are used to store a collection of related data.

There are four built-in data structures in Python - list, tuple, dictionary and set. We will see how to use each of them and how they make life easier for us.

List

A list is a data structure that holds an ordered collection of items i.e. you can store a sequence of items in a list. Like a string, a list is a sequence of values. In a string, the values are characters; in a list, they can be any type.

This is easy to imagine if you can think of a shopping list where you have a list of items to buy, except that you probably have each item on a separate line in your shopping list whereas in Python you put commas in between them.

# This is my shopping list
      shoplist = ['apple', 'mango', 
'carrot', 'banana']

The list of items should be enclosed in square brackets [ and ] so that Python understands that you are specifying a list. Once you have created a list, you can add, remove or search for items in the list. Since we can add and remove items, we say that a list is a mutable data type - in other words this type can be modified.

The values in list are called elements or sometimes items.

There are several ways to create a new list; the simplest is to enclose the elements in square brackets ([ and ]):

list_1 = [10, 20, 30, 40]
    
  list_2 = ['crunchy frog', 'ram bladder', 'lark vomit']

The first example (list_1) is a list of four integers. The second (list_2) is a list of three strings.

Another way to create a new list is to use the built-in list() function:

Code	Output
`list_3 = list() print(list_3)`	`[]`

The list function without arguments will create an empty list. You can also pass in a single object to be converted into a list:

Code	Output
`list_4 = list(range(3)) print(list_4)`	`[0, 1, 2]`

The syntax for accessing the elements of a list is the same as for accessing the characters of a string—the bracket operator. The expression inside the brackets specifies the index. Remember that the indices start at 0:

Code	Output
`cheeses = ['Cheddar', 'Edam', 'Gouda'] print(cheeses[0])`	`Cheddar`

The elements of a list don't have to be the same type. The following list contains a string, a float, an integer, and (lo!) another list:

['spam', 2.0, 5, [10, 20]]

A list within another list is nested.

When you want to access an element within a nested list, you need to use multiple indices. Look at this example:

my_bills = [["electric", 50], 
["gas", 60], ["cell", 60]]

my_bills[0] references the first element in the list. The first element is another list ["electric", 50].

To get the name of the individual bill ("electric") we need the first element of the first element of the my_bills list. We reference it like this:

Code	Output
`my_bills[0][0]`	`electric`

To get the dollar amount, we need the second element of the first element of the my_bills list:

Code	Output
`my_bills[0][1]`	`50`

A list that contains no elements is called an empty list; you can create one with just a pair of empty brackets, [].

As you might expect, you can assign list values to variables:

Code	Output
`cheeses = ['Cheddar', 'Edam', 'Gouda'] numbers = [17, 123] empty = [] print(cheeses, numbers, empty)`	`['Cheddar', 'Edam', 'Gouda'] [17, 123] []`

Lists are Mutable

Unlike strings, lists are mutable because you can change the order of items in a list or reassign an item in a list. When the bracket operator appears on the left side of an assignment, it identifies the element of the list that will be assigned.

Code	Output
`numbers = [17, 123] numbers[1] = 5 print(numbers)`	`[17, 5]`

The one-eth element of numbers, which used to be 123, is now 5.

You can think of a list as a relationship between indices and elements. This relationship is called a mapping; each index "maps to" one of the elements.

Index	Map
`0`	`17`
`1`	`5`

List indices work the same way as string indices:

Any integer expression can be used as an index.
If you try to read or write an element that does not exist, you get an IndexError.
If an index has a negative value, it counts backward from the end of the list.

Lists and Functions

There are a number of built-in functions that can be used on lists that allow you to quickly look through a list without writing your own loops:

Given:

numbers = [3, 41, 12, 9, 74, 15]

Function	Description	Example Code	Example Output
`len()`	Return the length of a list	`len(numbers)`	`6`
`max()`	Return the maximum value in the list	`max(numbers)`	`74`
`min()`	Return the smallest value in the list	`min(numbers)`	`3`
`sum()`	Return the sum of all the elements in a list	`sum(numbers)`	`154`

The sum function only works when the list elements are numbers. The other functions (len, max, and min) work with lists of strings and other types that can be comparable. The min and max functions look at the ASCII values of the characters which make up the string – just like with the comparison operators.

cheeses = ['Cheddar', 'Edam', 'Gouda']

Code	Result
`len(cheeses)`	`3`
`max(cheeses)`	`Gouda`
`min(cheeses)`	`Cheddar`
`sum(cheeses)`	`TypeError: unsupported operand type(s) for +: 'int' and 'str'`

Although a list can contain another list, the nested list still counts as a single element. The length of this list is four:

my_list = ['spam', 1, 
['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]

Our elements are:

Index	Code
`0`	`'spam'`
`1`	`1`
`2`	`['Brie', 'Roquefort', 'Pol le Veq']`
`3`	`[1, 2, 3]`

Traversing a List

The most common way to traverse the elements of a list is with a for loop. The syntax is the same as for strings:

cheeses = 
['Cheddar', 'Edam', 'Gouda']

Code	Output
`for cheese in cheeses: print(cheese)`	`Cheddar Edam Gouda`

Notice that the variable cheese contains the value of that element in the list.

Using a for loop like this works well if you only need to read the elements of the list. But if you want to write or update the elements, you need the indices. A common way to do that is to combine the functions range and len:

for i in 
range(len(cheeses)):
          cheeses[i] = 
cheese[i]*2

Note that in this version, the variable i is an integer and displaying cheeses[i] will then display the value of that element in the list.

This loop traverses the list and updates each element. len returns the number of elements in the list. range returns a list of indices from 0 to n-1, where n is the length of the list. Each time through the loop, i gets the index of the next element. The assignment statement in the body uses i to read the old value of the element and to assign the new value.

A for loop over an empty list never executes the body:

for x in empty:
          print('This 
never happens.')

List Operations

The + operator concatenates lists:

Code	Output
`a = [1, 2, 3] b = [4, 5, 6] c = a+b print(c)`	`[1, 2, 3, 4, 5, 6]`

Similarly, the * operator repeats a list a given number of times:

Code	Result
`[0]*4`	`[0, 0, 0, 0]`
`[1, 2, 3]*3`	`[1, 2, 3, 1, 2, 3, 1, 2, 3]`

The first example repeats [0] four times. The second example repeats the list [1, 2, 3] three times.

The in operator also works on lists.

cheeses = 
['Cheddar', 'Edam', 'Gouda']

Code	Output
`'Edam' in cheeses`	`True`
`'Brie' in cheeses`	`False`

List Slices

The slice operator also works on lists:

Code	Result
`t = ['a', 'b', 'c', 'd', 'e', 'f'] t[1:3]`	`['b', 'c']`
`t[:4]`	`['a', 'b', 'c', 'd']`
`t[3:]`	`['d', 'e', 'f']`
`t[:]`	`['a', 'b', 'c', 'd', 'e', 'f']`

If you omit the first index, the slice starts at the beginning. If you omit the second, the slice goes to the end. So if you omit both, the slice is a copy of the whole list.

An important note: strings are immutable, so any manipulation of strings did not affect the original string. Lists are mutable so manipulations will change the list. Since lists are mutable, it is often useful to make a copy before performing operations that fold, spindle, or mutilate lists.

A slice operator on the left side of an assignment can update multiple elements:

Code	Output
`t = ['a', 'b', 'c', 'd', 'e', 'f'] t[1:3] = ['x', 'y'] print(t)`	`['a', 'x', 'y', 'd', 'e', 'f']`

List Methods

Python provides methods that operate on lists. For example, append adds a new element to the end of a list:

Code	Output
`t = ['a', 'b', 'c'] t.append('d') print(t)`	`['a', 'b', 'c', 'd']`

Extend

extend takes a list as an argument and appends all of the elements:

Code	Output
`t1 = ['a', 'b', 'c'] t2 = ['d', 'e'] t1.extend(t2) print(t1)`	`['a', 'b', 'c', 'd', 'e']`

This example leaves t2 unmodified.

Sort

sort arranges the elements of the list from low to high:

Code	Output
`t = ['d', 'c', 'e', 'b', 'a'] t.sort() print(t)`	`['a', 'b', 'c', 'd', 'e']`

Most list methods are void; they modify the list and return None. If you accidentally write t = t.sort(), you will be disappointed with the result.

The sort method sorts in ascending order by default. That is, from A-Z. You can perform a sort from Z-A using the optional argument reverse within the sort method:

Code	Output
`t = ['d', 'c', 'e', 'b', 'a'] t.sort(reverse=True) print(t)`	`['e', 'd', 'c', 'b', 'a']`

Reverse

If you need to reverse the indices in the list (make the last element the first, make the second-to-last-element the second, etc), you can use the reverse method:

Code	Output
`t = ['d', 'c', 'e', 'b', 'a'] t.reverse() print(t)`	`['a', 'b', 'e', 'c', 'd']`

Deleting Elements

There are several ways to delete elements from a list.

Pop

If you know the index of the element you want, you can use pop:

Code	Output
`t = ['a', 'b', 'c', 'd', 'e'] x = t.pop(1) print(t)`	`['a', 'c', 'd', 'e']`
`print(x)`	`B`

pop modifies the list and returns the element that was removed. If you don't provide an index, it deletes and returns the last element.

Remove

If you know the element you want to remove (but not the index), you can use remove:

Code	Output
`t = ['a', 'b', 'c', 'd', 'e'] t.remove('b') print(t)`	`['a', 'c', 'd', 'e']`

The return value from remove is None.

Del

If you don't need the removed value, you can use the del operator:

Code	Output
`t = ['a', 'b', 'c', 'd', 'e'] del t[1] print(t)`	`['a', 'c', 'd', 'e']`

To remove more than one element, you can use del with a slice index:

Code	Output
`t = ['a', 'b', 'c', 'd', 'e'] del t[1:4] print(t)`	`['a', 'e']`

As usual, the slice selects all the elements up to, but not including, the second index.

Lesson 6: Lists, Dictionaries, and Tuples