# 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:
### subscript-based access ###
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
pass
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
pass
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
pass
### stringification ###
def __repr__(self):
"""Supports inspection"""
return '[]'
def __str__(self):
"""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):
"""Implements `self + other_array_list`"""
return self
def clear(self):
pass
def copy(self):
pass
def extend(self, other):
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).
ArrayList data structure¶import numpy as np
class ArrayList:
def __init__(self): #constructor
self.data = np.empty(1, dtype=object) # new Object[1] of Null
# contains None
self.size = 0
def append(self, value):
if self.size==len(self.data):
newArray = np.empty(2*len(self.data), dtype=object)
# copy everything over
for i in range(0, self.size):
newArray[i]=self.data[i]
self.data=newArray
self.data[self.size]=value
self.size+=1
def __getitem__(self, idx): #assume valid 0<=idx<len(self.data)
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
return self.data[idx] #O(1)
def __setitem__(self, idx, value): #assume valid 0<=idx<len(self.data)
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
self.data[idx]=value #O(1)
def __delitem__(self, idx): #assume valid 0<=idx<len(self.data) #worst case O(n)
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
for i in range(idx+1,self.size): #first to move is idx+1, last to move is at self.size-1
self.data[i-1]=self.data[i]
self.data[self.size-1]=None
self.size-=1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
# [1, -4, 3] []
out="["
if self.size>0:
out=out+str(self.data[0])
for i in range(1, self.size):
out=out+", "+str(self.data[i])
out=out+"]"
return out
lst = ArrayList()
lst
[]
for i in range(5):
lst.append(i) #append
lst #repr
[0, 1, 2, 3, 4]
lst[3] #get
3
lst[2]=-1 #set
lst
[0, 1, -1, 3, 4]
len(lst)
5
del lst[0]
lst
[1, -1, 3, 4]
len(lst)
4
lst['a']
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-12-d58f87080c21> in <module> ----> 1 lst['a'] <ipython-input-4-50a4f2cd6394> in __getitem__(self, idx) 19 def __getitem__(self, idx): #assume valid 0<=idx<len(self.data) 20 """Implements `x = self[idx]`""" ---> 21 assert(isinstance(idx, int)) 22 return self.data[idx] #O(1) 23 AssertionError:
lst[7]
lst.data
array([1, -1, 3, 4, None, None, None, None], dtype=object)
lst[10]
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-17-655442512158> in <module> ----> 1 lst[10] <ipython-input-4-50a4f2cd6394> in __getitem__(self, idx) 20 """Implements `x = self[idx]`""" 21 assert(isinstance(idx, int)) ---> 22 return self.data[idx] #O(1) 23 24 def __setitem__(self, idx, value): #assume valid 0<=idx<len(self.data) IndexError: index 10 is out of bounds for axis 0 with size 8
import numpy as np
class ArrayList:
def __init__(self): #constructor
self.data = np.empty(1, dtype=object) # new Object[1] of Null
# contains None
self.size = 0
def append(self, value):
if self.size==len(self.data):
newArray = np.empty(2*len(self.data), dtype=object)
# copy everything over
for i in range(0, self.size):
newArray[i]=self.data[i]
self.data=newArray
self.data[self.size]=value
self.size+=1
def _normalize_idx(self, nidx): #helper function to translate a neg idx to pos idx
if nidx<0:
nidx+=self.size
if nidx<0:
nidx=0
return nidx
def __getitem__(self, idx): #assume valid 0<=idx<self.size
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
return self.data[idx] #O(1) only on positive index
def __setitem__(self, idx, value): #assume valid 0<=idx<self.size
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
self.data[idx]=value #O(1)
def __delitem__(self, idx): #assume valid 0<=idx<self.size #worst case O(n)
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
for i in range(idx+1,self.size): #first to move is idx+1, last to move is at self.size-1
self.data[i-1]=self.data[i]
self.data[self.size-1]=None
self.size-=1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
# [1, -4, 3] []
out="["
if self.size>0:
out=out+str(self.data[0])
for i in range(1, self.size):
out=out+", "+str(self.data[i])
out=out+"]"
return out
lst = ArrayList()
lst
for i in range(5):
lst.append(-1*i) #append
lst #repr
[]
[0, -1, -2, -3, -4]
lst[-1]
lst[-3]
lst[7]
-4
-2
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-20-5ca48497d51b> in <module> 1 lst[-1] 2 lst[-3] ----> 3 lst[7] <ipython-input-18-ecfce4f97ba2> in __getitem__(self, idx) 30 idx = self._normalize_idx(idx) # now the idx is non-negative 31 if idx>=self.size: ---> 32 raise IndexError() 33 return self.data[idx] #O(1) only on positive index 34 IndexError: