🍋数组（Array）
基本原理： 数组是一种线性数据结构，它在内存中是一段连续的存储空间。 数组通过索引（或下标）访问元素，索引从 0 开始递增。 所有元素的类型相同，占用的内存空间相等。 优点： 随机访问：可以通过索引快速访问任意位置的元素，时间复杂度为 O(1)。 索引计算简单：根据索引计算元素的内存地址很简单，只需一个乘法和一个加法操作。 缺点： 大小固定：数组的大小在创建时就固定了，无法动态调整。 插入和删除操作效率低：在数组中间插入或删除元素会涉及到大量元素的移动，时间复杂度为 O(n)。 内存空间的浪费：如果数组预留了很大的空间但只存储了少量元素，会造成内存空间的浪费。
🍋链表（Linked List）
基本原理： 链表是一种由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针（或引用）。 节点不必在内存中连续存储，通过指针将它们串联起来。 优点： 动态大小：链表的大小可以动态增长或缩小，不需要预先分配固定大小的空间。 插入和删除操作高效：在链表中插入或删除元素只需要改变指针的指向，时间复杂度为 O(1)。 缺点： 随机访问低效：要访问链表中的第 k 个元素，需要从头节点开始依次遍历，时间复杂度为 O(k)。 需要额外的空间存储指针：每个节点都需要额外的空间存储指向下一个节点的指针，占用的内存空间较大。
🍋代码实现
数组
from selenium.common import NoSuchElementException class MyArrayList: def __init__(self, init_capacity=1): self.data = [None] * init_capacity self.size = 0 # 在列表末尾添加元素 e。 # 如果列表已满，则调用 _resize 函数扩展列表的容量。 def add_last(self, e): cap = len(self.data) if self.size == cap: self._resize(2 * cap) self.data[self.size] = e self.size += 1 # 在指定索引 index 处插入元素 e。 # 如果列表已满，则调用 _resize 函数扩展列表的容量。 # 使用切片操作实现在 index 处插入元素，并将后续元素向后移动一个位置。 def add(self, index, e): self._check_position_index(index) cap = len(self.data) if self.size == cap: self._resize(2 * cap) self.data[index+1:self.size+1] = self.data[index:self.size] self.data[index] = e self.size += 1 # 在列表开头添加元素 e，实际上是调用 add(0, e)。 def add_first(self, e): self.add(0, e) # 移除并返回列表末尾的元素。 # 如果列表的大小为容量的四分之一，则调用 _resize 函数缩小列表的容量。 def remove_last(self): if self.size == 0: raise NoSuchElementException() cap = len(self.data) if self.size == cap // 4: self._resize(cap // 2) deleted_val = self.data[self.size - 1] self.data[self.size - 1] = None self.size -= 1 return deleted_val # 移除并返回指定索引 index 处的元素。 # 如果列表的大小为容量的四分之一，则调用 _resize 函数缩小列表的容量。 # 使用切片操作实现在 index 处移除元素，并将后续元素向前移动一个位置。 def remove(self, index): self._check_element_index(index) cap = len(self.data) if self.size == cap // 4: self._resize(cap // 2) deleted_val = self.data[index] self.data[index:self.size-1] = self.data[index+1:self.size] self.data[self.size - 1] = None self.size -= 1 return deleted_val # 移除并返回列表开头的元素，实际上是调用 remove(0)。 def remove_first(self): return self.remove(0) # 返回指定索引 index 处的元素。 def get(self, index): self._check_element_index(index) return self.data[index] # 将指定索引 index 处的元素设置为 element，并返回原始值。 def set(self, index, element): self._check_element_index(index) old_val = self.data[index] self.data[index] = element return old_val # 返回列表的大小。 def size(self): return self.size # 返回列表是否为空。 def is_empty(self): return self.size == 0 # 将列表的容量调整为 new_cap。 # 如果新容量小于当前大小，则不进行调整。 def _resize(self, new_cap): if self.size > new_cap: return temp = [None] * new_cap temp[:self.size] = self.data[:self.size] self.data = temp # 用于检查索引是否在有效范围内。 def _is_element_index(self, index): return 0 <= index < self.size def _is_position_index(self, index): return 0 <= index <= self.size # 用于检查索引是否在有效范围内，如果不在有效范围内，则抛出 IndexError。 def _check_element_index(self, index): if not self._is_element_index(index): raise IndexError("Index: " + str(index) + ", Size: " + str(self.size)) def _check_position_index(self, index): if not self._is_position_index(index): raise IndexError("Index: " + str(index) + ", Size: " + str(self.size)) # 使 MyArrayList 对象可迭代，从而可以使用 for 循环遍历其中的元素。 def __iter__(self): self.p = 0 return self def __next__(self): if self.p == self.size: raise StopIteration self.p += 1 return self.data[self.p - 1] # 打印 def display(self): print(f"size = {self.size} cap = {len(self.data)}") print(self.data) if __name__ == "__main__": arr = MyArrayList(3) for i in range(1, 6): arr.add_last(i) arr.remove(3) arr.add(1, 9) arr.add_first(100) val = arr.remove_last() for i in range(arr.size): print(arr.get(i)) print(arr.display())
双链表
from selenium.common import NoSuchElementException class MyLinkedList: class Node: def __init__(self, val): self.val = val self.next = None self.prev = None def __init__(self): self.head = self.Node(None) self.tail = self.Node(None) self.head.next = self.tail self.tail.prev = self.head self.size = 0 def add_last(self, e): x = self.Node(e) temp = self.tail.prev temp.next = x x.prev = temp x.next = self.tail self.tail.prev = x self.size += 1 def add_first(self, e): x = self.Node(e) temp = self.head.next temp.prev = x x.next = temp self.head.next = x x.prev = self.head self.size += 1 def add(self, index, element): self._check_position_index(index) if index == self.size: self.add_last(element) return p = self._get_node(index) temp = p.prev x = self.Node(element) p.prev = x temp.next = x x.prev = temp x.next = p self.size += 1 def remove_first(self): if self.size < 1: raise NoSuchElementException() x = self.head.next temp = x.next self.head.next = temp temp.prev = self.head x.prev = x.next = None self.size -= 1 return x.val def remove_last(self): if self.size < 1: raise NoSuchElementException() x = self.tail.prev temp = x.prev temp.next = self.tail self.tail.prev = temp x.prev = x.next = None self.size -= 1 return x.val def remove(self, index): self._check_element_index(index) x = self._get_node(index) prev = x.prev next = x.next prev.next = next next.prev = prev x.prev = x.next = None self.size -= 1 return x.val def get(self, index): self._check_element_index(index) p = self._get_node(index) return p.val def get_first(self): if self.size < 1: raise NoSuchElementException() return self.head.next.val def get_last(self): if self.size < 1: raise NoSuchElementException() return self.tail.prev.val def set(self, index, val): self._check_element_index(index) p = self._get_node(index) old_val = p.val p.val = val return old_val def size(self): return self.size def is_empty(self): return self.size == 0 def _get_node(self, index): self._check_element_index(index) p = self.head.next for _ in range(index): p = p.next return p def _is_element_index(self, index): return 0 <= index < self.size def _is_position_index(self, index): return 0 <= index <= self.size def _check_element_index(self, index): if not self._is_element_index(index): raise IndexError("Index: " + str(index) + ", Size: " + str(self.size)) def _check_position_index(self, index): if not self._is_position_index(index): raise IndexError("Index: " + str(index) + ", Size: " + str(self.size)) def display(self): print("size =", self.size) p = self.head.next while p != self.tail: print(p.val, "-> ", end="") p = p.next print("null") print() def __iter__(self): self.p = self.head.next return self def __next__(self): if self.p == self.tail: raise StopIteration val = self.p.val self.p = self.p.next return val if __name__ == "__main__": # 创建一个 MyLinkedList 实例 linked_list = MyLinkedList() # 在链表末尾添加元素 linked_list.add_last(1) linked_list.add_last(2) linked_list.add_last(3) # 在链表开头添加元素 linked_list.add_first(0) # 在指定位置插入元素 linked_list.add(2, 1.5) # 输出链表大小 print("Size of linked list:", linked_list.size) # 输出链表中的元素 print("Linked list elements:") for val in linked_list: print(val) # 移除链表开头和末尾的元素 print("Removed first element:", linked_list.remove_first()) print("Removed last element:", linked_list.remove_last()) # 输出链表中的元素 print("Linked list elements after removal:") for val in linked_list: print(val)
🍋总结
下一节，我把单链表的也给出来，顺便做两道题应用一下以上的基本操作
挑战与创造都是很痛苦的，但是很充实。
