# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from timeit import timeit
def time_array_front_insert_delete(n):
return timeit('lst.insert(0, None) ; del lst[0]',
'lst = list(range({}))'.format(n),
number=1000)
ns = np.linspace(100, 10000, 50)
plt.plot(ns, [time_array_front_insert_delete(int(n)) for n in ns], 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x1defd91ad60>]
# consider:
def concatenate(arr1, arr2):
"""Concatenates the contents of arr1 and arr2 as efficiently (time-wise)
as possible, so that the resulting structure can be used to index all
combined elements (arr1's followed by arr2's)."""
# option 1: worst case O(size arr2 * size arr1)
for x in arr2: # size of arr2
arr1.append(x) # sometimes O(1) when there is room, sometimes O(size arr1) when there is no room
return arr1
# option 2: O(?) worst case O(size arr2 * size arr1)
arr1.extend(arr2)
return arr1
# option 3: O(?) worst case O(size arr2 * size arr1)
return arr1 + arr2
We would like a new data storage mechanism for constructing data structures that:
# data items
i1 = 'lions'
i2 = 'tigers'
i3 = 'bears'
i4 = 'oh, my'
# creating individual "links"
l1 = [i1,None]
l2 = [i2,None]
l3 = [i3,None]
l4 = [i4,None]
l1
l2
l3
l4
['lions', None]
['tigers', None]
['bears', None]
['oh, my', None]
l1[0]
l1[1]
'lions'
# link-ing them together
l1[1]=l2
l2[1]=l3
l3[1]=l4
l1
l2
l3
l4
['lions', ['tigers', ['bears', ['oh, my', None]]]]
['tigers', ['bears', ['oh, my', None]]]
['bears', ['oh, my', None]]
['oh, my', None]
# iteration
def link_iter(head): # since it has a yield it is a generator function
# head is a two element list [0] is data [1] is link to the next list
while head:
yield head[0]
head=head[1]
for j in link_iter(l0):
print(j)
walruses lions tigers elephants bears oh, my
l1
['lions', ['tigers', ['bears', ['oh, my', None]]]]
# prepending
i0 = 'walruses'
l0=[i0, l1]
l0
['walruses', ['lions', ['tigers', ['bears', ['oh, my', None]]]]]
# insertion
i2_5 = 'elephants'
l2_5=[i2_5,None]
l2_5
['elephants', None]
l2_5[1]=l2[1] #l2[1] points to l3, you should not assuem you have l3
l2[1]=l2_5 # tigers list points to elephant list
#l2_5[1]= l3 #elephant list points to bears list
l0
['walruses', ['lions', ['tigers', ['elephants', ['bears', ['oh, my', None]]]]]]
# deletion
#need a pointer to the element before the one you want to delete
#walruses l0
#lions l1
#tigers l2
#elephants l3
#bears l4
#oh, my l5
#delete l2, we actually need a pointer to the node before it, I need l1
# assuming allwe have is l0, I can walk to l1n
nodeBefore = l0[1]
nodeToDelete=nodeBefore[1]
nodeBefore[1]=nodeToDelete[1]
for j in link_iter(l0):
print(j)
walruses lions elephants bears oh, my
class Link:
def __init__(self, val, next=None):
self.val = val
self.next = next
# manually constructing a list
i1 = 'lions'
i2 = 'tigers'
i3 = 'bears'
i4 = 'oh, my'
head=Link(i1,Link(i2,Link(i3,Link(i4))))
head
head.val
head.next
head.next.val
<__main__.Link at 0x252c7a85760>
'lions'
<__main__.Link at 0x252c7a85940>
'tigers'
# prepending
def prepend(l, val): # l is head of a list, val is value to insert in Link object at the beginning
return Link(val, l)
l = None
for x in range(10):
l=prepend(l, x)
# iterator
def link_iterator(lst):
while lst!=None: # while lst
yield lst.val
lst=lst.next
for x in link_iterator(l):
print(x)
9 8 7 6 5 4 3 2 1 0
# iteration based on a recursive pattern
def link_iterator_rec(l):
yield
for x in link_iterator_rec(l):
print(x)
class LinkedList:
class Node:
def __init__(self, val, next=None): # constructor for Node object
self.val = val
self.next = next
def __init__(self): #constructor for LinkedList objects
self.head = None
def prepend(self, val):
self.head = self.Node(val, self.head)
def __iter__(self):
n=self.head #only execute once
while n:
yield n.val
n=n.next
def __repr__(self):
return '[' + ', '.join(str(x) for x in self) + ']'
l = LinkedList()
for x in range(10):
l.prepend(x)
l #calls __repr__
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]