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.
Reference reading: http://interactivepython.org/courselib/static/pythonds/Introduction/WhyStudyDataStructuresandAbstractDataTypes.html
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 len(self.data)
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
l = List()
l.append('x')
l[0]
len(l)
class List:
def __init(self):
self.data = 0
def append(self, value):
self.data = value
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
return self.data
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
self.data = value
def __repr__(self):
"""Supports inspection"""
return '[' + str(self.data) + ']'
l = List()
l.append(10)
l
l.append('x')
l
l[0]
l[0] = 20
l
len(l)
list
as array¶To use the built-in list as though it were a primitive array, we will constrain ourselves to just the following APIs on a given list lst
:
lst[i]
for getting and setting values at an existing, positive index i
len(lst)
to obtain the number of slotslst.append(None)
to grow the list by one slot at a timedel lst[len(lst)-1]
to delete the last slot in a listl = []
l[0] = 10 #not permitted
l.append(None)
l[0] = 10
l[0]
l # not permitted
l.append(None)
l[1] = 20
l[0], l[1]
del lst[len(lst)-1] #delete one by one in the reverse order
ArrayList
data structure¶class ArrayList:
def __init__(self):
self.data = []
pass
def append(self, value):
pass
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
pass
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
pass
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
pass
def __len__(self):
"""Implements `len(self)`"""
pass
def __repr__(self):
"""Supports inspection"""
pass
class ArrayList:
def __init__(self):
self.data = []
def append(self, value):
self.data.append(None)
self.data[len(self.data)-1] = value
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
self.data[idx] = value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
for i in range(idx, len(self)-1): #len(), __getitem()__ already implemented
self[i] = self[i+1] #shift elements after i one position ahead
del self.data[len(self.data)-1]
def __len__(self):
"""Implements `len(self)`"""
return len(self.data)
def __repr__(self):
"""Supports inspection"""
pass
l = ArrayList()
for i in range(10):
l.append(i)
l[0], l[5], l[9]
l
l.data
del l[5]
l.data