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, and have particular methods to retrieve or manipulate 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 overview: List is one of the simplest and most important data structures in Python.
Lists are collections of items where each item in the list has an assigned index value.
A list is mutable, meaning you can change its contents.
Lists are very flexible and have many built-in control functions.
List
List overview: List is one of the simplest and most important data structures in Python.
Lists are collections of ordered items, each item in the list has an assigned index value.
the items in a list are called 'elements', they don't need to be the same data type, these items can even be a list itself!
List items are enclosed in square brackets [ ] and each item is separated by a comma ','
A list is mutable, means you can change its contents.
Lists are very flexible and have many built-in control functions and methods you can use to manipulate lists.
7.1 Make a list
First, see some examples of lists:
Ex. 7.1-1 some_lsts.py
# some_lsts.py
>>> numbers =[1, 3, 5, 7]
>>> eye_color = [ 'blue', 'brown', 'black', 'green']
>>> address = [ 'Flying Circus Community', 18008,
'26th street', 01969, 'Python City']
>>> lsts_list = [ [1, 2, 3], ['x', 'y', 'z'],
['red', 'green', 'yellow'] ]
>>> empty_lst = []
>>> vegetables = ['spinach', 'brocali', 'cabbage', 'onion']
>>> vegetables # run this and see result
['spinach', 'broccoli', 'cabbage', 'onion']
>>>
Save your fingers from over typing if you need a list with a thousand numbers.
Use range( ) function to generate a list of numbers.
Remember range (start, stop, step)? See range( ) function in Chapter 6.2.
We will call list() function on range() function.
Ex. 7.1-2 number_lst.py
# number_lst.py
>>>def number_lst(n): # lst means list
return list( range(1,n+1) )
>>>
>>>print( number_lst(5))
[0,1,2,3,4]
>>>print( number_lst(1,9))
[1,2,3,4,5,6,7,8]
>>> # Now you can create a list with many numbers.
Now make an odd number list from 1 to n (including n if n is odd, not including n if n is even) using range() function.
Ex. 7.1-3 odd_lst.py
# odd_lst.py
>>>def odd_lst(n):
return list( range(1,n+1,2) )
>>>
>>>print (odd_lst(9))
[1,3,5,7,9]
>>>print (odd_lst(10))
[1,3,5,7,9]
CallList() function on a string can turn a string into a list of single charactors:
Ex. 7.1-4 list_string.py
>>> s = 'hi, there!'
>>> lst= list(s)
>>> print(lst)
['h', 'i', ',', 't', 'h', 'e', 'r', 'e','!']
String method, split() can turn a string(which has whitespaces) into a list of words like:
Ex. 7.1-5 split_string.py
# split_string.py
>>> s='I like to eat apples'
>>> lst= s.split()
>>> print(lst)
['I', 'like', 'to', 'eat', 'apples']
When you use variables to create a list, later if you change the variables' original value, the value in the list won't change.
Ex. 7.2-3 var_makeLst.py
# var_makeLst.py
>>> fruit1, fruit2 = 'apple', 'orange'
>>> fruit_list = [fruit1, fruit2]
>>> fruit1 = 'pear'
>>> print (fruit1)
pear
>>> print (fruit_list)
['apple', 'orange']
>>>
7.2 List indexing, list slicing
The indexing and slice operation we saw with strings also work on lists.
Index of a list, from left to right, index starts from 0 to ( len(list) -1); from right to left(counting backward), starts with negative number index -1.
Ex. 7.2-1 lst_index.py
>>> dates = ['Monday', 'Tuesday', 'Wed', 'Th', 'Fri', 'Sat', 'Sun']
>>> dates[1]
'Tuesday'
>>> dates[0]
'Monday'
>>> dates[7]
Traceback (most recent call last):
File "<stdin>", .....list index out of range
>>>
>>>dates[6]
'Sun'
>>>dates[-1]
'Sun'
# same as string index, -1 means the last item
>>>dates[len(dates)-1]
'Sun'
# the item index at the end
Slice of a list
Remember range ( start, stop, step)? Lists understand start, stop and step too.
list[start:stop:step], the first number is the list index that the slice starts, if omitted, default value is 0, means the slice starts from the beginning of the list; the second number after : is the end index(not included in the slice), if omitted, the slice goes to the end of the list. The last number is the step, default value is 1.
Ex. 7.2-2 lst_slice.py
# lst_slice.py
>>> numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> numbers[3:] # Skip the first 3 numbers, then give everything starting at index 3.
[4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> numbers[: 4] # All numbers up to (not including) index number 4
[1, 2, 3, 4]
>>>
>>> numbers[1:6] # elements from index 1 to 6(index 6 is not included)
[2,3,4,5,6]
>>> numbers [: : 3] # Every third number
[1, 4, 7, 10]
>>> numbers [0: 10: 2] # Every other number up to (not including) index location 10
[1, 3, 5, 7, 9]
>>>
We can use list index to reverse a list: Ex. 7.2-3 reverse_list.py
# reverse_list.py
>>> num = [0,1,2,3,4,5,6,7,8]
>>> n1 = num[ : : -1] # reverse a list, from end to start, going backward
>>> print (n1)
[8, 7, 6, 5, 4, 3, 2, 1, 0]
>>>
>>> n2 = num[6:1:-1] # a piece of backward list
>>> print(n2)
[6, 5, 4, 3, 2]
>>>
7.3 Lists are mutable
So far we have seen two types of sequential collections: strings, which are made up of characters; and lists, which are made up of elements of any type. One of the differences between strings and lists is that the characters in a string cannot be modified, but the elements of a list can be modified,. in other words, strings are immutable and lists are mutable.
lists are mutable means we can change an item in a list by accessing it directly as part of the assignment statement. Using list index, we can update one of the list items.
An assignment to an element of a list is called item assignment.
Ex. 7.3-1 itAssign_lst.py
# itAssign_lst.py
>>> lst_pet = ['cat','dog', 10, 'hamster']
>>> lst_pet[2] = 'pig'
>>> print(lst_pet)
['cat', 'dog', 'pig' 'hamster']
Item assignment does not work for strings.
Ex. 7.3-2 itAssign_str.py
# itAssign_str.py
>>> s = 'Aloha'
>>> print(s[2])
o
>>> s[2] = 'ta'
...
TypeError: 'str' object does not support item assignment
>>>
Later in Ch. 7.5 we will learn about list mutation methods.
7.4 Operations on lists and more
Similar to strings, some operators can perform certain tasks on lists. Here we talk about:
addition + (concatenation) multiplication * keyword in (membership operator) len() function list() function ' '.join() function
Concatenation(addition operator works on lists), list1 + list2 gives a new list contains all the items in list1 and list2.
Ex. 7.4-1 add_lst.py
# add_lst.py
>>> lst1 = ['apple', 'pear']
>>> lst2 = ['orange', 'kiwi', 'grape']
>>> mylist = lst1 + lst2
>>> print (mylist)
['apple', 'pear', 'orange', 'kiwi', 'grape']
>>>
>>> anotherList = ['apple'] + ['pear'] # Another way to concatenation lists
>>> print (anotherList)
['apple', 'pear']
Multiplication operator * tells Python to repeat a given item.
Ex. 7.4-2 multiply_lst.py
# multiply_lst.py
>>> myList = ['Yep'] *3
>>> print (myList)
['Yep', 'Yep', 'Yep']
>>>
Use keyword 'in' to find out if an element is in the list.
x in list returns True if x is an element of list
Ex. 7.4-3 in_lst.py
# in_lst.py
>>> fruit = [ 'apple', 'pear', 'banana', 'apple', 'orange']
>>> 'apple' in fruit
True
>>> 'grape' in fruit
False
>>>
built-in len( ) function reports on the size of an list. Ex. 7.4-4 len_lst.py
# len_lst.py
>>> numbers = [1, 2, 3, 4, 5, 8]
>>> len (numbers)
6
>>>
list(a string)--->turns a string into a list; ' '.join(a string list)---> turns a string list into a string. ' '.join(lst[start:stop])---> this takes a chunk of a list and turns it back into a string.
Ex. 7.4-5 lstString_switch.py
# lstString_switch.py
```python
>>> phrase = 'Hello, Buzz!'
>>> ph_list = list (phrase)
>>> print (phrase)
Hello, Buzz!
>>> print (ph_list)
['H', 'e', 'l', 'l', 'o', ',', ' ', 'B','u','z','z','!']
>>>
>>> new_phrase = ' '.join(ph_list)
>>> print (new_phrase)
Hello, Buzz! # same as phrase
>>>
>>> new_phrase2 = ' '.join(ph_list[7:]) # a piece from index 7 to the end
>>> print (new_phrase2)
Buzz
>>>
7.5 List functions (Methods of List Objects)
A little bit about class, objects:
Till now, we've heard about the names of objects and classes here and there, a little explanation is needed right now so that you can understand lists better. We will explore this topic in detail in a later chapter.
When we use type( ) function, we menssioned that 5 is of integer type or class int. When we create a variable s and assign a value to it, say string 'hello' to it, you can think of it as creating an object (i.e. instance) s of class str(i.e. string type).
Object oriented programming(OOP) is to organize your program by combining data and functionality and wrap it inside something called an object. Classes are essentially templates for creating your objects.
Variables that belong to an object or class are referred to as fields.
Objects can also have functionality by using functions that belong to a class. Such functions are called methods of the class. Simply put, a method is a function defined inside a class.. You can use these pieces of functionality only when you have an object of that class. For example, mystring='hello', it's an object of string class. Python provides upper() method for the string class. mystring.upper() will change that string to be 'HELLO'.
Note the use of dot notation for accessing methods of the objects. The “dot notation” is the way we connect the name of an object to the name of a method it can perform. Like mystring.upper() and mylist.reverse().
If it's hard to understand all the above, we have more lessons on objects and classes later. For now, just keep in mind we need to use dot notation to access list methods.
List functions (Methods of List Objects)
Let's get back to List Methods:
A list is an example of usage of objects and classes. Lists come with some very useful built-in methods that can work on the list you call them with.
Suppose we now have a list L, x is a item. Then:
- L.append(x) adds an element x to the end of L
- L.insert(i, x) insert item x at the index i of L
- L.extend(another_lst) appends each elements of another_lst to L
- L.clear() removes all entries from the list
- L.remove(x) removes the first occurrence of x (x is the value to remove, not an index as in pop(i))
L.pop(i) removes and returns the element at index i in L;
if i is omitted, **L.pop()** will removes and returns the last itemL.sort() sorts the elements of s into increasing order
L.reverse() reverses the order of the elements of L
L.copy() makes a copy of the current list and places it in a new list
L.index(x) returns the index of the first occurrence of x
- L.count(x) returns the number of times x appears in L
^^^^^^^^^^^^^^^
Time for examples of using list methods:
append(), extend(), insert(), make a list bigger
Ex. 7.5-1 grow_lst.py
# grow_lst.py
>>> my_lst = [0] # not an empty list
>>> my_lst.append(1) # add element 1 to my_lst
>>> print(my_lst)
[0,1]
>>>
>>> lst2 = [2,3,4]
>>> my_lst.extend(lst2) # appends all elements in list variable lst2 to the end of my_lst
>>> print(my_lst)
[0,1,2,3,4]
>>>
>>> my_lst.extend(['five','six']) # another way to use extend()
>>> print(my_lst)
[0,1,2,3,4, 'five','six']
>>>
>>> my_lst.insert(3,'two and a half') # insert a string element at index 3 of my_lst
>>> print(my_lst)
[0, 1, 2, 'two and a half', 3, 4, 'five', 'six']
remove(), pop(), clear(), make a list smaller
Ex. 7.5-2 shrink_lst.py
# shrink_lst.py
>>> my_lst = ['a', 'weirdo', 'b', 'kiddo', 'c', 'd','end']
>>> my_lst.remove('kiddo')
>>> print(my_lst)
['a', 'weirdo', 'b', 'c', 'd', 'end']
>>>
>>> my_lst.pop(1)
>>> print(my_lst)
['a', 'b', 'c', 'd', 'end']
>>>
>>> my_lst.pop()
'end'
>>> print(my_lst)
['a', 'b', 'c', 'd']
>>>
>>> my_lst.clear()
>>> print(my_lst)
[] # now my_lst is an empty list
>>>
Check your understanding:
Ex. 7.5-3 check_lst.py
>>> size = ['small','medium','large']
>>> size.insert(2, size.pop()) # what's this? think before looking at the answer below
>>> print (size)
['small', 'large', 'medium']
>>>
sort(), reverse() change elements' order in a list
Ex. 7.5-4 order_lst.py
# order_lst.py
>>> my_lst = [1,3,2,5,7,4] # order numbers ascending, alphabetically in a list.
>>> my_lst.sort()
>>> print(my_lst)
[1,2,3,4,5,7]
>>> my_lst.reverse()
>>> print(my_lst)
[7,5,4,3,2,1]
>>>
index(), count() will do searching on a list
Ex. 7.5-5 search_lst.py
# search_lst.py
>>> myLst = ['red','green','yellow','red']
>>>
>>> print( myLst.index('red') )
0 # returns the index of the first 'red'
>>>
>>> print( myLst.count('red') )
2 # 'red' appeared twice
>>> lstCopy = myLst.copy()
>>> print (lstCopy)
['red','green','yellow','red']
>>>
List Aliasing and Copying
lists are mutable, you need to be aware of aliasing. Whenever two variables refer to the same list object, changes to one affect the other. See example:
Ex. 7.5-6 lst_alias.py
# lst_alias.py
>>> original = ['o1','o2','o3','o4']
>>> test = original
>>> print(test is original)
True
>>> print(test)
['o1','o2','o3','o4']
>>> test[2] = 'New'
>>> print(original) # test and original refer to the same list object
['o1','o2','New','o4']
>>>
If you want to modify a list and keep a copy of the original, use the list copy method.
copy() makes a copy of current list and puts in a new list, changes to the new list will not effect the original.
Ex. 7.5-7 lst_copy.py
# lst_copy.py
>>> original = ['o1','o2','o3','o4']
>>> copy = original.copy()
>>> copy[1] = 'New'
>>> print(copy)
['o1','New','o3','o4']
>>> print(original)
['o1','o2','o3','o4'] # hahaha, problem solved
>>>
7.6 Loops and Functions using Lists
For statement make it easy to Loop through the items in a list, it can be as simple as:
for item in L:
print item
Ex. 7.6-1 loopThrough_lst.py
# loopThrough_lst.py
L = ['red', 'blue', 'orange']
for color in L:
print color
...#run
red
blue
orange
Make that into a function:
Ex. 7.6-2 loop_lstFun.py
# loop_lstFun.py
def itemInLst(L):
for i in L:
print (i)
Num = [1,2,3]
itemInLst(Num)
...#run
1
2
3
Use while loop to calculate the average of a list of numbers:
Ex. 7.6-3 average_while.py
# average_while.py
num_list = [1,2,3,5,8,2,5,2]
total = 0
i = 0
while i < len(num_list):
total = total + num_list[i]
i = i + 1
average = total / len(num_list)
print ('The average is: ', average)
...#run
The average is : 3.5
Next let's use for loop to calculate the average, and make it into a function:
Ex. 7.6-4 average_forFun.py
# average_forFun.py
def averageOfLst(L):
total = 0
for item in L: # same as for i in range(0, len(L)):
total += item # total += L[i]
average = total/ len(L)
return average
num=[4,5,3,6,8]
print('average is', averageOfLst(num))
...#run
average is 5.2
Find all divisors of a given number list: Ex. 7.6-5 divisors.py
# divisors.py
num = int(input("Please type in a number to divide: "))
test_list = list(range(1,num+1))
divisorList = []
for number in test_list:
if num % number == 0:
divisorList.append(number)
print('Divisor list is ', divisorList)
...#run
Please type in a number to divide: 15
Divisor list is [1,3,5,15]
Find all the vowels in a given word: Ex. 7.6-6 find_vowel.py
# find_vowel.py
def find_vowel(word):
vowels = [ 'a', 'e', 'i', 'o', 'u' ]
for letter in word: # Take each letter in the word
if letter in vowels: # See if letter is an item in list vowels
print ( letter )
my_word = 'Millionare'
find_vowel(my_word)
...#run...
i
i
o
a
e
List ends: take a list and return a new list consist only the first and last items inside.
Ex. 7.6-7 list_ends.py
# list_ends.py
def endsList(lst):
endsList = []
endsList.append(lst[0])
endsList.append(lst[-1])
return endsList
my_lst=[4,5,6,3,2,1]
print( endsList(my_lst) )
...#run
[4,1]
A similar problem: return a new list consist the last two items in old list.
Ex. 7.6-8 last2.py
# last2.py
def last2(alst):
return [alst[-2], alst[-1]]
myLst=[1,2,3,'second last', 'last']
print( last2(myLst) )
...#run
['second last', 'last']
Try this problem, it's a little bit hard: Return a new list with only the first, third, fifth..., (odd number items)
Ex. 7.6-8 odd_item.py
# ex. odd_item.py
def oddItem(lst):
newLst = []
for i in range(0, len(lst), 2): # every other item's index starts from the beginning
newLst.append(lst[i])
return newLst
myLst = [1,2,3,4,5,6,7,8,9,10]
print( oddItem(myLst))
...#run
[1,3,5,7,9] # 'Ta Da!'
From a given list of words, randomly pick one of them
Ex. 7.6-9 random_item.py
# random_item.py
import random # we need to use randint() function in random module
def pick(word_lst):
rand_index = random.randint(0,len(word_lst))
return word_lst[rand_index]
word = ['hi','apple','red','ok']
print(pick(word))
...#run
apple
...#run again
ok
Reverse the characters in a word like: reverse 'like', we get 'ekil'.
Ex. 7.6-10 reverse_word.py
# reverse_word.py
def reverseWord(w):
lst_w = list(w)
lst_w.reverse()
return ''.join(lst_w) # ''.join() and ' '.join(), check the difference yourself
myWord= 'hello'
print(reverseWord(myWord))
...#run
olleh # odl lay ee odl lay odl lay hee hoo! Sing now!
Reverse the words order in a sentence with at least two words(there is at least one whitespace). Like: reverse 'I have a car' we get 'car a have I'
Ex. 7.6-11 reverse_sentence.py
# reverse_sentence.py
def reverse_sent(sent):
lst = sent.split()
lst.reverse()
re_sent = ' '.join(lst)
return re_sent
my_sent = 'There is a bug '
print(reverse_sent(my_sent)
...#run
bug a is There # Run! Don't run into Bug B!
# another version of reverse_sent to get the same result.
def reverse_sent2(sent):
return ' '.join(sent.split()[::-1])
print(reverse_sent2(my_sent))
...#run
bug a is There # Why still there, is it a dead bug?
Element search You hide, we seek. Find if an element is in a given list
Ex. 7.6-12 search_lst.py
# search_lst.py
def find(a_list, item_to_find):
for item in a_list:
if item == item_to_find:
return True
return False
my_lst = [1,2,3,4,5,6]
print( find(my_lst, 4) )
...#run
True
print( find(my_lst, 8) )
...#run
False