# 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"
An abstract data type (ADT) defines a conceptual model for how data may be stored and accessed.
A list ADT is a data container where:
Other common ADTs (some of which we'll explore later) include:
A list data structure is a concrete implementation of the list ADT in some programming language, which, in addition to adhering to the basic premises of the ADT, will also typically support operations that:
The implementation of any data structure will generally rely on simpler, constituent data types (e.g., "primitive" types offered by the language), the choice of which may affect the runtime complexities of said operations.
class List: # python class
# any variable prefixed by self. is an instance attribute
# any method with first argument self is an instance method
# we can call methods of a class by instantiating and object
# and then call the method on the object using objectVariable.methodname
# if calling one instance method within another one, use self.methodname
### subscript-based access ###
def __getitem__(self, idx): # validate idx
"""Implements `x = self[idx]`""" # self. __getitem__(idx)
pass
def __setitem__(self, idx, value): # validate idx
"""Implements `self[idx] = x`"""
pass
def __delitem__(self, idx): # validate idx
"""Implements `del self[idx]`"""
pass
### stringification ###
def __repr__(self): # reveals more of the actual implementation of the object
# however in all our data structure repr will call str
"""Supports inspection"""
return '[]'
def __str__(self): # like toString
"""Implements `str(self)`"""
return '[]'
### single-element manipulation ###
def append(self, value):
pass
def insert(self, idx, value):
pass
def pop(self, idx=-1):
pass
def remove(self, value):
pass
### predicates (T/F queries) ###
def __eq__(self, other):
"""Implements `self == other`"""
return True
def __contains__(self, value):
"""Implements `val in self`"""
return True
### queries ###
def __len__(self):
"""Implements `len(self)`"""
return self.size
def min(self):
pass
def max(self):
pass
def index(self, value, i, j):
pass
def count(self, value):
pass
### bulk operations ###
def __add__(self, other): # returns new list
"""Implements `self + other_array_list`"""
return self
def clear(self):
pass
def copy(self):
pass
def extend(self, other): # other can be any sequence type
# anything iterable
pass
### iteration ###
def __iter__(self):
"""Supports iteration (via `iter(self)`)"""
pass
For the ArrayList's underlying data storage mechanism you will use the NumPy array. You will be using a very limited subset of the available APIs for working with NumPy arrays, however. Specifically, you may use:
empty for creating empty arrays. You will be calling it like this (assuming the numpy library has been imported as np, as we always do): np.empty(N, dtype=object). This will create an empty array of size N, each slot of which can be used to store a reference to an arbitrary Python object.
Valid, positive indexes into arrays. It will be your job in the implementation of ArrayList to check for valid indexes and to translate negative indexes into positive ones.
len(arr) to get the length (i.e., number of slots) of array arr. Note that this will not generally coincide with the number of actual elements in the list!
You should not use any other array-related functions provided by NumPy! Notably, delete, insert append, resize, and others, are off limits. Using them to carry out list operations is, generally speaking, less efficient than the manual approach outlined in class. Also, it's important that you learn how to implement them yourself. Breaking this rule will result in significant score reduction(s).
# what is runtime of each of these
# creating an empty NumPy array. O(1) constant
# access an index postion [] in NumPy array. O(1) constant
# get the length of a NumPy array. O(1) constant
ArrayList data structure¶import numpy as np
class ArrayList:
def __init__(self): # constructor in python
# default arraylist size is 1 element
self.data = np.empty(1, dtype=object) # array variable name is "data"
self.size = 0 # how many items have been addded to the arrayList
# also tells us where to put the next item
# not the same as len(self.data)
# myList = ArrayList() calls __init__
def append(self, value):
# how do we append an item after the last item in the arraylist
# just put the item at the next index position
# if not fit, make a bigger array, copy over, then append
if self.size<len(self.data): # O(1)
self.data[self.size]=value
self.size+=1
else: # iteration needed for copy, slow
# options to make one larger, but then every append
# needs to do a O(self.size) copy of items O(n)
# instead assume more appends are coming, and make array much larger
# so this one append is slow, but future appends are fast
# accepted larger is twice as big
newArray = np.empty(len(self.data)*2, dtype=object)
# iterate over all the items in self.data
# copy them to same position in newArray
for i in range(len(self.data)):
newArray[i]=self.data[i]
newArray[self.size]=value
self.size+=1
self.data=newArray
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
# later implement error checking is idx valid (0 to self.size-1)
# later also support negative idx
# if they give us a valid index
idx=self.normalize_idx(idx) # correcting negative index
if idx<0 or idx>=self.size:
raise IndexError()
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
# if they give us a valid index
assert(isinstance(idx, int))
self.data[idx]=value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
# don;t erase it or cross it out, don;t leave a hole
# move the items after the deleted item, up one
# shifting items
# if they give us a valid index
for i in range(idx, self.size-1): #len(self.data)
# i is the position we are moving to
#i+1 is the position we are moving from
self.data[i]=self.data[i+1]
self.data[self.size-1]=None
self.size-=1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
value='['
for i in range(self.size):
value+=str(self.data[i])
if i<self.size-1:
value+=', '
value+=']'
return value
def normalize_idx(self, idx):
# error checking on out of range will be in get, set, del, insert
# will be done in those methods
# here we just fix the negative index
# corrects index from -1 to -N
# to index N-1 to 0
# we cannot do range checking here, because insert allows N as a valid index
newIdx=idx
if newIdx<0:
newIdx+=self.size
# what if newIdex is still negative?
# what if user gives -2N
# change the if to a while and get newIdx from 0 to N-1
# OR if still negative, set newIdx to 0
if newIdx<0:
newIdx=0
return newIdx
m = ArrayList()
m
[]
m.append(5)
m
[5]
m.append(-1)
m
[5, -1]
m[1]
-1
m[0]
5
m[1]=12
m
[5, 12]
len(m)
2
m.append(44)
m.append(45)
m.append(46)
m.append(47)
m
[5, 12, 44, 45, 46, 47]
del m[1]
m
[5, 44, 45, 46, 47]
del m[0]
m
[44, 45, 46, 47]
del m[3]
m
[44, 45, 46]
m[-2]
m[-3]
45
44
m[-1]
46
m[-4]
44
m[12]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-18-587e96a96ed8> in <module> ----> 1 m[12] <ipython-input-3-08eb1c722bd4> in __getitem__(self, idx) 41 idx=self.normalize_idx(idx) # correcting negative index 42 if idx<0 or idx>=self.size: ---> 43 raise IndexError() 44 return self.data[idx] 45 IndexError:
m['matt']
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-19-cf9079c0b033> in <module> ----> 1 m['matt'] <ipython-input-3-08eb1c722bd4> in __getitem__(self, idx) 35 def __getitem__(self, idx): 36 """Implements `x = self[idx]`""" ---> 37 assert(isinstance(idx, int)) 38 # later implement error checking is idx valid (0 to self.size-1) 39 # later also support negative idx AssertionError:
m[12]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-21-587e96a96ed8> in <module> ----> 1 m[12] <ipython-input-8-e895c39db345> in __getitem__(self, idx) 39 # later also support negative idx 40 # if they give us a valid index ---> 41 return self.data[idx] 42 43 IndexError: index 12 is out of bounds for axis 0 with size 8
m[-1]
m[3]
m
[44, 45, 46]