大家好，我是沉默的王二。
今天我们来学一下数据结构方面的知识，对扎实Java的基本功非常有用，学会了就会有一种自带大佬的感觉，嘿嘿。数据结构，也就是DataStructure，是一种存储数据的结构体，数据与数据之间存在着一定的关系，这样的关系有数据的逻辑关系、数据的存储关系和数据的运算关系。
在Java中，数据结构一般可以分为两大类：线性数据结构和非线性数据结构。哈哈，这个非字很有灵*吧？
先来说线性数据结构吧。
1）数组
一眼看上去就知道的，像String[]、int[]这种；还有需要看两眼才能看透的（看源码了），像ArrayList，内部对数组进行了封装。
数组这种数据结构最大的好处，就是可以根据下标（或者叫索引）进行操作，插入的时候可以根据下标直接插入到具体的位置，但与此同时，后面的元素就需要全部向后移动，需要移动的数据越多，就越累。
假设现在已经有了一个ArrayList了，准备在第4个位置（下标为3）上添加一个元素55。
此时ArrayList中第5个位置以后的元素将会向后移动。
准备把23从ArrayList中移除。
此时下标为7、8、9的元素往前挪。
简单总结一下ArrayList的时间复杂度，方便大家在学习的时候作为参考。
1、通过下标（也就是get(intindex)）访问一个元素的时间复杂度为O(1)，因为是直达的，无论数据增大多少倍，耗时都不变。
2、添加一个元素（也就是add()）的时间复杂度为O(1)，因为直接添加到末尾。
3、删除一个元素的时间复杂度为O(n)，因为要遍历列表，数据量增大几倍，耗时也增大几倍。
4、查找一个未排序的列表时间复杂度为O(n)，因为要遍历列表；查找排序过的列表时间复杂度为O(logn)，因为可以使用二分查找法，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，每找一次排除一半的可能）。
2）链表
链表在物理存储空间是不连续的，但每个节点要么知道它的下一个节点是谁，要么知道它的上一个节点是谁，仿佛就像我们之间隔着千山万水，却心有灵犀一点链。像LinkedList就是最典型的链表结构，通过引用相互链接。
LinkedList中的每一个元素都可以称之为节点（Node），每一个节点都包含三个项目：其一是元素本身，其二是指向下一个元素的引用地址，其三是指向上一个元素的引用地址。
LinkedList看起来就像下面这个样子：
第一个节点由于没有前一个节点，所以prev为null；最后一个节点由于没有后一个节点，所以next为null；这是一个双向链表，每一个节点都由三部分组成，前后节点和值。相比ArrayList，LinkedList有以下优势：
1、LinkedList允许内存进行动态分配，这就意味着内存分配是由编译器在运行时完成的，我们无需在LinkedList声明的时候指定大小。
2、LinkedList不需要在连续的位置上存储元素，因为节点可以通过引用指定下一个节点或者前一个节点。也就是说，LinkedList在插入和删除元素的时候代价很低，因为不需要移动其他元素，只需要更新前一个节点和后一个节点的引用地址即可。
3）栈
栈是一种非常有用的数据结构，它就像一摞盘子，第一个放在最下面，第二个放在第一个上面，第三个放在第二个上面，最后一个放在最上面。栈遵循后进先出的原则，也就是“LastInFirstOut”（简称LIFO）——最后的一个进的，最先出去。
对于栈这样一个数据结构来说，它有两个常见的动作：
push，中文释义有很多种，我个人更喜欢叫它“压入”，非常形象。当我们要把一个数据放入栈的顶部，这个动作就叫做push。
pop，同样的，我个人更喜欢叫它“弹出”，带有很强烈的动画效果，有没有？当我们要从栈中移除一个数据时，这个动作就叫做pop。
4）队列
队列，只允许在队尾添加数据，队首移除数据。队列在Java中的出现频率非常高，有各种不同的类来满足不同的场景需求。像优先级队列PriorityQueue、延时队列DelayQueue等等。队列遵循的是FirstInFirstOut，缩写为FIFO，也就是先进先出，第一个进入队列的第一个先出来。
再来说非线性数据结构。
1）树
树是一种典型的非线性结构，它是由n（n0）个有限节点组成的一个具有层次关系的集合。之所以叫“树”，是因为这种数据结构看起来就像是一个倒挂的树，只不过根在上，叶在下。树形数据结构有以下这些特点：
每个节点都只有有限个子节点或无子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。下图展示了树的一些术语：
根节点是第0层，它的子节点是第1层，子节点的子节点为第2层，以此类推。
深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0。高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。树又可以细分为下面几种：
1、普通树：对子节点没有任何约束。
2、二叉树：每个节点最多含有两个子节点的树。二叉树按照不同的表现形式又可以分为多种。
2.1、普通二叉树：每个子节点的父节点不一定有两个子节点的二叉树。
2.2、完全二叉树：对于一颗二叉树，假设其深度为d（d1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列。
2.3、满二叉树：一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式，第一种，像下图这样（每一层都是满的），满足每一层的节点数都达到了最大值2。
3、二叉查找树：英文名叫BinarySearchTree，即BST，需要满足以下条件：
任意节点的左子树不空，左子树上所有节点的值均小于它的根节点的值；任意节点的右子树不空，右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树。3.1、平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。由前苏联的数学家Adelse-Velskil和Landis在年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。
平衡二叉树本质上也是一颗二叉查找树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于1。
平衡二叉树的难点在于，当删除或者增加节点的情况下，如何通过左旋或者右旋的方式来保持左右平衡。
红黑树是一种常见的平衡二叉树，节点是红色或者黑色，通过颜色的约束来维持着二叉树的平衡：
每个节点都只能是红色或者黑色根节点是黑色每个叶节点（NIL节点，空节点）是黑色的。如果一个节点是红色的，则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。4、B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树。
5、B+树：B树的变体。
HashMap里面的TreeNode就用到了红黑树，而B树、B+树在数据库的索引原理里面有典型的应用。
2）哈希表
哈希表（HashTable），也叫散列表，是一种可以通过关键码值（key-value）直接访问的数据结构，它最大的特点就是可以快速实现查找、插入和删除。其中用到的算法叫做哈希，就是把任意长度的输入，变换成固定长度的输出，该输出就是哈希值。像MD5、SHA1都用的是哈希算法。
每一个Java对象都会有一个哈希值，默认情况就是通过调用本地方法执行哈希算法，计算出对象的内存地址+对象的值的关键码值。
数组的最大特点就是查找容易，插入和删除困难；而链表正好相反，查找困难，而插入和删除容易。哈希表很完美地结合了两者的优点，Java的HashMap在此基础上还加入了树的优点。
哈希表具有较快（常量级）的查询速度，以及相对较快的增删速度，所以很适合在海量数据的环境中使用。
对于任意两个不同的数据块，其哈希值相同的可能性极小，也就是说，对于一个给定的数据块，找到和它哈希值相同的数据块极为困难。再者，对于一个数据块，哪怕只改动它的一个比特位，其哈希值的改动也会非常的大——这正是Hash存在的价值！
尽管可能性极小，但仍然会发生，如果哈希冲突了，Java的HashMap会在数组的同一个位置上增加链表，如果链表的长度大于8，将会转化成红黑树进行处理——这就是所谓的拉链法（数组+链表）。
3）图
图是一种复杂的非线性结构，由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
上图共有V0，V1，V2，V3这4个顶点，4个顶点之间共有5条边。
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素（除第一个和最后一个外）均有唯一的“前驱”和“后继”；
在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素（父节点）及下一层的多个元素（子节点）相关；
而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。
完蛋，怎么感觉飘了呀！
不过，我觉得最佳的治疗方案应该是继续点赞或者在看，嘿嘿。
预览时标签不可点收录于话题#个上一篇下一篇