共计 3885 个字符，预计需要花费 10 分钟才能阅读完成。
本文摘自：缄默王二
百度百科对数据结构的定义是：相互之间存在一种或多种特定关系的数据元素的汇合。定义很形象，须要大声地朗诵几遍，才有点感觉。怎么让这种感觉来得更强烈，更亲切一些呢？我来列举一下常见的 8 种数据结构，数组、链表、栈、队列、树、堆、图、哈希表。
这 8 种数据结构有什么区别呢？
①、数组
长处：
- 依照索引查问元素的速度很快；
- 依照索引遍历数组也很不便。
毛病：
- 数组的大小在创立后就确定了，无奈扩容；
- 数组只能存储一种类型的数据；
- 增加、删除元素的操作很耗时间，因为要挪动其余元素。
②、链表
《算法（第 4 版）》一书中是这样定义链表的：
链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的援用，该节点还有一个元素和一个指向另一条链表的援用。
Java 的 LinkedList 类能够很形象地通过代码的模式来示意一个链表的构造：
public class LinkedList<E> {
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
这是一种双向链表，以后元素 item 既有 prev 又有 next，不过 first 的 prev 为 null，last 的 next 为 null。如果是单向链表的话，就只有 next，没有 prev。
单向链表的毛病是只能从头到尾顺次遍历，而双向链表可进可退，既能找到下一个，也能找到上一个——每个节点上都须要多调配一个存储空间。
链表中的数据依照“链式”的构造存储，因而能够达到内存上非间断的成果，数组必须是一块间断的内存。
因为不用依照程序的形式存储，链表在插入、删除的时候能够达到 O(1) 的工夫复杂度（只须要从新指向援用即可，不须要像数组那样挪动其余元素）。除此之外，链表还克服了数组必须事后晓得数据大小的毛病，从而能够实现灵便的内存动静治理。
长处：
- 不须要初始化容量；
- 能够增加任意元素；
- 插入和删除的时候只须要更新援用。
毛病：
- 含有大量的援用，占用的内存空间大；
- 查找元素须要遍历整个链表，耗时。
③、栈
栈就如同水桶一样，底部是密封的，顶部是闭口，水能够进能够出。用过水桶的小伙伴应该明确这样一个情理：先进去的水在桶的底部，后进去的水在桶的顶部；后进去的水先被倒进去，先进去的水后被倒进去。
同理，栈依照“后进先出”、“先进后出”的准则来存储数据，先插入的数据被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始顺次读出。
④、队列
队列就如同一段水管一样，两端都是闭口的，水从一端进去，而后从另外一端进去。先进去的水先进去，后进去的水后进去。
和水管有些不同的是，队列会对两端进行定义，一端叫队头，另外一端就叫队尾。队头只容许删除操作（出队），队尾只容许插入操作（入队）。
留神，栈是先进后出，队列是先进先出——两者尽管都是线性表，但准则是不同的，构造不一样嘛。
⑤、树
树是一种典型的非线性构造，它是由 n（n>0）个无限节点组成的一个具备档次关系的汇合。
之所以叫“树”，是因为这种数据结构看起来就像是一个倒挂的树，只不过根在上，叶在下。树形数据结构有以下这些特点：
- 每个节点都只有无限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点能够分为多个不相交的子树。
下图展现了树的一些术语：
根节点是第 0 层，它的子节点是第 1 层，子节点的子节点为第 2 层，以此类推。
- 深度：对于任意节点 n，n 的深度为从根到 n 的惟一门路长，根的深度为 0。
- 高度：对于任意节点 n，n 的高度为从 n 到一片树叶的最长门路长，所有树叶的高度为 0。
树的品种有很多种，常见的有：
- 无序树：树中任意节点的子节点之间没有程序关系。那怎么来了解无序树呢，到底长什么样子？
如果有三个节点，一个是父节点，两个是同级的子节点，那么就有三种状况：
如果有三个节点，一个是父节点，两个是不同级的子节点，那么就有六种状况：
三个节点组成的无序树，合起来就是九种状况。
- 二叉树：每个节点最多含有两个子树。二叉树依照不同的表现形式又能够分为多种。
齐全二叉树：对于一颗二叉树，假如其深度为 d（d > 1）。除了第 d 层，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右间断地严密排列，这样的二叉树被称为齐全二叉树。
拿上图来说，d 为 3，除了第 3 层，第 1 层、第 2 层 都达到了最大值（2 个子节点），并且第 3 层的所有节点从左向右分割地严密排列（H、I、J、K、L），合乎齐全二叉树的要求。
满二叉树：一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式，第一种，像下图这样（每一层都是满的），满足每一层的节点数都达到了最大值 2。
第二种，像下图这样（每一层尽管不满），但每一层的节点数依然达到了最大值 2。
二叉查找树：英文名叫 Binary Search Tree，即 BST，须要满足以下条件：
- 任意节点的左子树不空，左子树上所有节点的值均小于它的根节点的值；
- 任意节点的右子树不空，右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也别离为二叉查找树。
基于二叉查找树的特点，它相比拟于其余数据结构的劣势就在于查找、插入的工夫复杂度较低，为 O(logn)。如果咱们要从上图中查找 5 个元素，先从根节点 7 开始找，5 必然在 7 的左侧，找到 4，那 5 必然在 4 的右侧，找到 6，那 5 必然在 6 的左侧，找到了。
现实状况下，通过 BST 查找节点，所须要查看的节点数能够减半。
均衡二叉树：当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度均衡的二叉树，依据科学家的英文名也称为 AVL 树。
均衡二叉树实质上也是一颗二叉查找树，不过为了限度左右子树的高度差，避免出现歪斜树等偏差于线性构造演变的状况，所以对二叉搜寻树中每个节点的左右子树作了限度，左右子树的高度差称之为均衡因子，树中每个节点的均衡因子绝对值不大于 1。
均衡二叉树的难点在于，当删除或者减少节点的状况下，如何通过左旋或者右旋的形式来放弃左右均衡。
Java 中最常见的均衡二叉树就是红黑树，节点是红色或者彩色，通过色彩的束缚来维持着二叉树的均衡：
1）每个节点都只能是红色或者彩色
2）根节点是彩色
3）每个叶节点（NIL 节点，空节点）是彩色的。
4）如果一个节点是红色的，则它两个子节点都是彩色的。也就是说在一条门路上不能呈现相邻的两个红色节点。
5）从任一节点到其每个叶子的所有门路都蕴含雷同数目的彩色节点。
- B 树：一种对读写操作进行优化的自均衡的二叉查找树，可能保持数据有序，领有多于两个的子树。数据库的索引技术里就用到了 B 树。
⑥、堆
堆能够被看做是一棵树的数组对象，具备以下特点：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵齐全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
⑦、图
图是一种简单的非线性构造，由顶点的有穷非空集合和顶点之间边的汇合组成，通常示意为：G（V，E），其中，G 示意一个图，V 是图 G 中顶点的汇合，E 是图 G 中边的汇合。
上图共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。
在线性构造中，数据元素之间满足惟一的线性关系，每个数据元素（除第一个和最初一个外）均有惟一的“前驱”和“后继”；
在树形构造中，数据元素之间有着显著的档次关系，并且每个数据元素只与上一层中的一个元素（父节点）及下一层的多个元素（子节点）相干；
而在图形构造中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相干。
⑧、哈希表
哈希表（Hash Table），也叫散列表，是一种能够通过关键码值（key-value）间接拜访的数据结构，它最大的特点就是能够疾速实现查找、插入和删除。
数组的最大特点就是查找容易，插入和删除艰难；而链表正好相同，查找艰难，而插入和删除容易。哈希表很完满地联合了两者的长处，Java 的 HashMap 在此基础上还退出了树的长处。
哈希函数在哈希表中起着⾮常要害的作⽤，它能够把任意长度的输出变换成固定长度的输入，该输入就是哈希值。哈希函数使得一个数据序列的拜访过程变得更加迅速无效，通过哈希函数，数据元素可能被很快的进行定位。
若关键字为 k，则其值寄存在 hash(k) 的存储地位上。由此，不须要遍历就能够间接获得 k 对应的值。
对于任意两个不同的数据块，其哈希值雷同的可能性极小，也就是说，对于一个给定的数据块，找到和它哈希值雷同的数据块极为艰难。再者，对于一个数据块，哪怕只改变它的一个比特位，其哈希值的改变也会十分的大——这正是 Hash 存在的价值！
只管可能性极小，但依然会产生，如果哈希抵触了，Java 的 HashMap 会在数组的同一个地位上减少链表，如果链表的长度大于 8，将会转化成红黑树进行解决——这就是所谓的拉链法（数组 + 链表）。
加个好玩的总结：吃了拉进去是队列，吃了进去是栈。
说句实在话，照这个进度恶补上来，我感觉要秃的节奏，不过，如果可能变得更强，值了——对，值了。
