列表和字典的常用函数及其实现方法
列表和字典是Python中两种非常常用的数据结构。它们都有一些常用的函数，下面就分别介绍一下它们的常用函数及其实现方法。
一、列表的常用函数
1. append()
语法：list.append(obj)
功能：在列表末尾添加一个新元素
实现方法：
def append(self, obj: Any) -> None:
self._resize(len(self) + 1) # 列表扩容
self._A[len(self)-1] = obj # 在末尾添加元素
2. extend()
语法：list.extend(iterable)
功能：在列表末尾添加一个可迭代的对象，如另一个列表或元组
实现方法：
def extend(self, iterable: Iterable) -> None:
for item in iterable:
self.append(item) # 遍历可迭代对象，依次添加到列表末尾
3. insert()
语法：list.insert(index, obj)
功能：在指定的位置插入一个新元素
实现方法：
def insert(self, index: int, obj: Any) -> None:
if index < 0:
index += len(self) # 将索引转换成正数
if index < 0:
index = 0 # 如果还是小于0，那么插入到列表最前面
if index > len(self):
index = len(self) # 如果超出列表范围，那么插入到列表末尾
self._resize(len(self) + 1) # 列表扩容
for i in range(len(self)-1, index-1, -1):
self._A[i+1] = self._A[i] # 将插入位置后面的元素依次向后移动
self._A[index] = obj # 在插入位置插入元素
4. remove()
语法：list.remove(obj)
功能：删除列表中第一个出现的指定元素
实现方法：
def remove(self, obj: Any) -> None:
for i in range(len(self)):
if self._A[i] == obj:
for j in range(i, len(self)-1):
self._A[j] = self._A[j+1] # 将后面的元素依次向前移动
self._A[len(self)-1] = None # 列表大小减1
self._n -= 1
5. pop()
语法：list.pop([index])
功能：删除并返回指定索引或最右边的元素
实现方法：
def pop(self, index: Optional[int] = None) -> Any:
if index is None:
index = len(self) - 1 # 如果没有指定索引，则删除最右边的元素
if index < 0:
index += len(self) # 将索引转换成正数
if index < 0 or index >= len(self):
raise IndexError('list index out of range') # 如果索引超出列表范围，抛出异常
obj = self._A[index] # 获取要删除的元素
for i in range(index, len(self)-1):
self._A[i] = self._A[i+1] # 将后面的元素依次向前移动
self._A[len(self)-1] = None # 列表大小减1
self._n -= 1
return obj
6. clear()
语法：list.clear()
功能：清空列表中的所有元素
实现方法：
def clear(self) -> None:
self._A = self._new_array(self._DEFAULT_CAPACITY) # 创建一个新的，大小为默认容量的列表
self._n = 0 # 列表大小为0
7. index()
语法：list.index(obj, start=0, end=len(list))
功能：返回列表中第一个出现指定元素的索引
实现方法：
def index(self, obj: Any, start: Optional[int] = 0, end: Optional[int] = None) -> int:
if end is None:
end = len(self) # 如果没有指定终止索引，则搜索整个列表
if start < 0:
start += len(self) # 将起始索引转换成正数
if end < 0:
end += len(self) # 将终止索引转换成正数
for i in range(start, end):
if self._A[i] == obj:
return i
raise ValueError(f'{obj} is not in list') # 如果没有找到指定元素，抛出异常
8. count()
语法：list.count(obj)
功能：返回指定元素在列表中出现的次数
实现方法：
def count(self, obj: Any) -> int:
count = 0
for item in self._A:
if item == obj:
count += 1
return count
9. reverse()
语法：list.reverse()
功能：将列表中的元素反转
实现方法：
def reverse(self) -> None:
for i in range(len(self)//2):
self._A[i], self._A[len(self)-1-i] = self._A[len(self)-1-i], self._A[i] # 交换对称位置的元素
10. sort()
语法：list.sort(key=None, reverse=False)
功能：将列表中的元素排序
实现方法：
def sort(self, key: Optional[Callable[[Any], Any]] = None, reverse: bool = False) -> None:
if key is None:
key = lambda x: x # 如果没有指定排序函数，那么默认使用元素本身作为排序标准
if len(self) > 1:
pivot = self._A[0]
low = [x for x in self[1:] if key(x) <= key(pivot)]
high = [x for x in self[1:] if key(x) > key(pivot)]
self._A = MyList(low)._A + [pivot] + MyList(high)._A # 将两个已排序的子列表按顺序拼接起来
if reverse:
self.reverse() # 如果需要降序排列，那么反转一下列表即可
二、字典的常用函数
1. clear()
语法：dict.clear()
功能：清空字典中的所有键值对
实现方法：
def clear(self) -> None:
self._table = self._make_table(self._M) # 创建一个新的空哈希表
self._n = 0 # 字典大小变为0
2. get()
语法：dict.get(key, default=None)
功能：返回与指定键相关联的值，如果键不存在则返回默认值
实现方法：
def get(self, key: Any, default: Optional[Any] = None) -> Optional[Any]:
i = self._hash_function(key)
for j in range(self._M):
if self._table[i] is None:
break
elif self._table[i][0] == key:
return self._table[i][1]
i = (i+1) % self._M
return default # 如果键不存在，则返回默认值
3. keys()
语法：dict.keys()
功能：返回字典中所有的键
实现方法：
def keys(self) -> List[Any]:
return [pair[0] for pair in self.items()] # 返回字典中所有键所构成的列表
4. values()
语法：dict.values()
功能：返回字典中所有的值
实现方法：
def values(self) -> List[Any]:
return [pair[1] for pair in self.items()] # 返回字典中所有值所构成的列表
5. items()
语法：dict.items()
功能：返回字典中所有的键值对
实现方法：
def items(self) -> List[Tuple[Any, Any]]:
return [(pair[0], pair[1]) for pair in self._table if pair is not None] # 返回字典中所有键值对所构成的列表
6. pop()
语