数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构

• 非受限线性表
  • 顺序结构
    • 数组
      • 支持 O(1) 的随机访问
      • 平均为 O(n) 的插入和删除
      • 警惕越界错误，导致 Stack Over Flow
  • 链式结构
    • 单链表
      • 不支持随机访问，需要遍历去访问结点
      • 插入和删除只需要移动指针，时间复杂度为 O(1)
      • 每个结点需要额外的空间存储指针，需要的内存比数组大
    • 双链表
      • 在单链表的基础上，除头结点外，每个结点多了一个存放前驱结点内存地址的指针
    • 循环链表
      • 尾节点指针指向头结点
    • 静态链表
      • 借助数组，伴随指向后继结点的指针
• 受限线性表
  • 栈
    • 顺序和链式都可以实现，先进后出
    • 实际应用
      • 浏览器的前进与后退
      • 括号匹配
      • 表达式计算
  • 堆
    • 大顶堆
    • 小顶堆
    • 实际应用
      • 找第 K 大元素
  • 队列
    • 普通队列
      • 顺序和链式都可以实现，先进先出
    • 双边队列
      • 入口和出口都可以进队和出队
    • 优先级队列
      • 根据优先级来出队
    • 实际应用
      • LRU Cache
• 树与二叉树
  • 二叉树
    • 特点
      • 顺序和链式都可以实现
      • 遍历方式
        • 广度优先搜索
        • 深度优先搜索
          • 前序遍历
          • 中序遍历
          • 后序遍历
    • 完全二叉树
    • 满二叉树
    • 二叉搜索树
    • 平衡二叉搜索树
      • 红黑树
  • 哈夫曼树
  • 字典树
• 排序
  • O(n^2)
    • 冒泡排序
    • 插入排序
    • 选择排序
  • O(nlogn)
    • 快速排序
    • 归并排序
  • O(n)
    • 桶排序
    • 计数排序
    • 基数排序