Python Essential Data Structures

Data Structure	Python Instantiation *	Operations	what it does	Run-time
Hash Table
(Dictionary)	`dct = {

”oranges”: 1,
”apples”: 2

}

keys = ["oranges", "apples"]
vals = [1, 2]
dct = {}
for key, val in zip(keys, vals): dct[key] = val

dct = { key:val for key, val in zip(keys, vals) }|if dct: len(dct) dct[aKey] = aVal if aKey in dct: dct.pop(aKeyType)` | if not empty? get size insert into dictionary do … if key exists remove+return an element | O(1) O(1) O(1)** O(1)** O(1)** O(n)

O(n) | | Array (auto-resizing) | lst = [1, 6, “kiwi”, 3]

lst = [] for i in range(5): lst.append(1*2)

`lst = [func(num) for num in nums]

lst = [func(num, i) for i, num in enumerate(nums)]` | see “python lists” | lst becomes [1, 6, “kiwi”, 3]

lst becomes [0, 2, 4, 6, 8] | O(n)

O(n)

O(n) | | Queue | from collections import deque qu = deque() ”doubly ended queue” | bool(qu) len(qu) qu.append(aValType) elem = qu.popleft() qu[0] qu[-1] | is not empty? get size push pop+return an element front back | O(1) O(1) O(1) O(1) O(1) O(1) | | Stack | from collections import deque stk = deque() ”doubly ended queue” | bool(stk) len(stk) stk.append(aValType) elem = stk.pop() stk[-1] | is not empty? get size push pop+return an element peek | O(1) O(1) O(1) O(1) O(1) | | Linked List | class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None | | | | | Binary Tree | class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None | | | | | max/min heap | import heapq hp = [3,6,8,2,5,8] heapq.heapify(hp) (build heap) O(n) (min-heap)

negate inputs to make max-heap | bool(hp) len(hp) heapq.heappush(hp, aValType) heapq.heappop(hp) hp[0] | is not empty? get size push pop peek | O(1) O(1) O(log(n)) O(log(n)) O(1) | | Graph (adj list) (for sparse graphs) | no built-in structure | addEdge(v1, v2) removeEdge(v1, v2) addVertex(v) removeVertex(v) doesEdgeExist(v1, v2) doesVertexExist(v) findAllAdjacentVertices(v) | | O(1) O(1) O(1) O(deg(v)) O(deg(v1)) O(|V|) O(1) | | Graph (adj matrix) (for dense graphs) | no built-in structure | addEdge(v1, v2) removeEdge(v1, v2) addVertex(v) removeVertex(v) doesEdgeExist(v1, v2) doesVertexExist(v) findAllAdjacentVertices(v) | | O(1) O(1) O(|V|) O(|V|)** O(1) O(|V|) O(|V|) | | set (uses hash-table) | s1 = set((”a”, “b”, “c”))

s1 = set() start with empty set

s1 = {”a”, “b”, “c”}

fzn_set = frozenset((”a”, “b”, “c”)) this creates an immutable set

| `bool(s1) len(s1) “a” in s1 s1.add("d") s1.remove("a")

s1.issubset(s2)or s1 <= s2 s1 < s2 s1.issuperset(s2)ors1 >= s2 s1 > s2

s1.union(s2)ors1|s2 s1.intersection(s2)or s1&s2 s1&s2&s3&s4 s1.difference(s2)ors1-s2 s1.isdisjoint(s2)

s1.symmetric_difference(s2)ors1^s2

s1.difference_update(s2) ors1 -= s2

s1.symmetric_difference_update(s2)ors1 ^= s2` | is not empty? get size boolean for if value is in set add an element to a set remove an element from a set

is s1 a subset of s2 is s1 a proper subset of s2 is s1 a superset of s2 is s1 a proper superset of s2

union of s1 and s2 intersection of s1 and s2 intersection of s1, s2, s3, s4 set difference of s1 and s2 are s1 and s2 disjoint sets

symmetric difference s1, s2

remove elements of s2 from s1

make s1 have elements that are in s1 or s2 (not both) | O(1) O(1) O(1)** O(1)** O(1)**

O(n1)**

O(n2)**

O(n1+n2) O(min(n1, n2))** (n-1)*O(max(n1,..,n2)) ? O(s1)

O(n1)**

O(n2)

Python Lists

These are implemented as automatically resizing arrays

initialize like this: lst = [”apple”, “orange”, “banana”]

Operation	Purpose	Run-time (on average)
`len(lst)`	get length of the list	O(1)
`lst.append(”guava”)`	add a value (”guava”) to the end of the list	O(1)
`lst.clear()`	Removes all the elements from the list	O(n)
`my_copy = lst.copy()`	Returns a copy of the list	O(n)
`lst.count()`	Returns the number of elements with the specified value	O(n)
`lst.extend([”pear”, “kiwi”])`	Add the elements of a list (or any iterable) to the end of the current list	O(k)*
`lst.index(”apple”)`	Returns the index of the first element with the specified value	O(1)
`lst.insert(2, "kiwi")`	Adds an element (”kiwi”) at the specified position (2)	O(n)
`elem = lst.pop()`	Removes the element at the end	O(1)
`lst.remove()`	Removes the first item with the specified value	O(n)
`lst.reverse()`	Reverses the order of the list	O(n)
`lst.sort(reverse=False, key=comparatorFunc)`	Sorts the list (can choose to reverse) (can choose the comparison function)	O(nlogn)
`sublst = lst[start:end]`	Retrieve a sub-list from `start` to `end`	O(end - start)
`min(lst)` or `max(lst)`	gets the min or max value	O(n)

note* : k is number of elements in list argument to this function

Strings

str1 = 'such' #initilize a variable with a string like this
str2 = 'fun'
n1 = len(str1) #size of str1
n2 = len(str2) #size of str2

Operation	Evaluates to…	Purpose	Run-time
len(str1)	4	get number of characters in string	O(n1)
str1 + ‘ ’ + str2	‘such fun’	concatenates the three strings	O(n1 + n2)
str1 == str2	False	see if strings match i.e. same sequence of characters	O(min(n1, n2))**
str1[2]
str[1:3]	‘c’
’uc’	get the character from str1 at index 2
get substring from index 1 up to -not including- index 3	O(1)
O(len(substring))
‘,’.join([str1, str2])	‘such,fun’	concatenates strings in the list (str1 and str2) with
a comma in between	O(n1 + n2)
str1.split(’u’)	[’s’,’ch’]	splits string in a list of substrings using ‘u’ as a delimiter	O(n1len(delimiter))**

note**: O(1) if strings are different by a factor of two

note***: O(n/len(separator)) sublinear in good cases due to specialized algorithm

Abstract function	Python example	value returned
map
(with lambda)	just use a list comprehension (above)
reduce	`import functools`
`functools.reduce(lambda a,b: a+b, [1,4,7])`	1+4+7
filter	`list(filter(lambda n: n%2==0, [1,2,3,4,5,6,7]))`	[2,4,6]
(even numbers)