非受限线性表

顺序结构

数组

     - 支持O(1)随机访问
     - 平均O(n)的插入和删除
     - 小心越界

链式结构

单链表

     - 不支持随机访问 需要遍历
     - 插入删除只需移动指针 O(1)
     - 每个节点需要额外的空间 内存比较大

双链表

     - 在单链表基础上 除了头节点 每个节点增加了前驱指针

循环链表

     - 尾节点指向了头节点

静态链表

     - 借助数组 记录了后继

受限线性表

栈

  - 顺序和链式都可以 先进后出

实际应用

     - 浏览器历史记录
     - 括号匹配
     - 表达式计算

堆

大顶堆

小顶堆

实际应用

     - 找第K大元素

队列

普通队列

     - 顺序链式都可以 先进先出

双边队列

     - 前后都能出队入队

优先级队列

     - 根据优先级出队

实际应用

     - LRU Cache

树于二叉树

二叉树

平衡二叉树

     - 红黑树

二叉搜索树

满二叉树

完全二叉树

特性

     - 顺序链式都可以
     - 遍历方式
        - 广度优秀
        - 深度优先
           - 前序遍历
           - 中序遍历
           - 后续遍历

哈夫曼树

字典树

排序

O(n^2)

冒泡排序

插入排序

选择排序

O(nlogn)

快速排序

归并排序

O(n)

桶排序

计数排序

基数排序