We discussed OOP and special methods that allow us to define operators in Python. Then, we saw an implementation of a Linked list data structure.
OOP allows us to create classes at will and to define complex objects. Remember that the most important thing is to find a good inner representation of the object so that you will have an easy time working with it.
Important properties of Linked lists:
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
A link to special method names in python: https://diveintopython3.net/special-method-names.html
We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
f
g
(1*x^0) + (1*x^1)
(2*x^0) + (3*x^1) + (4*x^2)
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
f = Polynomial([1, 1])
f.degree()
f.evaluate(5)
1
6
p = Polynomial([1,0,1])
q = Polynomial([1,0,1])
p == q
False
Without it, Python compares memory adderesses
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
f = Polynomial([1, 1])
f2 = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
f == g
f == f2
f.__eq__(f2)
False
True
True
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms[0] += other
return Polynomial(terms)
#else, other is a polynomial
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
f+g
f+100
100+f
(3*x^0) + (4*x^1) + (4*x^2)
(101*x^0) + (1*x^1)
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-6-b1cbfd0c49d6> in <module> 49 f+g 50 f+100 ---> 51 100+f TypeError: unsupported operand type(s) for +: 'int' and 'Polynomial'
Since there is no support for addition with a Polynomial in the class int, python needs a definition of right addition for int in class Polynomial
When executing the command $f + 3$, python will first search for an __add__ method in class int that can support a second operand of type polynomial (self = int, other = polynomial). If such method does not exist, python will then search for an __radd__ method in class polynomial that can support a second operand of type int (self= polynomial, other = int). If such method does not exist, an exception is thrown.
Since + is commutative, then we set __radd__ to be identical to __add__
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms[0] += other
return Polynomial(terms)
#else, other is a polynomial
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
__radd__ = __add__ #to allow int+Polynomial
f = Polynomial([1, 1])
1 + f
(2*x^0) + (1*x^1)
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms[0] += other
return Polynomial(terms)
#else, other is a polynomial
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
__radd__ = __add__ #to allow int+Polynomial
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
f = Polynomial([1, 1])
-f
(-1*x^0) + (-1*x^1)
Using the fact we already have __neg__ and __add__ we define $f-g = f + (-g)$
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms[0] += other
return Polynomial(terms)
#else, other is a polynomial
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
__radd__ = __add__ #to allow int+Polynomial
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
def __sub__(self, other):
assert isinstance(other, (int, Polynomial))
return (self + (-other))
f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
g - f
g - 1
(1*x^0) + (2*x^1) + (4*x^2)
(1*x^0) + (3*x^1) + (4*x^2)
Using the fact we already have __neg__ and __sub__ we define $f-g = -(g-f)$
since oprator - is not commutative, then we cannot set __rsub__ to be identical to __sub__
Note that the following implementation of __rsub__ is promlematic, because it will keep calling itself (infinitely)
def __rsub__(self, other):
return other-self #PROBLEMATIC!
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms[0] += other
return Polynomial(terms)
#else, other is a polynomial
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
__radd__ = __add__ #to allow int+Polynomial
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
def __sub__(self, other):
assert isinstance(other, (int, Polynomial))
return (self + (-other))
#__rsub__ = __sub__ #not what we want...
def __rsub__(self, other):
# other - self
return -(self - other) #why not just other-self ?
f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
1 - f
1 - g
(-1*x^1)
(-1*x^0) + (-3*x^1) + (-4*x^2)
A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a "pointer" to the next node in the list.
Linked lists support operations such as insertion, deletion, search and many more.
class Node():
def __init__(self, val):
self.value = val
self.next = None
def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"
#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"
class Linked_list():
def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:
self.add_at_start(x)
def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out
def __len__(self):
''' called when using Python's len() '''
return self.len
def add_at_start(self, val):
''' add node with value val at the list head '''
p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def add_at_end(self, val):
''' add node with value val at the list tail '''
p = self
while (p.next != None):
p = p.next
p.next = Node(val)
self.len += 1
def insert(self, loc, val):
''' add node with value val after location 0<=loc<len of the list '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def __getitem__(self, loc):
''' called when using L[i] for reading
return node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
return p
def __setitem__(self, loc, val):
''' called when using L[loc]=val for writing
assigns val to node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
p.value = val
return None
def find(self, val):
''' find (first) node with value val in list '''
p = self.next
# loc = 0 # in case we want to return the location
while p != None:
if p.value == val:
return p
else:
p = p.next
#loc=loc+1 # in case we want to return the location
return None
def delete(self, loc):
''' delete element at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
# p is the element BEFORE loc
p.next = p.next.next
self.len -= 1
def insert_ordered(self, val):
''' assume self is an ordered list,
insert Node with val in order '''
p = self
q = self.next
while q != None and q.value < val:
p = q
q = q.next
newNode = Node(val)
p.next = newNode
newNode.next = q
self.len += 1
def find_ordered(self, val):
''' assume self is an ordered list,
find Node with value val '''
p = self.next
while p != None and p.value < val:
p = p.next
if p != None and p.value == val:
return p
else:
return None
Converting a string to a list
L= Linked_list("abc")
L
[a,91843024] [b,91843088] [c,91842992]
memory view
Adding elements one by one. Try using Python tutor.
l = Linked_list()
l.add_at_start("a")
l.add_at_start("b")
l
[b,91843568] [a,91843664]
Method | List | Linked list |
init | $O(1)$ | $O(1)$ |
init with $k$ items | $O(k)$ | $O(k)$ |
for the rest of the methods we assume that the structure contains $n$ items | ||
add at start | $O(n)$ | $O(1)$ |
add at end | $O(1)$ | $O(n)$ |
$lst[k]$ (get the $k$th item) | $O(1)$ | $O(k)$ |
delete $lst[k]$ | $O(n-k)$ | $O(k)$ |
Reversing a linked list in $O(1)$ additional memory. See the code and demo here
class Node():
def __init__(self, val):
self.value = val
self.next = None
def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"
#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"
class Linked_list():
def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:
self.add_at_start(x)
def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out
def __len__(self):
''' called when using Python's len() '''
return self.len
def add_at_start(self, val):
''' add node with value val at the list head '''
p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def add_at_end(self, val):
''' add node with value val at the list tail '''
p = self
while (p.next != None):
p = p.next
p.next = Node(val)
self.len += 1
def insert(self, loc, val):
''' add node with value val after location 0<=loc<len of the list '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def __getitem__(self, loc):
''' called when using L[i] for reading
return node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
return p
def __setitem__(self, loc, val):
''' called when using L[loc]=val for writing
assigns val to node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
p.value = val
return None
def find(self, val):
''' find (first) node with value val in list '''
p = self.next
# loc = 0 # in case we want to return the location
while p != None:
if p.value == val:
return p
else:
p = p.next
#loc=loc+1 # in case we want to return the location
return None
def delete(self, loc):
''' delete element at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
# p is the element BEFORE loc
p.next = p.next.next
self.len -= 1
def insert_ordered(self, val):
''' assume self is an ordered list,
insert Node with val in order '''
p = self
q = self.next
while q != None and q.value < val:
p = q
q = q.next
newNode = Node(val)
p.next = newNode
newNode.next = q
self.len += 1
def find_ordered(self, val):
''' assume self is an ordered list,
find Node with value val '''
p = self.next
while p != None and p.value < val:
p = p.next
if p != None and p.value == val:
return p
else:
return None
def reverse(self):
prev = None
curr = self.next
while curr != None:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
self.next = prev
ll = Linked_list("abc")
ll
ll.reverse()
ll
[a,91941296] [b,91941232] [c,91941200]
[c,91941200] [b,91941232] [a,91941296]
Exam question (2018, Spring Semester)
Let $L,K$ be two linked lists of length $n,m$ respectively. We say that the lists merge if there exists a node that is on both lists.
I.e. - there exists a node $q$ in $L$ and $p$ in $K$ such that $q ~is~ p == True$. In such a case we call $p$ a joint node.
Write a function $are\_merged$ that gets two linked lists as an input and returns True iff the lists merge.
The main idea - two linked lists merge if and only if their last node (their tail) is the same node.
def are_merged(L, K):
node_l = L.next
node_k = K.next
while node_l.next != None:
node_l = node_l.next
while node_k.next != None:
node_k = node_k.next
return node_k is node_l
#Here is an equivalent solution with a shorter code:
#last_node_l = L[len(L)-1]
#last_node_k = K[len(K)-1]
#return last_node_l is last_node_k
L = Linked_list("abcd")
L
K = Linked_list()
K.next = L.next.next.next
# Manually define the length of K
K.len = 2
K.add_at_start("e")
K
M = Linked_list()
M.add_at_start("d")
M
print(are_merged(L,K))
print(are_merged(L,M))
[a,2582652271360] [b,2582652268728] [c,2582652271808] [d,2582652268840]
[e,2582652270800] [c,2582652271808] [d,2582652268840]
[d,2582652629344]
True False
Space: Saving a pointer to two nodes can be done in $O(1)$ memory Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$
Next, write a function $find\_shared$ that gets two merged linked lists as an input and returns the first joint node of the lists.
Analyze its running time and space complexity.
def find_shared_1(L, K):
id_set = set()
p = L.next
while p != None:
id_set.add(id(p))
p = p.next
q = K.next
while q != None:
if id(q) in id_set:
return q
q = q.next
return None # should not reach here since L, K have joint items
def find_shared_2(L, K):
n = len(L)
m = len(K)
p = L.next
q = K.next
for i in range(max(0, n-m)):
print('advp')
p = p.next
for i in range(max(0, m-n)):
print('advq')
q = q.next
while p != None:
if p is q:
return p
p = p.next
q = q.next
return None # Should never get here
def find_shared_3(L, K):
p = L.next
q = K.next
while p != None and q != None:
if p is q:
return p
p = p.next
q = q.next
if p == None:
p = K.next
if q == None:
q = L.next
return None # must end before, since L, K have joint items
L = Linked_list("abcd")
L
K = Linked_list()
K.next = L.next.next.next
# Save the first joint node
x = K.next
K.len = 2
K.add_at_start("e")
K
M = Linked_list()
M.add_at_start("d")
M
print(are_merged(L,K))
print(are_merged(L,M))
print(find_shared_1(L,K), find_shared_1(L,K) == x)
print(find_shared_2(L,K), find_shared_2(L,K) == x)
print(find_shared_3(L,K), find_shared_3(L,K) == x)
[a,91940784] [b,91940624] [c,91940592] [d,91940272]
[e,91940432] [c,91940592] [d,91940272]
[d,1901584]
True False advp advp [c,91940592] True [c,91940592] True [c,91940592] True
For the analysis assume wlog that $n \geq m$: