基本结构

1. Python 数据结构

1.1. List (列表) - [] / list()

• 定义： 有序的可变序列，可以包含任意类型的对象。
• 操作：
  • 索引访问：O(1)
  • 添加元素（末尾）：O(1) 均摊
  • 插入/删除元素（中间）：O(n)
  • 搜索元素：O(n)
• 特点：
  • 支持重复元素
  • 支持索引操作，可以通过下标访问或修改元素
  • 支持切片操作
• 使用场景： 适合需要频繁访问、修改数据，或维持元素顺序的场景。
• 常用函数：
  • append()：接受一个 item
  • extend()：接收 list，扩展原有 list（+ 返回新 list 不修改原 list）
  • insert()：指定索引位置添加元素
  • pop()，clear()：删除元素或清空列表
  • index()：找出第一个匹配索引
  • count()：计算元素出现次数
  • sort()，reverse()：排序和反转

1.2. Tuple (元组) - ()

• 定义： 有序的不可变序列，一旦创建不能修改。
• 操作：
  • 索引访问：O(1)
  • 搜索元素：O(n)
• 特点：
  • 不可变，不能增删元素或修改
  • 支持索引和切片
  • 可作为字典的键，或用在需要不可变对象的地方
• 使用场景： 适合不需要修改内容的数据集合，常用于函数的返回值。
• 常用函数：
  • index()：找出第一个匹配索引
  • count()：计算某元素出现次数

1.3. Set (集合) - set()

• 定义： 无序的唯一元素集合，集合中的元素没有重复。
• 操作：
  • 添加元素：O(1) 均摊
  • 删除元素：O(1) 均摊
  • 搜索元素：O(1) 均摊
  • 合并/交集/差集：O(n)
• 特点：
  • 不允许重复元素
  • 无序，不支持索引
• 使用场景： 适合需要快速去重或集合运算（如交集、并集、差集）的场景。
• 常用函数：
  • add()：添加元素
  • update()：扩展集合
  • remove() / discard()：删除元素（区别在于不存在时是否报错）
  • pop()：随机删除元素
  • union() / intersection() / difference()：并集、交集、差集

1.4. Map (字典) - {} / dict()

• 定义： 键值对的无序集合，通过键存取对应的值。
• 操作：
  • 查找/插入/删除键值对：O(1) 均摊
  • 遍历键/值：O(n)
• 特点：
  • 键是唯一的，可以快速查找对应值
  • 键必须是不可变类型（如 str、tuple、int）
• 使用场景： 适合需要快速查找、插入、删除数据的场景，尤其是键值对映射。
• 常用函数：
  • get()，setdefault()：查找值并设置默认值
  • update()，pop()：更新或删除键值对
  • keys()，values()，items()：获取所有键、值或键值对

2. 非 Python 直接提供的数据结构

2.1. Array (数组) - array.array() / np.array()

• 定义： 固定类型的序列，常用于数值计算。
• 操作：
  • 索引访问：O(1)
  • 添加元素（末尾）：O(1) 均摊
  • 插入/删除元素（中间）：O(n)
  • 搜索元素：O(n)
• 特点：
  • 元素类型必须一致（如整型、浮点型）
  • numpy 支持多维数组和高级运算
• 使用场景： 适合大量数值计算或对存储效率有要求的场景。

2.2. Linked List (链表)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

• 定义： 链表是一种线性数据结构，每个节点包含数据和指向下一个节点的指针。常见的链表有单链表、双向链表等。
• 操作：
  • 索引访问：O(n)
  • 添加元素（末尾）：O(1)（有尾指针），O(n)（无尾指针）
  • 插入/删除元素：O(1)（已知位置），O(n)（遍历到位置）
  • 搜索元素：O(n)
• 特点：
  • 动态大小，按需分配内存
  • 插入和删除操作非常高效
  • 不支持随机访问
• 使用场景： 适用于需要频繁插入、删除操作的场景，如队列、栈等。
• 常用方法：
  • insert()，delete()，append()，find()，reverse()

2.3. Stack (栈) - 通常由列表实现

• 定义： 栈是一种后进先出（LIFO）的数据结构，数据只能在栈顶插入和删除。
• 操作：
  • 压栈（push()）：O(1)
  • 出栈（pop()）：O(1)
  • 获取栈顶元素：O(1)
• 特点：
  • 后进先出（LIFO）
  • 只能在栈顶进行操作
• 使用场景： 适用于递归、括号匹配、浏览器前进/后退等场景。

2.4. Queue (队列) - 通常用 collections.deque 实现

• 定义： 队列是一种先进先出（FIFO）的数据结构，数据在队尾插入，在队首删除。
• 操作：
  • 入队（append()）：O(1)
  • 出队（popleft()）：O(1)
  • 获取队首元素：O(1)
  • 检查是否为空：O(1)
• 特点：
  • 先进先出（FIFO）
  • 操作只在队尾和队首进行
• 使用场景： 适用于任务调度、消息队列、广度优先搜索等场景。

2.5. 双端队列（deque） - 使用 collections.deque 实现

• 定义： 双端队列支持在两端高效地插入和删除元素。
• 操作：
  • 从队尾插入（append()）：O(1)
  • 从队尾删除（pop()）：O(1)
  • 从队首插入（appendleft()）：O(1)
  • 从队首删除（popleft()）：O(1)
• 使用场景： 适用于实现栈、队列、双向队列等场景。

2.6. Heap (堆) - 使用 heapq 实现

• 定义： 堆是一种完全二叉树结构，通常用于实现优先队列，有最大堆和最小堆之分。
• 操作：
  • 插入元素（heappush()）：O(log n)
  • 获取并删除最小元素（heappop()）：O(log n)
  • 获取最小元素（heap[0]）：O(1)
• 特点：
  • 快速获取最大/最小元素
• 使用场景： 适用于优先队列、调度系统等。

2.7. Priority Queue (优先队列) - 使用 queue.PriorityQueue 实现

• 定义： 优先队列按照元素的优先级顺序处理数据，通常使用堆来实现。
• 操作：
  • 插入元素（put()）：O(log n)
  • 删除最高优先级元素（get()）：O(log n)
  • 获取队列大小（qsize()）：O(1)
• 特点：
  • 按优先级顺序处理任务
• 使用场景： 适用于任务调度、事件驱动模拟等场景。

2.8. Graph (图)

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def display(self):
        for vertex in self.graph:
            print(vertex, ":", self.graph[vertex])

• 定义： 图由节点和边组成，表示节点之间的关系。可以是有向图或无向图，边可以是带权或无权的。
• 操作：
  • 添加顶点：O(1)
  • 添加边：O(1)
• 特点：
  • 适合表示复杂关系
• 使用场景： 社交网络、路线规划等。

2.9. Trie (前缀树)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

• 定义： Trie 是一种用于快速查找前缀匹配的树结构，常用于字符串操作。
• 操作：
  • 插入单词：O(n)
  • 搜索单词：O(n)
• 特点：
  • 快速查找前缀
• 使用场景： 自动补全、前缀匹配等。