数组、链表、列表
数组
什么是数组
数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。
数组操作
初始化
# array init
arr_1 = [0]*5
arr_2 = [1,2,3,4,5]
访问
通过索引即可访问数组中的内容，例如：
arr_1[0]
插入元素
倒序将元素逐个后移，最后将插入处的元素设为插入值
for i in range(len(arr) - 1,index,-1):
arr[i] = arr [i-1]
删除元素
从删除处开始顺序将元素逐个前移，删除的元素直接被覆盖
for i in range(index, len(arr)):
arr[i] = arr [i+1]
数组特点
- 存储为连续空间存储，且数组中的元素类型是相同的。
- 计算机加载数组时还会加载数组周围的数据，利于提升后续操作速度。
- 数组支持用O(1)的时间复杂度访问数组中任意一个元素。（索引直接访问）
- 增加、删除元素的开销较大，需要移动大量的元素。
- 数组创建之后长度不变，扩容需要将旧元素全部复制到新数组中，开销极大。
- 数组创建时长度固定，可能造成浪费
数组应用
数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。
- 随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
- 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
- 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。
- 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
- 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。
链表
什么是链表
链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过 “引用” 相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。（内存无须连续）
链表操作
初始化
链表初始化需要实例化各节点，并且建立每个节点之间的引用。通常将头节点当作链表的代称。
# 链表节点类
class ListNode:
def __init__(self, val):
self.val = val # 节点值
self.next = None # 引用，指向下一个节点
# 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
#
访问
在链表中访问节点需要从头开始遍历链表直至找到目标节点，复杂度为O(N)。
def access(head, index)
"""
head: 链表头
index: 要访问的节点的索引
"""
for _ in range(index):
if not head:
return None
# 移动到下一个节点
head = head.next
return head
插入元素
例如需要在n0和n1节点中间插入一个新的节点p，先将p的引用指向n1，再将n0指向p即可。
（需要先保存原来在n0后的节点，再设置插入节点和n0的引用）
链表插入元素时间复杂度为O(1)
def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
n1 = n0.next # 保存 n0 原本指向的下一个节点。
P.next = n1 # 插入的节点指向n1
n0.next = P # 改变n0的引用
删除元素
假设删除节点p，前后节点为n0和n1，那么将n0节点指向n1即可。（只需要改变前一个节点的引用）
def remove(n0: ListNode):
"""删除链表的节点 n0 之后的首个节点"""
if not n0.next:
return
# n0 -> P -> n1
P = n0.next # 保存n0的后一个节点
n1 = P.next # n1指向
n0.next = n1
常见的链表类型
- 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
- 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
- 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
class ListNode:
"""双向链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向后继节点的引用
self.prev: ListNode | None = None # 指向前驱节点的引用
链表特点
- 存储为分散空间存储
- 可以灵活扩展
- 元素占用内存较数组元素多（包含值和引用）
- 增加、删除元素的开销较小，而访问元素需要从头节点开始遍历，开销较大
链表应用
单向链表可以实现栈、队列、哈希表和图等数据结构。
– 只在单向链表的同一端进行元素的插入和删除（先进后出）即可实现栈。
– 在单向链表的一端进行元素的插入，另一端进行元素的删除（先进先出）即可实现队列。
– 邻接表常用于表示图。图中的每个节点都有一个链表，链表中的每个元素代表与该顶点相连的其他顶点。
– 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
双向链表常用于需要快速查找前一个和后一个元素的场景。
- 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
- 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。
– 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
– 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。
列表
什么是列表
列表表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
列表可以视为动态数组
列表常用操作
python中访问和初始化列表与数组相同，故不再赘述。
python中使用append在列表末尾添加元素
insert方法可以在某个位置插入元素。
pop方法可以删除指定位置元素。
sort方法可以对列表进行排序
# 清空列表
nums.clear()
# 在尾部添加元素
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)
# 在中间插入元素
nums.insert(3, 6) # 在索引 3 处插入数字 6
# 删除元素
nums.pop(3) # 删除索引 3 处的元素
python中拼接列表可以直接使用加号运算符
# 拼接两个列表
nums1: list[int] = [6, 8, 7, 10, 9]
nums += nums1 # 将列表 nums1 拼接到 nums 之后