| 数组 | 链表 | 栈 | 队列 | 散列表 |
|---|---|---|---|---|
| 跳表 | 图 | 树 | 堆 | 字典树 |
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里有几个关键词给大家解释一下，帮助大家更深刻的认识数组，它们分别是：线性表数据结构、连续内存空间、相同类型。
1.1 数组是其他数据类型的基础
为什么说数组是一种基本的数据类型？
第一：数组这种数据类型太常用了 ，基本每个编程语言都有；
第二：数组还构成了其他数据类型。
数组构成了哪些数据类型？
链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer). 链表可以不是连续内存
2.1 链表的用途
链表是一种使用极其广泛的数据结构，它也可以用来作为实现栈、队列等数据结构的基础，链表没有像数组需要预先知道数据大小的缺点，可充分利用计算机内存，实现动态灵活的内存管理。除非需要频繁的通过下标来随机访问各个数据，否则数组都可以用链表代替。
数组： 逻辑上相邻，物理上相邻
链表： 逻辑上相邻，物理不一定相邻
有数组为什么还要用链表呢？
C语言里面的数组是固定不变的，开辟了多大空间就会在它作用域内一直存在，而链表则是当你不用链表中某段值时可以随时的释放掉那部分内存，即可以时刻节省内存。
由于其非连续内存的特性导致链表非常适用于频繁插入、删除的场景，而不见长于读取场景，这跟数组的特性恰好形成互补，所以现在也可以回到题目中的问题了，链表的特性与数组互补，各有所长，而且链表由于指针的存在可以形成环形链表，在特定场景也非常有用，因此链表的存在是很有必要的。
记住这句话：
基本上所有的数据结构都可以使用数组和链表来实现
栈就是一种只允许在表尾进行插入和删除操作的线性表
FILO：Last In First Out
3.1 栈的用途
栈区：由编译器自动分配释放, 存放函数的参数值,局部变量等
栈的一个典型应用就是函数调用
常见的二叉树先序、中序、后序非递归遍历
栈的应用广泛，比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs，替代递归等等。
队列（queue）是只允许在一端（队尾）进行插入操作，而在另一端（队头）进行删除操作的线性表。
FIFO：First in First Out
4.1 队列的用途
树的按层遍历
图的广度优先搜索等
这两个缩写代表了栈和队列这两个数据结构对数据存取的特点
散列表英文名叫“Hash Table”，也叫哈希表或者Hash表。它利用数组支持按照下标随机访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
5.1 Hash的应用
Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。
Hash表在海量数据处理中有着广泛应用。
链表是一种基本的数据结构，而跳跃表是一种特殊的有序链表。
跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构，实质上是可以进行二分查找的有序链表；跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。
跳表使用的是空间换时间的思想，通过构建多级索引来提高查询效率，实现基于链表的“二分查找”，跳表是一种动态的数据结构，支持快速的查找、插入和删除操作，时间复杂度是 O(logn)。
6.1 跳表的应用
Redis在存储有序集合的时候就用到了跳表+散列表的数据结构
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构
图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。
图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。
堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。 堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。
Trie 树，也叫“字典树”,是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。
10.1 字典树的应用
它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
原文：https://www.cnblogs.com/gmengshuai/p/13871406.html