文章目录

• 前言
• 一、为什么要研究数据结构
• 二、数据结构的分类
• • 1.数组（Array）
  • 2.链表（Linked List）
  • 3.队列（Queue）
  • 4.栈（Stack）
  • 5.散列表（Hash）
  • 6.树（Tree）
  • 7.堆（Heap）
  • 8.图（Graph）
• 总结

---

前言

其实在Java编程中大家一直都比较忽视数据结构，大部分都是常用几个集合类型，能实现业务功能就行，对数据结构都缺乏系统认知。最近计划翻翻源码，对java中常用的数据结构加深下理解。

---

一、为什么要研究数据结构

1. 应付大厂面试，升职加薪
2. 熟悉数据结构可以帮忙我们更好的理解源码和架构设计，明白设计的精妙之处
3. 数据结构可以帮助我们进行程序的性能优化
4. 数据结构是软件编程的基石，具有普遍的适用性，俗称的“内功”，不像具体的技术栈，很容易过时。

二、数据结构的分类

程序 = 算法 + 数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。可分为八大数据结构：。

• 访问数组中第n个数据（即根据数据的下标随机访问）的时间复杂度是O(1)；但是要在数组中查找一个指定的数据则是O(N)；
• 当向数组中插入或者删除数据的时候：
  最好的情况是在数组的末尾进行操作，时间复杂度是O(1) ；
  最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。平均情况时间复杂度也为O(n)。

像上面这样的链表结构在插入和删除的时候编程会比较困难，因为需要记住当前节点的前一个节点，这样才能完成插入和删除。为了简便通常使用带有头节点的链表：

头指针就是链表的名字，头指针仅仅是个指针而已。

添加头结点的好处：

• 主要是为了。头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
  有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

上面的链表是单链表，此外还有双链表，就是节点中包含指向下一个节点的指针和指向上一个节点的指针：

向循环双向链表和循环链表中插入或者从中删除数据只是多移动几个指针。
特点：
很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或删除元素时只需要改变前后两个元素节点的指针域指向地址即可，所以添加删除速度很快。

限制：
因含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

使用场景：
数据量较小，需要频繁添加删除操作的场景。

注意：
有一种说法是软件编程中只有两种数据结构：。其他数据结构都是基于这两种数据结构的演化，由此可见数组和链表这两种数据结构的重要性。

3.队列（Queue）

队列实现了先入先出的语义，队列也可以使用数组和链表来实现。队列也是一种线性表 。不同的是，队列可以在一端添加元素，在另一端取出元素 。

特点：先进先出（FIFO）；
使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用，MQ消息顺序消费，集合对象的有序遍历。

队列（Queue）在java体系中。

ArrayDeque基于数组实现的双向链表，可以满足队列先进先出（FIFO）的特性。

4.栈（Stack）

栈或者称为堆栈，栈是一种特殊的线性表（桶状线性数据结构）。仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作 。

5.散列表（Hash）

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。针对某个数据的等值查询时间复杂度为O(1)。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构案是肯定的，这就是我们要提起的哈希表。

优点：一对一的查找效率很高；
缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。
hash冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。

哈希表是种数据结构，它可以提供快速的插入操作和快速精确查找操作。

在java体系中，HashMap就是典型的散列表（Hash）结构。
其底层实现就是：

定义树的一个节点：

注意：
树可以理解成一种特殊的链表结构。

7.堆（Heap）

**堆（Heap）**是计算机科学中一类特殊的数据结构的统称，堆通常是一个可以被看做一棵完全二叉树的数组对象，根节点可以为大于等于任何子节点（也可以小于等于任意子节点，看具体的排序方法），在存取时没有任何限制，可以随意的访问某一个子节点。最大堆：每个节点的值都大于等于它的孩子节点。最小堆：每个节点的值都小于等于它的孩子节点。

注意：
特别要声明和注意的是，这里的堆仅仅是存储数据的一种结构方式，与内存的堆栈不是一个概念。

特点：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的作用：

• 构建优先队列
• 支持堆排序
• 快速找出一个集合中的最小值（或者最大值）

堆和普通树的区别
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

• 节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

• 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。

• 平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

• 搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

优先队列：出队与入队时的顺序无关，与优先级有关。
堆是优先队列这种数据结构的一种实现方式。

来源：斗者_2013