Data Structures
lec1
What are Data Structures?
• Data Structures are ways of organizing and storing data in a
computer so it can be accessed and modified efficiently.
Why Are Data Structures Important?
They help:
• Store data efficiently
• Access data quickly
• Manage large amounts of information
• Improve program performance
• Solve complex problems
What is Algorithm
• An algorithm is a step-by-step procedure or set of instructions
used to solve a problem or perform a task.
List Tuple
General purpose Immutable (can’t add/change)
Most widely used data structure Useful for fixed data
Grow and shrink size as needed Faster than Lists
Sequence type Sequence type
Sortable
Set Dict
Store non-duplicate items Key/Value pairs
Very fast access vs Lists Associative array, like Java HashMap
Math Set ops (union, intersect) Unordered
Unordered
SEQUENCES (String, List, Tuple)
• indexing: x[6]
• slicing: x[1:4]
• adding/concatenating: +
• multiplying: *
• checking membership: in/not in
• iterating for i in x:
• len(sequence1)
• min(sequence1)
• max(sequence1)
• sum(sequence1[1:3]])
• sorted(list1)
• [Link](item)
• [Link](item)
SEQUENCES
String List Tuple
• indexing
– Access any item in the sequence using its index
String
x = 'frog'
print (x[3]) # prints 'g'
List
x = ['pig', 'cow', 'horse']
print (x[1]) # prints 'cow'
SEQUENCES
String List Tuple
• slicing
– Slice out substrings, sublists, subtuples using indexes
[start : end+1 : step]
x = 'computer'
Code Result Explanation
x[1:4] 'omp' Items 1 to 3
x[1:6:2] 'opt' Items 1, 3, 5
x[3:] 'puter' Items 3 to end
x[:5] 'compu' Items 0 to 4
x[-1] 'r' Last item
x[-3:] 'ter' Last 3 items
x[:-2] 'comput' All except last 2 items
SEQUENCES
String List Tuple
• adding / concatenating
– Combine 2 sequences of the same type using +
String
x = 'horse' + 'shoe'
print (x) # prints 'horseshoe'
List
x = ['pig', 'cow'] + ['horse']
print (x) # prints ['pig', 'cow', 'horse']
SEQUENCES
String List Tuple
• multiplying
– Multiply a sequence using *
String
x = ‘bug' * 3
print (x) # prints ‘bugbugbug'
List
x = [8, 5] * 3
print (x) # prints [8, 5, 8, 5, 8, 5]
SEQUENCES
String List Tuple
• checking membership
– Test whether an item is in or not in a sequence
String
x = 'bug'
print ('u' in x) # prints True
List
x = ['pig', 'cow', 'horse']
print ('cow' not in x) # prints False
SEQUENCES
String List Tuple
• iterating
– Iterate through the items in a sequence
Item
x = [7, 8, 3]
for item in x:
print (item * 2) # prints 14, 16, 6
Index & Item
x = [7, 8, 3]
for index, item in enumerate(x):
print (index, item) # prints 0 7, 1 8, 2 3
SEQUENCES
String List Tuple
• number of items
– Count the number of items in a sequence
String
x = 'bug'
print (len(x)) # prints 3
List
x = ['pig', 'cow', 'horse']
print (len(x)) # prints 3
SEQUENCES
String List Tuple
• minimum
– Find the minimum item in a sequence lexicographically
– alpha or numeric types, but cannot mix types
String
x = 'bug'
print (min(x)) # prints 'b'
List
x = ['pig', 'cow', 'horse']
print (min(x)) # prints 'cow'
SEQUENCES
String List Tuple
• maximum
– Find the maximum item in a sequence
– alpha or numeric types, but cannot mix types
String
x = 'bug'
print (max(x)) # prints 'u'
List
x = ['pig', 'cow', 'horse']
print (max(x)) # prints 'pig'
SEQUENCES
String List Tuple
• sum
– Find the sum of items in a sequence
– entire sequence must be numeric type
String -> Error
x = [5, 7, 'bug‘]
print (sum(x)) # error!
List
x = [2, 5, 8, 12]
print (sum(x)) # prints 27
print (sum(x[-2:])) # prints 20
SEQUENCES
String List Tuple
• sorting
– Returns a new list of items in sorted order
– Does not change the original list
String
x = 'bug'
print (sorted(x)) # prints ['b', 'g', 'u']
List
x = ['pig', 'cow', 'horse']
print (sorted(x)) # prints ['cow', 'horse', 'pig']
SEQUENCES
String List Tuple
• count (item)
– Returns count of an item
String
x = 'hippo'
print ([Link]('p')) # prints 2
List
x = ['pig', 'cow', 'horse', 'cow']
print ([Link]('cow')) # prints 2
SEQUENCES
String List Tuple
• index (item)
– Returns the index of the first occurrence of an item
String
x = 'hippo'
print ([Link]('p')) # prints 2
List
x = ['pig', 'cow', 'horse', 'cow']
print ([Link]('cow')) # prints 1
SEQUENCES
String List Tuple
• unpacking
– Unpack the n items of a sequence into n variables
x = ['pig', 'cow', 'horse']
a, b, c = x # now a is 'pig'
# b is 'cow',
# c is 'horse'
Note:
The number of variables must exactly match the length of the list.
LISTS
LISTS
All operations from Sequences, plus:
• constructors:
• del list1[2] delete item from list1
• [Link](item) appends an item to list1
• [Link](sequence1) appends a sequence to list1
• [Link](index, item) inserts item at index
• [Link]() pops last item
• [Link](item) removes first instance of item
• [Link]() reverses list order
• [Link]() sorts list in place
LISTS
• constructors – creating a new list
x = list()
x = ['a', 25, 'dog', 8.43]
x = list(tuple1)
List Comprehension:
x = [m for m in range(8)]
resulting list: [0, 1, 2, 3, 4, 5, 6, 7]
x = [z**2 for z in range(10) if z>4]
resulting list: [25, 36, 49, 64, 81]
LISTS
• delete
– Delete a list or an item from a list
x = [5, 3, 8, 6]
del(x[1]) # [5, 8, 6]
del(x) # deletes list x
LISTS
• append
– Append an item to a list
x = [5, 3, 8, 6]
[Link](7) # [5, 3, 8, 6, 7]
LISTS
• extend
– Append an sequence to a list
x = [5, 3, 8, 6]
y = [12, 13]
[Link](y) # [5, 3, 8, 6, 7, 12, 13]
LISTS
• insert
– Insert an item at given index [Link](index, item)
x = [5, 3, 8, 6]
[Link](1, 7) # [5, 7, 3, 8, 6]
[Link](1,['a','m']) # [5, ['a', 'm'], 7, 3, 8, 6]
LISTS
• pop
– Pops last item off the list, and returns item
x = [5, 3, 8, 6]
[Link]() # [5, 3, 8]
# and returns the 6
print([Link]()) # prints 8
# x is now [5, 3]
LISTS
• remove
– Remove first instance of an item
x = [5, 3, 8, 6, 3]
[Link](3) # [5, 8, 6, 3]
LISTS
• reverse
– Reverse the order of the list
x = [5, 3, 8, 6]
[Link]() # [6, 8, 3, 5]
LISTS
• sort
– Sort the list in place
x = [5, 3, 8, 6]
[Link]() # [3, 5, 6, 8]
Note:
sorted(x) returns a new sorted list without changing the original list x.
[Link]() puts the items of x in sorted order (sorts in place).
TUPLES
TUPLES
• Support all operations for Sequences
• Immutable, but member objects may be mutable
• If the contents of a list shouldn’t change, use a tuple
to prevent items from accidently being added,
changed or deleted
• Tuples are more efficient than lists due to Python’s
implementation
TUPLES
• constructors – creating a new tuple
x = () # no-item tuple
x = (1,2,3)
x = 1, 2, 3 # parenthesis are optional
x = 2, # single-item tuple
x = tuple(list1) # tuple from list
TUPLES
• immutable
– But member objects may be mutable
x = (1, 2, 3)
del(x[1]) # error!
x[1] = 8 # error!
x = ([1,2], 3) # 2-item tuple: list and int
del(x[0][1]) # ([1], 3)
SETS
SETS
• A set is an unordered collection with no duplicate
elements.
• Basic uses include membership testing and
eliminating duplicate entries.
• Set objects also support mathematical operations
like union, intersection, difference, and symmetric
difference.
SETS
• constructors – creating a new set
x = {3,5,3,5} # {5, 3}
x = set(‘) # empty set
list1=[5,6,8,5,2]
x = set(list1) # {8,2,5,6}
basket = {'apple', 'orange', 'apple', 'pear',
'orange', 'banana'}
Set Comprehension:
x = {3*x for x in range(10) if x>5}
resulting set: {18, 21, 24, 27} but in random order
SETS
• basic set operations
Description Code
Add item to set x [Link](item)
Remove item from set x [Link](item)
Get length of set x len(x)
item in x
Check membership in x
item not in x
Pop random item from set x [Link]()
Delete all items from set x [Link]()
SETS
• basic set operations
• a = set('abracadabra’)
• [Link]('w’) #{'d', 'a', 'c', 'w', 'b', 'r’}
• [Link](‘c’) # {'d', 'a', 'w', 'b', 'r’}
• Len(a) #5
• ‘x’ in a #False
• [Link]() # {'a', 'w', 'b', ‘r’}
• [Link]() # set()
SETS
• standard mathematical set operations
Set Function Description Code
Intersection AND set1 & set2
Union OR set1 | set2
Symmetric Difference XOR set1 ^ set2
Difference In set1 but not in set2 set1 – set2
Subset set2 contains set1 set1 <= set2
Superset set1 contains set2 set1 >= set2
SETS
• standard mathematical set operations
a = set('abracadabra')
b = set('alacazam')
a # {'a', 'r', 'b', 'c', 'd'}
a - b # {'r', 'd', 'b'}
a & b # letters in both a and b{'a', 'c'}
a ^ b # {'r', 'd', 'b', 'm', 'z', 'l’}
a | b # {'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l’}
c=set('acz’)
c<=b # True
DICTIONARIES
DICTIONARIES
• Dictionaries are sometimes found in other
languages as “associative memories” or “associative
arrays”.
• Unlike sequences, which are indexed by a range of
numbers, dictionaries are indexed by keys, which
can be any immutable type; strings and numbers
can always be keys
DICTIONARIES
• constructors – creating a new dict
x = {'pork':25.3, 'beef':33.8, 'chicken':22.7}
x = dict([('pork', 25.3),('beef', 33.8),('chicken', 22.7)])
x = dict(pork=25.3, beef=33.8, chicken=22.7)
DICTIONARIES
• basic dict operations
Description Code
Add or change item in dict x x['beef'] = 25.2
Remove item from dict x del x['beef']
Get length of dict x len(x)
Check membership in x item in x
(only looks in keys, not values) item not in x
Delete all items from dict x [Link]()
Delete dict x del x
DICTIONARIES
• accessing keys and values in a dict
[Link]() # returns list of keys in x
[Link]() # returns list of values in x
[Link]() # returns list of key-value tuple pairs in x
item in [Link]() # tests membership in x: returns boolean
DICTIONARIES
• iterating a dict
for key in x: # iterate keys
print(key, x[key]) # print all key/value pairs
for k, v in [Link](): # iterate key/value pairs
print(k, v) # print all key/value pairs
Note:
Entries in a dict are in random order.