# 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 0x1973b32dd60>]
# 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: O(?) linear in the total number of items
for x in arr2: # O(len(arr2))
arr1.append(x) # each one is O(1) except when arr1 fills up and then we need O(len(arr1))
return arr1
# option 2: O(?) linear in the total number of items, probably uses append repeatedly
arr1.extend(arr2)
return arr1
# option 3: O(?) O(len(arr1)) + O(len(arr2))
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" 2 element lists, the position [0] will store some data,
#the position [1] will store a link (pointer, address), to another list
l1 = [i1,None]
l2 = [i2,None]
l3 = [i3,None]
l4 = [i4,None]
l1
['lions', None]
# link-ing them together
# l1[1] we want that to Point to the l2 list
l1[1]=l2
l2[1]=l3
l3[1]=l4
l1
['lions', ['tigers', ['bears', ['oh, my', None]]]]
l3
['bears', ['oh, my', None]]
# iteration
def link_iter(head): # head is usually the variable name for pointer to where we want to start iteration
while head: # fails when head==None
yield head[0] # when we switch to node objects head.val
head=head[1] # when we switch to node objects head.next
for x in link_iter(l1):
print(x)
lions tigers bears oh, my
for x in link_iter(l3):
print(x)
bears oh, my
# prepending O(1), does not depend on length of the list, fixed the array prepend O(n) issue
i0 = 'walruses'
l0=[i0, l1 ] #prepends the l0 list object in front of the l1 list object
for x in link_iter(l0):
print(x)
walruses lions tigers bears oh, my
# insertion between l2 and l3
# need to make l2[1] point to l2_5 and make l2_5[1] point to l3
i2_5 = 'elephants'
l2_5 = [i2_5, None]
l2[1] = l2_5
l2_5[1] =l3 # or l2[1]
for x in link_iter(l0):
print(x)
walruses lions tigers elephants bears oh, my
# if we did not have l3 variable (in final implementation we will only have a pointer to the head)
i2_5 = 'elephants'
l2_5 = [i2_5, None]
l2_5[1] = l2[1] # we need to fix the pointer for the new list first
l2[1] = l2_5
# deletion delete the item between l0 and l2
#l0[1]=l2 # l0[1] used to point to l1, nothing now is pointing to l1, l1 goes away
#l0[1]=l1[1]
l0[1]=l0[1][1] # not using any variable other than l0 the head
for x in link_iter(l0):
print(x)
walruses tigers elephants elephants bears oh, my
l1 #not reachable from the head, but is still pointing to the lists after it
['lions', ['tigers', ['elephants', ['elephants', ['bears', ['oh, my', None]]]]]]
class Node: #instead a list of [0] data and [1] pointer to next item
def __init__(self, val, next=None):
self.val = val
self.next = next
# manually constructing a list
head=Node(i1, None)
head.val
head.next
'lions'
head.next=Node(i2,None)
head.val
head.next
head.next.val
'lions'
<__main__.Node at 0x197391afdf0>
'tigers'
head.next.next=Node(i3,None)
head.val
head.next.val
head.next.next.val
'lions'
'tigers'
'bears'
# iteration
def node_iter(n): # head is usually the variable name for pointer to where we want to start iteration
while n: #initially, n==head
yield n.val
n=n.next
head.val
for x in node_iter(head):
print(x)
head.val
'lions'
lions tigers bears
'lions'
# prepending
# O(1) we do not need to walk the list
def prepend(l, val): # l is a pointer to the head of a list, val is the value to insert at new head
# and I want prepend to return a pointer to the new head
temp = Node(val, None) #make the new node
temp.next = l # make this new node point to the old head of the list
return temp
head=prepend(head, 'Matt')
for x in node_iter(head):
print(x)
Matt lions tigers bears
head=prepend(head, 'dog')
for x in node_iter(head):
print(x)
dog Matt lions tigers bears
class LinkedList:
class Node:
def __init__(self, val, next=None): # this self is a Node object
self.val = val
self.next = next
def __init__(self):
self.head = None
def prepend(self, val):
self.head = LinkedList.Node(val, self.head)
def __iter__(self): #since it contains a yield call, this is a generator iterator
n=self.head # n is the pointer to walk the list, we cannot change self.head
while n: # stops when n is None so you could say while n!=None
yield n.val
n=n.next
def __repr__(self):
return '[' + ', '.join(str(x) for x in self) + ']' # this self is a LinkedList object
l = LinkedList()
for x in range(10):
l.prepend(x)
l #calls repr
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]