数据结构定义
数据结构就是：计算机存储与组织数据的方式，一种或多种特定关系的数据元素的集合。
数据结构作用
精心选择的数据结构，可以显著的提升程序运行效率，所以重点是要了解不同的数据结构，并找到具体的应用场景。
常用的数据结构
常用的数据结构主要包含如下几类：
- 数组(Array)：连续存储，线性结构；
- 栈( Stack)：线性存储，只允许一端操作，先进后出；
- 队列(Queue)：类似栈，可以双端操作，先进先出，类似水管；
- 链表( LinkedList)：链式存储，配备前后节点的指针，可以是双向的；
- 树( Tree)：典型的非线性结构；
- 图(Graph)：另一种非线性结构，由节点和关系组成，没有根的概念；
- 堆(Heap)：特殊的树；
- 散列表(Hash)：源自于散列函数，将值做一个函数式映射，映射的输出作为存储的地址；
下面我分别详解这些常见的数据结构。
数组
1.数组定义
数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
2.数组数据结构
数组如下图所示：
3.数组特点
- 一个数组可以分解为多个数组元素；
- 按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等；
- 数组还可以有一维、二维以及多维等表现形式；
- 数组按照索引查询元素，速度很快，时间复杂度为O(1)；
- 添加、删除元素的操作很耗时间，因为要移动其他元素，时间复杂度为O(n)。
链表
1.链表定义
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
2.链表分类
链表是主要分为三类：单链表、双链表、循环链表。
1)单链表
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
具体如下图所示：
2)双链表
双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。
具体如下图所示：
3)循环链表
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
具体如下图所示：
3.链表的优缺点
链表的优点：
- 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
- 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加删除很快；
链表缺点：
- 因为含有大量的指针域，占用空间较大；
- 查找元素需要遍历链表来查找，非常耗时。
栈
1.栈定义
栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
2.栈操作
栈如下图所示：
栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。
栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。
哈希表
1.哈希表定义
哈希表，英文名为：Hash表，是根据键值而直接进行访问的数据结构。
2.哈希表数据结构
哈希表（hash table），也叫散列表，这种数据结构提供了键（Key）和值（Value）的映射关系。
只要给出一个Key，就可以高效查找到它所匹配的Value，如下图所示：
3.哈希表的应用
大家最熟悉经典的HashMap就是采用哈希表的结构。
如下图所示：
除此之外，还有大家熟悉的分布式缓存，Redis、Memcached等底层实现也会用到哈希表，比如：Redis数据存储本质就是一个巨大的哈希表。
队列
队列和栈类似，也是一种特殊的线性表，和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
队列的实现，如下图所示：
一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头，队列中没有元素时，称为空队列。
二叉树
二叉，顾名思义，这种树的每个节点最多有2个孩子节点，如下图所示：
二叉树（binary tree）是树的一种特殊形式，每个节点最多可以有两个子节点，称为左子节点和右子节点。
二叉树大致分为以下几类：满二叉树、完全二叉树、二叉查找树。
1.满二叉树
满二叉树，就是所有节点都是满的，如下图所示：
2.完全二叉树
完全二叉树除最后一层，其它层都是满结点的，这就是完全二叉树与满二叉树的区别所在。
3.二叉查找树
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》