数组
python 数组都是动态数组，长度是自动变化的，所以不需要数组的扩容操作，这也是python运行要比C，Java慢的原因之一
列表: 由于数组长度不可变导致实用性降低，创建了一种动态数组的数据结构，称为列表
所以严格意义来说，python里面的数组就是列表
列表的代码（硬要定义数组不可变化）
class MyList: def __init__(self): self.__capacity = 10 self.__nums = [0] * self.__capacity self.__size = 0 self.__extend_ratio: 2 def size(self): return self.__size def capacity(self): return self.__capacity def get(self, index): if index < 0 or index > self.__size: raise IndexError('索引越界') return self.__nums[index] def set(self, index, val): if index < 0 or index > self.__size: raise IndexError('索引越界') self.__nums[index] = val def add(self, val): if self.__size == self.__capacity: self.__capacity *= self.__extend_ratio self.__nums[self.__size] = val self.__size += 1 def insert(self, index, val): if index < 0 or index > self.__size: raise IndexError('索引越界') for i in range(index, self.__size-1): self.__nums[i+1] = self.__nums[i] self.__nums[i] = val self.__size += 1 def remove(self, index): if index < 0 or index > self.__size: raise IndexError('索引越界') for i in range(index, self.__size-1): self.__nums[i] = self.__nums[i+1] self.__size -= 1 def extend_capacity(self): self.__nums += [0]*self.__capacity*(self.__extend_ratio - 1) self.__capacity = len(self.__nums)
链表
链表的代码：
class ListNode: def __init__(self, value): self.value = value self.next = None self.prev = None
对比
重点
- 数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和离散空间存储。两者的特点呈现出互补的特性。
- 数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。
- 链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、循环链表、双向链表。
- 动态数组，又称列表，是基于数组实现的一种数据结构。它保留了数组的优势，同时可以灵活调整长度。列表的出现极大地提高了数组的易用性，但可能导致部分内存空间浪费。
