线性表(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),结点顺序固定,左孩子小于右孩子。
满二叉树
一个二叉树的所有非叶子结点都存在左右孩子,并且所有叶子结点都在同一层级上。
完全二叉树
将一个有n个结点的二叉树,按层级顺序编号为1-n,与同样深度的满二叉树的结点编号位置相同
二叉查找树(binary search/sort tree)
在二叉树的基础上要求左子树小于父结点,右子树大于父结点,保证了有序性,查找和插入的时间复杂度为O(logn),其性能稳定,扩容方便
红黑树(Red Black Tree)——
一种平衡二叉查找树,极端情况下二叉查找树退化成链表,时间复杂度为O(n),所以需要平衡二叉查找树。
- 特征
- 结点是黑色或是红色
- 根结点是黑色
- 每个叶子结点都是黑色的空结点(便利起见,一般省略)
- 父子结点不能同时为红
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点(平衡的关键)
- 新插入结点默认为红色,插入后需要校验红黑树是否符合规则,不符合则需要进行平衡
- 维持平衡的操作
- 左旋(RotateLeft):父结点被右孩子取代,自己成为新父结点的左孩子,原右孩子的左孩子变成原父结点的右孩子。
- 右旋(RotateRight):父结点被左孩子取代,自己成为新父结点的右孩子,原左孩子的右孩子变成原父结点的左孩子。
- 颜色反转:新插入的结点的父结点与叔叔结点同为红色,则反转两者为黑色,将祖结点反转为红色
- 5种插入结点的情况
- 新结点为根结点,直接置为黑色
- 新结点的父结点是黑色,不作调整
- 新结点的父结点与叔叔结点同为红色,需将反转两者为黑色,将祖结点反转为红色
- 新结点的父结点是红色,叔叔结点是黑色或者没有叔叔,新结点是右孩子,其父结点是左孩子,我们以父结点为轴左旋,使得新结点成为父结点,原父结点成为新结点的左孩子,进入情况5
- 新结点的父结点是红色,叔叔结点是黑色或者没有叔叔,新结点是左孩子,其父结点是左孩子,我们以祖结点为轴右旋,使得父结点代替祖结点,祖结点成为新祖结点的右孩子。将新祖结点置为黑色,原祖结点置为红色。
- 时间复杂度:O(logn)
- 应用:在JDK1.8中HashMap使用数组+链表+红黑树的数据结构。
- 特征
- 存储
- 链式存储:二叉树的每一个结点包含3部分,存储数据的data变量,指向左孩子的left指针,指向右孩子的right指针
- 数组存储:一个父结点的下标是n(根结点在数组中的下标为0),那么它的左孩子结点下标就是2×n+1、右孩子结点下标就是2*n+2,没有则以空表示,因此,对于一个稀疏的二叉树来说,用数组表示法是非常浪费空间的
- 遍历
- 深度优先
偏向于纵深,“一头扎到底”的访问方式- 前序遍历:根,左,右
- 中序遍历:左,根,右
- 后序遍历:左,右,根
- 广度优先
层序遍历,按照从根结点到叶子结点的层次关系,一层一层横向遍历各 个结点,可以利用队列实现——根结点A进入队列,根结点A出队,得到根结点孩子结点,A的左孩子B进队列,A的右孩子C进队列,左孩子B出队列,B的左孩子E进队列,B的右孩子F进队列,C出队列,C的孩子进队列……
- 深度优先
多路查找树(muitl-way search tree)
每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。
- B树(BalanceTree)
对二叉查找树的改进,它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。
一棵m阶的B树 (m叉树)的特性如下
- B树中所有结点的孩子结点数中的最大值称为B树的阶,记为M
- 树中的每个结点至多有M棵子树
- 若根结点不是叶子结点,则至少有两棵子树
- 除根结点和叶结点外,所有结点至少有m/2棵子树
- 所有的叶子结点都位于同一层
- B+树
B树的变体,是一种多路搜索树,其定义基本与B树相同,它的自身特征是:
- 非叶子结点的子树指针与关键字个数相同
- 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树
- 为所有叶子结点增加一个链指针
- 所有关键字都在叶子结点出现
- 应用:MySQL索引B+Tree
- B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树
- B树的高度一般都是在2-4这个高度,树的高度直接影响IO读写的次数
- 如果是三层树结构,支撑的数据可以达到20G,如果是四层树结构,支撑的数据可以达到几十T
- B和B+的区别
- 非叶子节点是否存储数据: B树是非叶子节点和叶子节点都会存储数据, B+树只有叶子节点才会存储数据
- 数据排布:B+树存储的数据都是在一行上,而且这些数据都是有指针指向的,也就是有顺序的。
二叉堆
二叉堆本质上是一种完全二叉树。
分类
- 大顶堆(最大堆):最大堆的任何一个父节点的值,都大于或等于它左、右孩子节点的值,最大堆的堆顶是整个堆中的最大元素
- 小顶堆(最小堆):最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值,最小堆的堆顶是整个堆中的最小元素
存储原理
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的,因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
图(待整理)
- 相关概念
- 顶点
- 边
- 度
- 分类
- 有向图
- 无向图
- 带权图
- 实现:领接矩阵(二维数组)/ 邻接表
- 遍历
- 应用