目录

一、时空复杂度 

二、数据结构分类图

三、细分数据结构

1. 数组

2. 链表

3. 栈

4. 队列

5. 散列表

6. 跳表

7. 树

8. 图

一、时空复杂度 

  小结：通常所说的时空复杂度分析其实是描述程序运行过程中所需要的时间与额外空间的一种度量方式并非真实所需要的时间与空间，因此也称为渐近时间复杂度或渐近空间复杂度。

二、数据结构分类图

总结： 通过上图可以知道数据的以下几个特点

1. 数据结构的物理存储方式通常只有在内存空间中顺序存储或链式存储两种方式，而这两种方式对应的数据结构分别为数组与链表。在一些资料中还看到物理结构中有散列存储方式，其实仔细分析会发现散列存储其实也是基于链式存储与顺序存储的一种存储方式。
2. 数据结构中像栈、队列、哈希表、跳表、图、树等都是通过数组或链表这两种基本数据结构所衍生而来。例如哈希表通过数组+链表或者数组+链表+红黑树所衍生而来。

三、细分数据结构

1. 数组

概念：通过连续的内存空间来存储一组相同类型的数据。

特点：数组最大的杀手锏是随机读取。代价是需要预先分配连续的存储空间与牺牲插入、删除操作的效率。

适用场景：读多写少。通过数组下标读取时间复杂度O(1)，插入或删除操作为了保持内存空间的连续性需要移动数据，故时间复杂度为O(n)。

顺序存储如下图红色部分所示：

2. 链表

概念：通过链式存储方式组织数据存储于内存中的一种线性表数据结构。

特点：通过指针的方式灵活地在内存中组织数据，其与数组最大的区别是不需要预先在内存中开辟整块连续的内存空间进行存储，这个特点也使得链表在无需复制数据的情况下支持自动扩容。代价是读只能是遍历的方式进行读取。

常见的链表有：单链表、双链表、循环单链表、循环双链表。

适用场景：读少写多。链表读需要遍历，时间复杂度为O(n)，更新因为不需要移动数据只需要更新对应节点的指向指针，时间复杂度为O(1)。

链式存储如下所示：

3. 栈

概念：栈是一种逻辑结构，只支持FILO。

特点：只有简单的入栈Push操作与出栈Pop操作。由于栈的入栈操作与出栈操作都是没有产生数据的移动，因此其时间复杂度都为O(1)。

类别：通过数组实现的栈称为顺序栈，链表实现的称为链表栈。

适用场景：

• 1. 不想对外暴露过多操作能力的场景
• 2. 实现浏览器的前进与后退
• 3. 栈在函数调用中的应用

4. 队列

概念：队列是一种先进先出的线性结构;

特点：只有简单的入队 enqueue()与出队 dequeue()操作。由于栈的入栈操作与出栈操作都是没有产生数据的移动，因此其时间复杂度都为O(1)。

类别：通过数组实现的队列叫顺序队列，通过链表实现的队列叫链式队列。

适用场景：

1. 有限资源的分配策略：通俗地来说对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现。

2. 类似“生产者与消费者”的模式，如消息队列，对应的实例有KafKa。

5. 散列表

概念：散列表（Hash table，也叫哈希表），是存储Key-Value映射的集合。

特点：可根据键(key)实现近O(1)的时间内对内存中数据进行读写的数据结构。散列表支持随机访问用的正是数组通过下标来随机访问数据的特性，可以说散列表就是数组的一个扩展。

组织数据：数组+链表或数组+链表+平衡树。

冲突解决：开放寻址或链表法。HashMap使用的是链表法，以及在JDK1.8后通过位运算优化了动态扩容copy数据这个缺点。

适合场景：

• 1. 拼写检查器：如word文档中拼写错误提示功能。
• 2. 实现LRU缓存淘汰算法，如java中 LinkedHashMap。

6. 跳表

概念：跳表（Skip List）也称跳跃表，是一种基于在有序链表上挑选关键点来创建多层索引的动态数据结构。

特点：思想上通过空间换取时间；查找方式与效果类似数组的二分查找。

原理：跳表实质就是一种可进行二分查找的有序链表。

时空复杂性分析：额外创建多层索引空间复杂度为O(n); 查找或更新时间复杂度为O(logn)，相对于有序数组其插入或删除不需要移动数据，故在写方面时间复杂度好过有序数组的O(n)。

适用场景

1.  Leveldb，一个google实现的非常高效的kv数据库；
2. Redis SortedSet，Redis 通过跳表实现有序集合；
3. 可以替代部分需要用平衡树实现的场景。
4. Java 容器对应的 ConcurrentSkipListMap

7. 树

概念：由n（n>=1）个有限结点组成一个具有层次关系的集合。

特点：最大的特点是一种支持快速查找、删除、插入的动态数据结构。

常用的存储方式：基于指针的链表式存储，还有一种就是基于数组的顺序存储。

适合场景：

几乎很多底层设计结构都有树的存在，如：Mysql 数据库索引通过B+树存储，HashMap 通过红黑树。

8. 图

概念：图(Graph )是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G (V,E )，其中，G表示一个图,，V是图G中顶点的集合，E是图G中边的集合。

存储方式：通常有两种方式分别为邻接距阵与链表式存储。

适合场景

1.几乎所有难以通过线性表解决的问题如果可以转换成图，便可用图现成的一些算法快速解决。

2.存储微信或微博的好友关系。

3. 图还可以应用在一些导航图或城市规划等形成的加权图；

4. 做为一些图数据库的底层思想存在。

注：了解更多数据结构知识