Data Structure

9 minute read

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)