Data Structure
Published:
This lesson covers An Informal Introduction to Python 3.10.5, https://docs.python.org/3/tutorial/introduction.html
Different Data Structures
Lists
nums = [1, 2, 3, 4]
print(nums)
nums.append(5) # Add an item to the end of the list
nums[len(nums):] = [6] # this is append
print(nums) # [1, 2, 3, 4, 5]
nums = [1, 2, 3, 4]
nums.append([5, 6, 7])
print(nums) # [1, 2, 3, 4, [5, 6, 7]]
nums = [1, 2, 3, 4]
nums.extend([5, 6, 7]) # Extend list from iterable
print(nums) # [1, 2, 3, 4, 5, 6, 7]
nums = [1, 2, 3, 4]
nums.extend(range(3)) # Extend list from iterable
print(nums) # [1, 2, 3, 4, 0, 1, 2]
nums = [1, 2, 3, 4]
nums.extend((5, 6, 7)) # Extend list from iterable
print(nums) # [1, 2, 3, 4, 0, 1, 2]
nums = [1, 2, 3, 4]
nums.insert(0, 5)
print(nums) # [5, 1, 2, 3, 4]
nums = [1, 2, 3, 4, 4, 4]
nums.remove(4) # remove first element else ValueError
print(nums) # [1, 2, 3, 4, 4]
nums = [1, 2, 3, 4]
nums.pop(0) # remove indexed element
print(nums) # [2, 3, 4]
nums = [1, 2, 3, 4]
nums.pop() # remove last element if no index
print(nums) # [1, 2, 3]
nums = [1, 2, 3, 4]
nums.clear() # remove all elements del nums[:]
print(nums) # []
nums = [1, 2, 3, 4, 3] # zer0-based index else ValueError
print(nums.index(3)) # 2
nums = [1, 2, 3, 4, 5, 3] # 3 after index from 3
print(nums.index(3, 3)) # 5
nums = [1, 2, 3, 4, 5, 3] # 3 after index from 3 until 4
# print(nums.index(3, 3, 4)) # ValueError
nums = [1, 2, 3, 4, 4, 4]
print(nums.count(4)) # count number of times 4 appears #3
nums = [5, 2, 3, 4, 1]
nums.sort(reverse=True) # inplace sort
print(nums) # [5, 4, 3, 2, 1
nums = [5, 2, 3, 4, 1]
nums = sorted(nums, reverse=True) # returns sorted list
print(nums) # [5, 4, 3, 2, 1
nums = [5, 2, 3, 4, 1]
nums.sort(key = lambda x: x%2) # inplace sort with key
print(nums) # [2, 4, 5, 3, 1]
nums = [1, 2, 3, 4, 5]
nums.sort(key = lambda x: x%2) # inplace sort
print(nums) # [2, 4, 1, 3, 5]
nums = [5, 2, 3, 4, 1]
nums.sort(key = lambda x: x%2, reverse=True) # inplace sort with key
print(nums) # [5, 3, 1, 2, 4] # remainder order 1, 0
nums = [1, 2, 3, 4, 5]
nums.sort(key = lambda x: x%2, reverse=True) # inplace sort
print(nums) # [1, 3, 5, 2, 4]
nums = [1, 2, 3, 4, 5]
nums.reverse() # Inplace reverse
print(nums) # [5, 4, 3, 2, 1]
nums1 = [1, 2, 3, 4, 5]
nums2 = nums1.copy() # Shallow copy
print(hex(id(nums1)), hex(id(nums1))) # same id
Using Lists as Stacks (LIFO)
stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack) # [3, 4, 5, 6, 7]
print(stack.pop()) # 7
print(stack) # [3, 4, 5, 6]
print(stack.pop()) # 6
print(stack.pop()) # 5
print(stack) # [3, 4]
Using Lists as Queues (FIFO)
- list not fast for queue
- use
collections.deque
for fast appends and pops
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry") # Terry arrives
queue.append("Graham") # Graham arrives
print(queue.popleft()) # 'Eric' # The first to arrive now leaves
print(queue.popleft()) # 'John' # The second to arrive now leaves
# Remaining queue in order of arrival
print(queue) # deque(['Michael', 'Terry', 'Graham'])
print(queue.pop()) # Graham # LIFO - stack
print(queue) # deque(['Michael', 'Terry'])
List Comprehensions
- A concise way to create lists
squares = []
for x in range(5):
squares.append(x**2)
print(squares) # [0, 1, 4, 9, 16]
squares = list(map(lambda x: x**2, range(5)))
print(squares) # [0, 1, 4, 9, 16]
squares = [x**2 for x in range(5)]
print(squares) # [0, 1, 4, 9, 16]
combs = [(x, y) for x in [1, 2, 3] for y in [3, 1, 4] if x != y]
print(combs)
combs = []
for x in [1, 2, 3]:
for y in [3, 1, 4]:
if x != y:
combs.append((x, y))
print(combs)
vec = [-4, -2, 0, 2, 4]
# create a new list with the values doubled
z = [x*2 for x in vec]
print(z) # [-8, -4, 0, 4, 8]
# filter the list to exclude negative numbers
z = [x for x in vec if x >= 0]
print(z) # [0, 2, 4]
# apply a function to all the elements
z = [abs(x) for x in vec]
print(z) # [4, 2, 0, 2, 4]
# call a method on each element
freshfruit = [' banana', ' loganberry ', 'passion fruit ']
z = [weapon.strip() for weapon in freshfruit]
print(z) # ['banana', 'loganberry', 'passion fruit']
# create a list of 2-tuples like (number, square)
z = [(x, x**2) for x in range(6)]
print(z) # [(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
# the tuple must be parenthesized, otherwise an error is raised
# z = [x, x**2 for x in range(6)] error
# flatten a list using a listcomp with two 'for'
vec = [ [1, 2, 3], [4, 5, 6], [7, 8, 9]]
z = [num for elem in vec for num in elem]
print(z) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
Nested List Comprehensions
# List of lists
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
# first element of each row
# then second element of each row ...
transposed = [ [row[i] for row in matrix] for i in range(4)]
print(transposed) # [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]
The del
statement
a = [-1, 1, 66.25, 333, 333, 1234.5]
print(a)
del a[0]
print(a) # [1, 66.25, 333, 333, 1234.5]
del a[2:4] # 4 not included
print(a) # [1, 66.25, 1234.5]
del a[:]
print(a) # []
Tuples and Sequences
t = 12345, 54321, 'hello!'
print(t[0]) # 12345
print(t) # (12345, 54321, 'hello!')
# Tuples may be nested:
u = t, (1, 2, 3, 4, 5)
print(u) # ((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
# Tuples are immutable:
#t[0] = 88888 # Error
# but they can contain mutable objects
# tuple (immutable) of lists (mutable)
v = ([1, 2, 3], [3, 2, 1])
print(v) # ([1, 2, 3], [3, 2, 1])
empty = ()
singleton = 'hello', # <-- note trailing comma
#singleton = 'hello' # without comma it is string
print(len(empty)) # 0
print(len(singleton)) # 1
print(singleton) # ('hello',)
# Tuple Immutable due to packing and packing
# Tuples - hetrogeneous sequence of elements accessed by unpacking
t = 12345, 54321, 'hello!' # Tuple Packing
x, y, z = t # Tuple unpacking
print(t) # (12345, 54321, 'hello!')
print(x, y, z) # 12345 54321 hello!
Sets
- unordered collection with no duplicate
- Curly braces or the set() function can be used to create sets.
- to create an empty set you have to use set(), not {} since {} creates dict
basket = {'apple', 'orange', 'apple',
'pear', 'orange', 'banana'}
# {'orange', 'banana', 'pear', 'apple'}
print(basket)
# fast membership testing
print('orange' in basket) # True
print('crabgrass' in basket) # False
# Demonstrate set operations
# on unique letters from two words
a = set('abracadabra')
b = set('alacazam')
# unique letters in a
print(a) # {'a', 'r', 'b', 'c', 'd'}
# letters in a but not in b
print(a - b) # {'r', 'd', 'b'}
# letters in a or b or both
#{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
print(a | b)
# letters in both a and b
print(a & b) # {'a', 'c'}
# letters in a or b but not both
print(a ^ b) # {'r', 'd', 'b', 'm', 'z', 'l'}
- Set Comprehension
a = {x for x in 'abracadabra' if x not in 'abc'}
print(a) # {'r', 'd'}
Dictionaries
tel = {'jack': 4098, 'sape': 4139}
tel['guido'] = 4127
# {'jack': 4098, 'sape': 4139, 'guido': 4127}
print(tel)
print(tel['jack']) # 4098
del tel['sape']
tel['irv'] = 4127
print(tel)
# {'jack': 4098, 'guido': 4127, 'irv': 4127}
print(list(tel))
# ['jack', 'guido', 'irv']
print(sorted(tel))
# ['guido', 'irv', 'jack']
print('guido' in tel) # True
print('jack' not in tel) # False
# create dict from sequence of k,v pairs
t = [('sape', 4139), ('guido', 4127), ('jack', 4098)]
tel = dict(t)
print(tel)
# {'sape': 4139, 'guido': 4127, 'jack': 4098}
# Disctionary Comprehension
d = {x: x**2 for x in (2, 4, 6)}
print(d) # {2: 4, 4: 16, 6: 36}
# when keys are strings
# passed as keyword arguments to create dict
tel = dict(sape=4139, guido=4127, jack=4098)
print(tel)
# {'sape': 4139, 'guido': 4127, 'jack': 4098}
Looping Techniques
# Access both k, v from dict
knights = {'gallahad': 'the pure',
'robin': 'the brave'}
for k, v in knights.items():
print(k, v)
# Access index and element
for i, v in enumerate(['tic', 'tac', 'toe']):
print(i, v)
# Loop over two or more sequences at same time
questions = ['name', 'quest', 'favorite color']
answers = ['lancelot', 'the holy grail', 'blue']
for q, a in zip(questions, answers):
print(f"What is your {q}? It is {a}")
# To loop over a sequence in reverse
for i in reversed(range(1, 10, 2)):
print(i)
# To loop over sorted
basket = ['apple', 'orange', 'apple',
'pear', 'orange', 'banana']
for i in sorted(basket):
print(i)
# To loop over unique
basket = ['apple', 'orange', 'apple',
'pear', 'orange', 'banana']
for i in set(basket):
print(i)