class Node: def __init__(self, val): self.value = val self.next = None def __repr__(self): return str(self.value) node1 = Node(1) node2 = Node(2) node1.next = node2 node3 = Node(3) node2.next = node3 class LinkedList: def __init__(self): self.first = None def __repr__(self): out = "[" curr = self.first while curr: out += str(curr) + ", " curr = curr.next return out[:-2] + "]" lst = LinkedList() lst.first = node1 lst class LinkedList: def __init__(self): self.first = None def __repr__(self): out = "[" curr = self.first while curr: out += str(curr) + ", " curr = curr.next return out[:-2] + "]" def length(self): curr = self.first i = 0 while curr: i += 1 curr = curr.next return i def prepend(self, value): node = Node(value) if not self.first: self.first = node else: self.first, node.next = node, self.first def append(self, value): node = Node(value) curr = self.first if not curr: self.first = node else: while curr.next: curr = curr.next curr.next = node def insert(self, index, value): curr = self.first for i in range(index - 1): if not curr or not curr.next: raise IndexError() curr = curr.next node = Node(value) curr.next, node.next = node, curr.next def remove(self, index): curr = self.first # iterate to the one before the one to be removed for i in range(index - 1): if not curr or not curr.next: raise IndexError curr = curr.next curr.next = curr.next.next def get(self, index): curr = self.first for i in range(index): if not curr or not curr.next: raise IndexError curr = curr.next return curr.value def index(self, value): curr = self.first i = 0 while curr: if curr.value == value: return i curr = curr.next i += 1 raise ValueError() node1 = Node(1) node2 = Node(2) node1.next = node2 node3 = Node(3) node2.next = node3 lst = LinkedList() lst.first = node1 print(lst) print(lst.length()) lst.prepend(0) print(lst) lst.append(4) print(lst) lst.insert(2, 1.5) print(lst) lst.remove(2) print(lst) print(lst.get(2)) print(lst.index(2)) def reverse(lst): prev = None curr = lst.first while curr: curr.next, prev, curr = prev, curr, curr.next lst.first = prev print(lst) reverse(lst) print(lst) class QueueList: def __init__(self): self.lst = [] def __repr__(self): return self.lst.__repr__() def push(self, value): self.lst.append(Node(value)) def pop(self): return self.lst.pop(0) q1 = QueueList() q1.push(1) q1.push(2) q1.push(3) print(q1.pop()) q1 class QueueLinkedList: def __init__(self): self.head = None def __repr__(self): out = "[" curr = self.head while curr: out += str(curr) + ", " curr = curr.next return out[:-2] + "]" def push(self, value): node = Node(value) if self.head == None: self.head = node else: self.head, node.next = node, self.head def pop(self): if self.head != None: curr, prev = self.head, None while curr.next: curr, prev = curr.next, curr prev.next = None return curr.value q2 = QueueLinkedList() q2.push(1) q2.push(2) q2.push(3) print(q2.pop()) q2 q1 = QueueList() q2 = QueueLinkedList() for i in range(10**5): q1.push(1) q2.push(1) %timeit -n 100 q1.push(1) %timeit -n 100 q2.push(1) %timeit -n 100 q1.pop() %timeit -n 100 q2.pop() class TailedQueueLinkedList: def __init__(self): self.head = None self.tail = None def __repr__(self): out = "[" curr = self.head while curr: out += str(curr) + ", " curr = curr.next if len(out) > 2: out = out[:-2] return out + "]" def push(self, value): node = Node(value) if self.head == None: # empty queue self.head, self.tail = node, node else: # push to the tail. can you think of a way to push from the head? where will you pop from? self.tail.next, self.tail = node, node def pop(self): # pop from the head if self.head != None: node = self.head self.head = self.head.next return node.value q3 = TailedQueueLinkedList() q3.push(1) q3.push(2) q3.push(3) print(q3.pop()) q3 q1 = QueueList() q2 = QueueLinkedList() q3 = TailedQueueLinkedList() for i in range(10**5): q1.push(1) q2.push(1) q3.push(1) %timeit -n 100 q1.push(1) %timeit -n 100 q2.push(1) %timeit -n 100 q3.push(1) %timeit -n 100 q1.pop() %timeit -n 100 q2.pop() %timeit -n 100 q3.pop() class A: def __init__(self): self.values = [1,2,3,4] def __repr__(self): return str(self.values) a = A() print(a) for x in a: print(x) class A: ''' using the built-in iterator of list ''' def __init__(self): self.values = [1,2,3,4] def __repr__(self): return str(self.values) def __iter__(self): #now A is iterable return iter(self.values) #returns the iterator class of a list a = A() for x in a: print(x) class B: ''' using our own iterator class: BIterator ''' def __init__(self): self.values = [1,2,3,4] self.counts = [3,4,0,1] def __repr__(self): return str(self.values) + "\n" + str(self.count) def __iter__(self): return BIterator(self.values, self.counts) class BIterator(): ''' iterator of B, must have __next__ ''' def __init__(self, values, counts): self.index = 0 self.lst = [values[i] for i in range(len(values)) for j in range(counts[i])] def __next__(self): if self.index < len(self.lst): res = self.lst[self.index] self.index += 1 return res raise StopIteration b = B() for x in b: print(x, end=", ") class C: ''' a generator example using yield ''' def __init__(self): self.values = [1,2,3,4] self.counts = [3,4,0,1] def __repr__(self): return str(self.values) + "\n" + str(self.count) def __iter__(self): for i in range(len(self.values)): for j in range(self.counts[i]): yield self.values[i] c = C() for x in c: print(x, end=", ") for i in list(range(10**8)): pass for i in range(10**8): pass def natural_numbers(): n = 0 while True: n += 1 yield n for n in natural_numbers(): if n % 667 == 0 and n**2 % 766 == 0: break print(n) evens_less_than_1e6_list = [x for x in range(1, 10**6) if x % 2 == 0] %timeit -n 3 [x for x in range(1, 10**6) if x % 2 == 0] evens_less_than_1e6_generator = (x for x in range(1, 10**6) if x % 2 == 0) %timeit -n 3 (x for x in range(1, 10**6) if x % 2 == 0) import sys sys.getsizeof(evens_less_than_1e6_list), sys.getsizeof(evens_less_than_1e6_generator)