# 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 0x1e7700acd60>]
# 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(len(arr2)) assuming room in arr1 so append is O(1)
# and assuming if not room, I rarely need to grow arr1
# amortized O(1)
for x in arr2:
arr1.append(x)
return arr1
# option 2: O(len(arr2))
arr1.extend(arr2) # extend does option 1
return arr1
# option 3: O(len(arr1) + len(arr2) )
return arr1 + arr2 # __add__ creates a new arraylist
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
l1 = [i1,None ]
# 0 1
l2 = [i2, None]
l3 = [i3, None]
l4 = [i4,None]
# link-ing them together
l1[1]=l2
l2[1]=l3
l3[1]=l4
l1
['lions', ['tigers', ['bears', ['oh, my', None]]]]
# iteration
def link_iterator(head):
while head: # while head != None
yield head[0] # data
head=head[1] # link to next item
for x in link_iterator(l1):
print(x)
lions tigers bears oh, my
# prepending O(1)
i0 = 'walruses'
l0=[i0,l1]
for x in link_iterator(l0):
print(x)
walruses lions tigers bears oh, my
for x in link_iterator(l2):
print(x)
tigers bears oh, my
l0
['walruses', ['lions', ['tigers', ['bears', ['oh, my', None]]]]]
# insertion O(1)
i2_5 = 'elephants'
l2_5 = [i2_5, l3] # or l2_5 = [i2_5, l2[1] ]
l2[1]=l2_5
for x in link_iterator(l0):
print(x)
walruses lions tigers elephants bears oh, my
# deletion O(1) as long as we have pointer to predecessor
l1[1]= l2[1]
l2[1]=None
for x in link_iterator(l0):
print(x)
walruses lions elephants bears oh, my
l2
['tigers', None]
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
# manually constructing a list, only use one pointer to first element
# and repeatedly prepend new elements
head = Node(i4)
head = Node (i3, head)
head = Node (i2, head)
head = Node (i1, head)
head
<__main__.Node at 0x1e76df3f6d0>
def node_iterator(list_pointer):
while list_pointer:
yield list_pointer.val # data
list_pointer=list_pointer.next # link to next item
for x in node_iterator(head):
print (x)
lions tigers bears oh, my
head
<__main__.Node at 0x1e76df3f6d0>
# prepending .val and .next
def prepend(l, val): # l is a pointer to the first Node in a list
return Node(val, l)
l = None
for x in range(10):
l = prepend(l, x)
for x in node_iterator(l):
print(x)
9 8 7 6 5 4 3 2 1 0
class LinkedList:
class Node:
def __init__(self, val, next=None): # constructor for Node
self.val = val
self.next = next
def __init__(self):# constructor for LinkedList
self.head = None # instance attirbute for a LinkedList
# is just a pointer to the head
def prepend(self, val):
self.head=LinkedList.Node(val, self.head)
def __iter__(self): # self is the linkedlist
# self.head is pointer to first element
list_pointer=self.head
while list_pointer:
yield list_pointer.val # data
list_pointer=list_pointer.next # link to next item
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]