Linked List

  • 链表即是由节点（Node）组成的线性集合，每个节点可以利用指针指向其他节点。它是一种包含了多个节点的、能够用于表示序列的数据结构。
  • 单向链表： 链表中的节点仅指向下一个节点，并且最后一个节点指向空。
  • 双向链表： 其中每个节点具有两个指针p、n，使得p指向先前节点并且n指向下一个节点；最后一个节点的n指针指向null。
  • 循环链表： 每个节点指向下一个节点并且最后一个节点指向第一个节点的链表。
  • 时间复杂度：
    • 索引：O(n)
    • 搜索：O(n)
    • 插入：O(1)
    • 移除：O(1)

Stack

  • 栈是元素的集合，其包含了两个基本操作：push操作可以用于将元素压入栈，pop操作可以将栈顶元素移除。
  • 遵循后入先出（LIFO）原则。
  • 时间复杂度：
    • 索引：O(n)
    • 搜索：O(n)
    • 插入：O(1)
    • 移除：O(1)

Queue

  • 队列是元素的集合，其包含了两个基本操作：enqueue操作可以用于将元素插入到队列中，而dequeue操作则是将元素从队列中移除。
  • 遵循先入先出原则（FIFO）。
  • 时间复杂度：
    • 索引：O(n)
    • 搜索：O(n)
    • 插入：O(1)
    • 移除：O(1)

Tree

  • 树是无向、连通的无环图。

Binary Tree

  • 二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构。
  • 满二叉树： 除了叶子结点之外的每一个结点都有两个孩子结点。
  • 完美二叉树（Perfect Binary Tree）： 除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
  • 完全二叉树： 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。

Binary Search Tree

  • 二叉搜索树（BST）是一种特殊的二叉树，其任何节点中的值都会大于或者等于其左子树中存储的值并且小于或者等于其右子树中存储的值。
  • 时间复杂度：
    • 索引：O(log(n))
    • 搜索：O(log(n))
    • 插入：O(log(n))
    • 删除：O(log(n))
BST

Trie

  • 字典树，又称基数树或者前缀树，能够用于存储键为字符串的动态集合或者关联数组的搜索树。树中的节点并没有直接存储关联键值，而是该节点在树中的挂载位置决定了其关联键值。某个节点的所有子节点都拥有相同的前缀，整棵树的根节点则是空字符串。
Trie

Fenwick Tree

  • 树状数组又称Binary Indexed Tree，其表现形式为树，不过本质上是以数组实现。数组中的下标代表着树中的顶点，每个顶点的父节点或者子节点的下标能够通过位运算获得。数组中的每个元素包含了预计算的区间值之和，在整棵树更新的过程中同样会更新这些预计算的值。
  • 时间复杂度：
    • 区间求值：O(log(n))
    • 更新：O(log(n))
Fenwick Tree

Segment Tree

  • 线段树是用于存放间隔或者线段的树形数据结构，它允许快速地查找某一个节点在若干条线段中出现地次数。
  • 时间复杂度：
    • 区间查询：O(log(n))
    • 更新：O(log(n))
Segment Tree

Heap

  • 堆是一种特殊的基于树的满足某些特性的数据结构，整个堆中的所有父子节点的键值都会满足相同的排序条件。堆更准确地可以分为最大堆与最小堆，在最大堆中，父节点的键值永远大于或者等于子节点的值，并且整个堆中的最大值存储于根节点；而最小堆中，父节点的键值永远小于或者等于其子节点的键值，并且整个堆中的最小值存储于根节点。
  • 时间复杂度：
    • 访问最大值/最小值：O(1)
    • 插入：O(log(n))
    • 移除最大值/最小值：O(log(n))
Heap

Hashing

  • 哈希能够将任意长度的数据映射到固定长度的数据。哈希函数返回的即是哈希值，如果两个不同的键得到相同的哈希值，这种现象称为哈希碰撞。
  • Hash Map： Hash Map是一种能够建立起键与值之间关系的数据结构，Hash Map能够使用哈希函数将键转化为桶或者槽中的下表，从而优化对于目标值的搜索速度。
  • 碰撞解决
    • 链地址法（Separate Chaining）： 链地址法中，每个桶是相互独立的，包含了一系列索引的列表。搜索操作的时间复杂度即是搜索桶的时间（固定时间）与遍历列表的时间之和。
    • 开地址法（Open Addressing）： 在开地址法中，当插入新值时，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到一个尚未被占用的地址。所谓开地址法也是指某个元素的位置并不永远由其哈希值决定。
Hashing

Graph

  • 图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。
    • 无向图（Undirected Graph）： 无向图具有对称的邻接矩阵，因此如果存在某条从节点u到节点v的边，反之从v到u的边也存在。
    • 有向图（Directed Graph）： 有向图的邻接矩阵是非对称的，即如果存在从u到v的边并不意味着一定存在从v到u的边。
Graph