线性数据结构：数组，链表，栈，队列

非线性数据结构：树，堆，散列表，图

数组：

# 初始化可变数组
array = []

# 向尾部添加元素
array.append(2)
array.append(3)
array.append(1)
array.append(0)
array.append(2)

链表：

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」 。

class ListNode:
    def __init__(self, x):
        self.val = x     # 节点值
        self.next = None  # 后继节点引用

# 实例化节点
n1 = ListNode(4) # 节点 head
n2 = ListNode(5)
n3 = ListNode(1)

# 构建引用指向
n1.next = n2
n2.next = n3

栈：

栈是一种具有 「先入后出」 特点的抽象数据结构，可使用数组或链表实现。

stack = [] # Python 可将列表作为栈使用
stack.append(1) # 元素 1 入栈
stack.append(2) # 元素 2 入栈
stack.pop()     # 出栈 -> 元素 2
stack.pop()     # 出栈 -> 元素 1

队列：

队列是一种具有 「先入先出」 特点的抽象数据结构，可使用链表实现。

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.pop()
queue.popleft()

树：

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。

class TreeNode:
    def __init__(self, x):
        self.val = x      # 节点值
        self.left = None  # 左子节点
        self.right = None # 右子节点

# 初始化节点
n1 = TreeNode(3) # 根节点 root
n2 = TreeNode(4)
n3 = TreeNode(5)
n4 = TreeNode(1)
n5 = TreeNode(2)

# 构建引用指向
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

图：

图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。
1599579136-Fxseew-Picture7.png
表示图的方法通常有两种：

1. 邻接矩阵： 使用数组 vertices 存储顶点，邻接矩阵 edges 存储边； edgesi 代表节点 i + 1 和 节点 j + 1 之间是否有边。

   vertices = [1, 2, 3, 4, 5]
   edges = [[0, 1, 1, 1, 1],

        [1, 0, 0, 1, 0],
        [1, 0, 0, 0, 1],
        [1, 1, 0, 0, 1],
        [1, 0, 1, 1, 0]]
   

2. 邻接表： 使用数组 vertices 存储顶点，邻接表 edges 存储边。 edges 为一个二维容器，第一维 i 代表顶点索引，第二维 edges[i] 存储此顶点对应的边集和；例如 edges[0] = [1, 2, 3, 4]代表 vertices[0] 的边集合为 [1, 2, 3, 4] 。

   vertices = [1, 2, 3, 4, 5]
   edges = [[1, 2, 3, 4],

        [0, 3],
        [0, 4],
        [0, 1, 4],
        [0, 2, 3]]
   

邻接矩阵 VS 邻接表 ：

邻接矩阵的大小只与节点数量有关，即 N^2，其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会> 造成较大的内存浪费。 因此，邻接表 适合存储稀疏图（顶点较多、边较少）；
邻接矩阵 适合存储稠密图（顶点较少、边较多）

散列表：

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找，设计一个高效的Hash函数可以使得时间复杂度为O（1）

# 初始化散列表
dic = {}

# 添加 key -> value 键值对
dic["小力"] = 10001
dic["小特"] = 10002
dic["小扣"] = 10003

# 从姓名查找学号
dic["小力"] # -> 10001
dic["小特"] # -> 10002
dic["小扣"] # -> 10003

堆：

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

完全二叉树定义： 设二叉树深度为 k ，若二叉树除第 k 层外的其它各层（第 1 至 k-1 层）的节点达到最大个数，且处于第 kk
层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序。

from heapq import heappush, heappop

# 初始化小顶堆
heap = []

# 元素入堆
heappush(heap, 1)
heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 6)
heappush(heap, 8)

# 元素出堆（从小到大）
heappop(heap) # -> 1
heappop(heap) # -> 2
heappop(heap) # -> 4
heappop(heap) # -> 6
heappop(heap) # -> 8