数据结构(Data structure)整理回顾

线性表(Linear List)

线性表(Linear List):数据结构成线型,只有前后两个方向,即一维数据

数组(Array)

  • 概念:有限相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。
  • 存储原理:数组用一组连续的内存空间来存储一组具有相同类型的数据,数组下标从0开始,可根据偏移量来寻址a[i]_address=a[0]_address+i*4
  • 操作:读取O(1),更新O(1),插入O(n)(尾部、中间、超范围/扩容插入),删除O(n)
  • 优点:高效的随机访问能力
  • 缺点:1.由于数组元素连续地存储在内存中,插入、删除元素都会导致大量元素被迫移动,影响效率。2. 申请的空间必须是连续的,如果超出范围,需要重新申请内存进行存储。

链表(linked list)

  • 概念:一种在物理上非连续、非顺序的数据结构,由若干结点(node)所组成。
  • 常见链表:单链表、双向链表、循环链表
    • 单链表:每一个结点包含两部分,存放数据的变量data,和指向下一个结点的指针next。
    • 双向链表:每一个结点包含三部分,除了拥有data和next指针,还拥有指向前置结点的prev指针。
    • 循环链表:链表的尾结点next指向头结点(或头结点prev指向尾结点)形成一个环,称为循环链表。
  • 存储原理:链表的每一个结点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间
  • 操作:读取O(n),更新O(1),插入O(1),删除O(1)
  • 优点:1.插入、删除、更新效率高。2.省空间。
  • 缺点:查询效率较低,不能随机访问。

栈(stack)

  • 概念:一种线性数据结构,最早进入的元素存放的位置叫作栈底(bottom),最后进入的元素存放的位置叫作栈顶 (top),栈中的元素只能先入后出(First In Last Out,简称FILO
  • 存储原理:数组实现的栈也叫顺序栈静态栈链表实现的栈也叫做链式栈动态栈
  • 操作:入栈O(1)(压栈,push,动态扩容O(n)),出栈O(1)(弹栈,pop)
  • 应用:函数调用栈,浏览器的后退前进功能。

队列(queue)

  • 概念:一种线性数据结构,出口端叫作队头(front),入口端叫作队尾(rear),队列中的元素只能先入先出(First In First Out,简称 FIFO
  • 存储原理:数组实现的队列叫作顺序队列链表实现的队列叫作链式队列
  • 操作:入队O(1)(enqueue),出队O(1)(dequeue)
  • 应用:资源池、消息队列、命令队列等等。

散列表(hash)

  • 概念:散列表也叫作哈希表,提供了键(Key)和值(Value)的映射关系。
  • 存储原理:本质上也是一个数组,通过hash函数把Key和数组下标进行转换,作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。例如,数组下标=取key的hashcode模数组的长度后的余数: int index = HashCode (Key) % Array.length
  • 操作:
    • 写操作O(m)(put,m为单链元素个数)
    • Hash冲突:即碰撞,由于数组的长度是有限的,当插入的Entry越来越多时,不同的Key通过哈希函数获得的下标有可能是相同的。常见的解决方法有,开放寻址法,在Java中,ThreadLocal所使用的就是开放寻址法;链表法。
    • 读操作O(m) (get,m为单链元素个数)
    • Hash扩容O(n)(resize):当HashMap.Size >= Capacity×LoadFactor时,需要进行扩容。Capacity,即HashMap的当前长度;LoadFactor,即HashMap的负载因子(阈值),默认值为0.75f。(JDK1.8前在HashMap扩容时,会反序单链表,这样在高并发时会有死循环的可能。Java8之后,当多个Entry被Hash到同一个数组下标位置时,为了提升插入和查找的效率,HashMap会把Entry的链表转化为红黑树这种数据结构。)
  • 优点:读写快
  • 缺点:1.哈希表中的元素是没有被排序的;2.Hash冲突;3.扩容需要重新计算
  • 应用:HashMap,字典,如Redis字典的相关实现包括:字典(dict)、Hash表(dictht)、Hash表结点(dictEntry),布隆过滤器,位图等

树(tree)

树(tree)n(n≥0)个结点的有限集;根结点(root),没有父结点;叶子结点(leaf),没有“孩子”;高度或深度,树的最大层级数

二叉树(binary tree)

特殊的树,每个结点最多有2个孩子结点,被称为左孩子(left child)和右孩子(right child),结点顺序固定,左孩子小于右孩子。

  1. 满二叉树

    一个二叉树的所有非叶子结点都存在左右孩子,并且所有叶子结点都在同一层级上。

  2. 完全二叉树

    将一个有n个结点的二叉树,按层级顺序编号为1-n,与同样深度的满二叉树的结点编号位置相同

  3. 二叉查找树(binary search/sort tree)

    在二叉树的基础上要求左子树小于父结点,右子树大于父结点,保证了有序性,查找和插入的时间复杂度为O(logn),其性能稳定,扩容方便

  4. 红黑树(Red Black Tree)——

    一种平衡二叉查找树,极端情况下二叉查找树退化成链表,时间复杂度为O(n),所以需要平衡二叉查找树。

    • 特征
      • 结点是黑色或是红色
      • 根结点是黑色
      • 每个叶子结点都是黑色的空结点(便利起见,一般省略)
      • 父子结点不能同时为红
      • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点(平衡的关键)
      • 新插入结点默认为红色,插入后需要校验红黑树是否符合规则,不符合则需要进行平衡
    • 维持平衡的操作
      • 左旋(RotateLeft):父结点被右孩子取代,自己成为新父结点的左孩子,原右孩子的左孩子变成原父结点的右孩子。
      • 右旋(RotateRight):父结点被左孩子取代,自己成为新父结点的右孩子,原左孩子的右孩子变成原父结点的左孩子。
      • 颜色反转:新插入的结点的父结点与叔叔结点同为红色,则反转两者为黑色,将祖结点反转为红色
    • 5种插入结点的情况
      • 新结点为根结点,直接置为黑色
      • 新结点的父结点是黑色,不作调整
      • 新结点的父结点与叔叔结点同为红色,需将反转两者为黑色,将祖结点反转为红色
      • 新结点的父结点是红色,叔叔结点是黑色或者没有叔叔,新结点是右孩子,其父结点是左孩子,我们以父结点为轴左旋,使得新结点成为父结点,原父结点成为新结点的左孩子,进入情况5
      • 新结点的父结点是红色,叔叔结点是黑色或者没有叔叔,新结点是左孩子,其父结点是左孩子,我们以祖结点为轴右旋,使得父结点代替祖结点,祖结点成为新祖结点的右孩子。将新祖结点置为黑色,原祖结点置为红色。
    • 时间复杂度:O(logn)
    • 应用:在JDK1.8中HashMap使用数组+链表+红黑树的数据结构。
  1. 存储
    • 链式存储:二叉树的每一个结点包含3部分,存储数据的data变量,指向左孩子的left指针,指向右孩子的right指针
    • 数组存储:一个父结点的下标是n(根结点在数组中的下标为0),那么它的左孩子结点下标就是2×n+1、右孩子结点下标就是2*n+2没有则以空表示,因此,对于一个稀疏的二叉树来说,用数组表示法是非常浪费空间
  1. 遍历
    • 深度优先
      偏向于纵深,“一头扎到底”的访问方式
      • 前序遍历:根,左,右
      • 中序遍历:左,根,右
      • 后序遍历:左,右,根
    • 广度优先
      层序遍历,按照从根结点到叶子结点的层次关系,一层一层横向遍历各 个结点,可以利用队列实现——根结点A进入队列,根结点A出队,得到根结点孩子结点,A的左孩子B进队列,A的右孩子C进队列,左孩子B出队列,B的左孩子E进队列,B的右孩子F进队列,C出队列,C的孩子进队列……

多路查找树(muitl-way search tree)

每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。

  1. B树(BalanceTree)

对二叉查找树的改进,它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

一棵m阶的B树 (m叉树)的特性如下

  • B树中所有结点的孩子结点数中的最大值称为B树的阶,记为M
  • 树中的每个结点至多有M棵子树
  • 若根结点不是叶子结点,则至少有两棵子树
  • 除根结点和叶结点外,所有结点至少有m/2棵子树
  • 所有的叶子结点都位于同一层
  1. B+树

B树的变体,是一种多路搜索树,其定义基本与B树相同,它的自身特征是:

  • 非叶子结点的子树指针与关键字个数相同
  • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树
  • 为所有叶子结点增加一个链指针
  • 所有关键字都在叶子结点出现
  • 应用:MySQL索引B+Tree
    • B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树
    • B树的高度一般都是在2-4这个高度,树的高度直接影响IO读写的次数
    • 如果是三层树结构,支撑的数据可以达到20G,如果是四层树结构,支撑的数据可以达到几十T
  1. B和B+的区别
  • 非叶子节点是否存储数据: B树是非叶子节点和叶子节点都会存储数据, B+树只有叶子节点才会存储数据
  • 数据排布:B+树存储的数据都是在一行上,而且这些数据都是有指针指向的,也就是有顺序的。

二叉堆

二叉堆本质上是一种完全二叉树。

  1. 分类

    • 大顶堆(最大堆):最大堆的任何一个父节点的值,都大于或等于它左、右孩子节点的值,最大堆的堆顶是整个堆中的最大元素
    • 小顶堆(最小堆):最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值,最小堆的堆顶是整个堆中的最小元素
  2. 存储原理

    完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的,因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。

图(待整理)

  • 相关概念
    1. 顶点
  • 分类
    1. 有向图
    2. 无向图
    3. 带权图
  • 实现:领接矩阵(二维数组)/ 邻接表
  • 遍历
  • 应用