# 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 0x1c5667acd60>]
# 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(?)
for x in arr2:
arr1.append(x)
return arr1
# option 2: O(?)
arr1.extend(arr2)
return arr1
# option 3: O(?)
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] # l1 is at made up address 111111
# 0 1
l2 = [i2,None] # l2 is at made up address 123456
l3 = [i3,None] # l3 is at made up address 456456
l4 = [i4,None] # l4 made up address 98765
# each one of these lists has an address
l1
['lions', None]
l1[0]
l1[1]
'lions'
# link-ing them together
l1[1] = l2 # l1 = ["lions", 123456]
l1[0]
l1[1]
'lions'
['tigers', None]
l2[1] = l3
l3[1] = l4
l2
['tigers', ['bears', ['oh, my', None]]]
# iteration
def link_iter(head): # link_iter(l1)
while head: # while head != None
yield head[0]
head=head[1]
for i in link_iter(l1):
print(i)
lions tigers bears oh, my
for i in link_iter(l3):
print(i)
bears oh, my
# prepending O(1)
i0 = 'walruses'
l0=[i0, l1]
for i in link_iter(l0):
print(i)
walruses lions tigers bears oh, my
# insertion between 2 tigers and 3 bears O(1) no shifting of items afterward
i2_5 = 'elephants'
l2_5 = [i2_5, l2[1] ] # l2[1] is what l2 used to point to
l2[1]=l2_5 # change what l2 points to
for i in link_iter(l0):
print(i)
walruses lions tigers elephants bears oh, my
# deletion tiger make l1[1]point to what l2[1] points to O(1)
l1[1]=l2[1]
l2[1]=None
for i in link_iter(l0):
print(i)
walruses lions elephants bears oh, my
class Node: # replacing the 2 element lists with an Node object
def __init__(self, val, next=None):
self.val = val
self.next = next
# manually constructing a list
# prepending
def prepend(l, val):
pass
l = None
for x in range(10):
l = prepend(l, x)
# iterator
def node_iterator(lst):
yield
for x in node_iterator(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
self.head = None #only instance attribute for the linked list
# pointer to first node
self.count=0 # how many items in linkedlist
def prepend(self, val):
self.head=LinkedList.Node(val, self.head) # calling Node constructor
self.count+=1
def __iter__(self):
n=self.head # make a copy of what self.head points to, don't change self.head
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
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]