COMP 6411: Comparative

Programming Languages

Tutorial 2: Data
structures
Topics

• A review of Python built-in data structures

• List extensions
– Stack
– Queue
– Deque
• Dictionaries
– Hash table implementation
• Tuples
– Sequence unpacking
• Sets
Building on Lists

• We can “re-purpose” the basic list to obtain

more specialized functionality.
• Stack: a “last-in-first out” (LIFO) structure.
– the append() and pop() methods can be used to
add and remove elements from the end of the
queue.
list1 = [“foo”, “boo”]
[Link](“bat”)
[Link](“bar”)
top = [Link]() # do not specify index
>>> top
>>> ‘bar’
Lists…cont’d

• And, of course, you can use a list to create

a queue
– First-in-first-out (FIFO).

l2 = [“foo”, “boo”]
[Link](“bat”)
[Link](“bar”)
first = [Link](0) # need index
>>> first
>>> ‘foo’
Slight complication

• The use of a List to represent a queue

works properly, in terms of the result.
• However, it is not recommended that you
actually use a List like this.
• Why not?
– As noted previously, Lists are represented
physically as an array.
– Popping the first element in the array is very
expensive in large lists because EVERYTHING
must be shifted by one.
 A better queue

• In practice, you will want to use a data

structure provided for just this purpose.
• Python refers to this as a deque.

from collections import deque # more on this later

q1 = deque([“foo”, “boo”])
[Link](“bat”)
[Link](“bar”)
first = [Link]()
>>> first
>>> ‘bar’
What is a deque

• To ensure adequate performance, a deque

is implemented using a doubly linked list

head foo boo bat bar

head foo boo bat bar

head boo bat bar

8-7
Proper use

• A deque works very well for popping

elements at either end of the data structure
• However, it should probably not be used for
general list processing
• Any kind of random access to the middle of
the deque would be very slow since the
whole list must be traversed
– This includes any kind of slice operations
– So use lists unless you have a good reason not
to do this.
Dictionaries

• One of the more useful python data

structures is the dictionary.
• In short, this is a set of (key/value) pairs
– The key is a unique “lookup” element
– Each key is associated with some value
– Keys must be unique
– Keys can be any immutable type
• e.g., strings or ints
• But NOT lists
• There is no fixed order for the key/value
pairs
 Basic use and methods

• Dictionaries are quite easy to use in Python

• Key/value pairs use a key : value syntax
• Initialization uses curly braces
• Assignment uses square brackets
location = {“joe” : “Montreal”, “Sue” : “Toronto”} # init
>>> location[“Sue”]
>>> ‘Toronto’
location[“Mo”] = “Tokyo”
del location[“joe”] # standard Python del statement
>>> location
>>> {“Sue” : “Toronto”, “Mo” : “Tokyo”}
Dictionary methods

• Dictionaries provide a number of additional

methods.
• A few of the more useful include:
– [Link](): returns a list of key/value pairs
– [Link](): returns a list of the keys
– [Link](): returns a list of the values
– [Link](): removes all items
– [Link](key): returns value if it exists
• If key doesn’t exist, nothing is returned but there is no
error raised
• Note that dict[“key”] would raise a KeyError exception if
the key does not exist
Other Dictionary processing

• There are a handful of other useful operations

for dictionaries
– del dict[key]: removes the key, if it exists (raises
KeyError if key not found)
– key [not] in dict: check for existence, returns True or
False
– len(dict): returns the number of items in the
dictionary.
• Finally, note that adding a key that already
exists is not an error
– Instead, the value in the key/value pair simply
replaces the current value.
Dictionary Implementation

• Dictionaries are implemented using a Hash

Table.
– A hash table uses a “hash function” to convert a
key into an index in a table/array.
– The table holds the values (or references to the
values)
• The average cost of a lookup up is O(1)
– There is a constant number of steps in
computing the hash function.
Implementation…cont’d
key
• Dictionaries are typically
implemented with either a
Balanced Tree or a Hash
Table. Hash
function

• In the case of Python, a

Hash Table is used.
• Note that while the value
amortized cost is O(1), this
includes:
– The cost of the Hash Function value

– The cost of collision

resolution, as multiple keys
may hash to the same cell
– Dynamic re-sizing of the
array once it is close to full.
Tuples

• Tuples are another example of a sequence data

type in Python.
– Strings and lists are also sequences
• Elements of a sequence have a specific order.
• Superficially, a tuple looks a lot like a list.
• The difference is that unlike lists, a tuple is
immutable – you can not change the element at a
specific position.
• Note: tuples can contain lists as elements
– So, indirectly, you can change its contents by changing
the value of mutable elements.
• Implementation: As a type of sequence, a tuple is
implemented as an array of references to tuple
elements.
Tuples…cont’d

• Tuple construction is quite easy and simply

consists of a comma-delimited set of
elements.
• Tuples can be nested and, for example, can
contain other tuples or lists.
• When displayed, tuples are listed with ( )
parenthesis, rather than the [ ] of lists.
• Empty tuples are constructed with empty
parenthesis
– nothing = ( )
• Tuples of one element are (oddly) constructed
using a trailing comma
– one = “boo”,
Basic use

• In practice, tuples are typically used for

heterogeneous data.
– A little like a C struct
• Lists are often used for homogenous data
– A little like a Java vector

t1 = “Joe”, 43, “Montreal” # a tuple

l1 = [78.7, 26.33, 99.99] # a list
both = t1, l1 # new tuple
>>>both
( (“Joe”, 43, “Montreal”), [78.7, 26.33, 99.99] )
l1[1] = 0.0 # update the list
>>>both
( (“Joe”, 43, “Montreal”), [78.7, 0.0, 99.99] )
Sequence unpacking

• One interesting Python feature is sequence

unpacking.
• Here, we can assigned the elements of a
sequence to a set of variables
• Note: an error will be generated if the number
of variables does not match the number of
elements in the sequence
t1 = “Joe”, 43, “Montreal” # a tuple
a, b, c = t1
>>>b
43
m, n = t1
ValueError: too many values to unpack
Sets

• A set is an unordered collection of elements

• Duplicates are explicitly disallowed.
• Operations on sets typically consists of:
– Testing for membership in the set
– Elimination of duplicates in a list
– Basic set operations
• Union
• Intersection
• Difference
Sets…cont’d

• Sets can be constructed with one of two

approaches
1. Initialize using curly braces
2. Use the set() function
• An empty set must use this syntax since { } will
create an empty dictionary.
• Sets also provide a group of methods,
including:
– [Link](x): add element x to set
– [Link](x)
– [Link]()
Set implementation

• Sets MUST prevent the inclusion of duplicate

values.
• To ensure this, sets are implemented
internally as Hash Tables (basically a Python
dictionary)
• In this case, only the keys are used – there
are no values that need to be stored in the
Hash Table
• Note: Adding an element that already exists
does NOT cause an error
– As is the case with Hash Tables, the duplicate key
is simply not inserted.
 Using a set

• In practice, Set operations are relatively

limited.
s1 = {“boo”, “bar”}
[Link](“baz”)
[Link](“bar”) # no error, just ignored
l1 = [“noo”, “nat”] # a “mutable” list
[Link](l1)
ValueError: unhashable type: list
s2 = {“boo”, “bar”}
>>> s1 – s2 # items in 1, but not 2
set([“baz”])
>>> s2 – s1 # items in 2 but not 1
set([])
Data structure summary

• Python has a group of built-in data

structures
– Strings
– Lists
• Stack
• Queue (Deque)
– Dictionary
– Tuple
– Set
Key features

• Strings, lists and tuples are sequences

– Sequence items have a specific order
• List are mutable, tuples and strings are not
• Tuples are typically used to store
heterogeneous items
• List are typically used to store homogenous
items
• Dictionaries are used for key/value pairs
– Duplicates are not possible
• Sets store unordered items and, like hash
tables, do not allow duplicates