今天我们来学习数据结构，对于扎实Java基本功很有用。学会了，你会觉得自己是个大老板，嘿嘿。数据结构，即DataStructure，是一种用于存储数据的结构。数据与数据之间存在一定的关系。这种关系包括数据的逻辑关系、数据的存储关系和数据的计算关系。在Java中，数据结构一般可以分为两类：线性数据结构和非线性数据结构。哈哈，这个非角色是有灵魂的吧？先说线性数据结构。1）数组一目了然，像String[]、int[]；还有一些东西需要看两遍（看源码），比如ArrayList，内部封装了数组。数组数据结构的最大优点是可以根据下标（或索引）进行操作。插入的时候可以直接根据下标插入到具体的位置，但是同时后面的元素都需要向后移动，需要移动的数据越多，就越累。假设我们已经有一个ArrayList，我们要在第4个位置（下标3）添加一个元素55。此时ArrayList中第5个位置之后的元素会向后移动。准备从ArrayList中删除23。此时，下标为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），每个节点包含三项：一是元素本身，二是下一个元素的引用地址，三是前一个元素Referrer的地址。LinkedList看起来是这样的：第一个节点没有前一个节点，所以prev为null；最后一个节点没有下一个节点，所以next为null；这是一个双向链表，每个节点由三个部分组成，前后节点和值。与ArrayList相比，LinkedList有以下优点：1.LinkedList允许动态分配内存，这意味着内存分配由编译器在运行时完成，我们不需要在声明LinkedList时指定大小。2、LinkedList不需要在连续的位置存储元素，因为一个节点可以通过引用指定下一个节点或前一个节点。也就是说，LinkedList在插入和删除元素时的成本非常低，因为不需要移动其他元素，只需要更新上一个节点和下一个节点的引用地址。3）栈是一种很有用的数据结构。它就像一堆盘子。第一个放在底部，第二个放在第一个上面，第三个放在第二个上面，最后一个放在上面。栈遵循后进先出的原则，也就是“后进先出”（简称LIFO）——最后一个进来，第一个出去。对于栈这样的数据结构，它有两个常见的动作：push，中文解释有很多，我个人更喜欢叫它“push”，很形象。当我们要将一条数据放到栈顶时，这个动作就叫做push。pop，一样的，我个人更喜欢叫它“pop”，有很强的动画效果，有没有？当我们要从栈中取出一条数据时，这个动作就叫做出栈。4）QueueQueue只允许在队尾添加数据，在队头移除数据。队列在Java中出现频率很高，并且有各种各样的类来满足不同场景的需要。像优先队列PriorityQueue，延迟队列DelayQueue等等。队列遵循FirstInFirstOut，简称FIFO，即先进先出，第一个进入队列的先出来。让我们谈谈非线性数据结构。1）树树是一种典型的非线性结构，它是由n（n>0）个有限节点组成的层次关系的集合。之所以叫“树”，是因为这个数据结构看起来像一棵倒过来的树，只是根在上面，叶子在下面。树型数据结构具有以下特点：每个节点只有有限数量的子节点或没有子节点；没有父节点的节点称为根节点；每个非根节点只有一个父节点；一个子节点可以分成多个不相交的子树。下图显示了树的一些术语：根节点为0级，其子节点为1级，其子节点的子节点为2级，依此类推。深度：对于任意节点n，n的深度是从根到n的唯一路径的长度，根的深度为0。高度：对于任意节点n，n的高度是最长的长度n到一片叶子的路径，所有叶子的高度都为0。树可以细分为以下几种类型：1.普通树：对子节点没有约束。2.二叉树：每个节点最多包含两个子节点的树。二叉树根据不同的表现形式可以分为很多种。2.1.普通二叉树：每个子节点的父节点不一定是有两个子节点的二叉树。2.2.完全二叉树：对于一棵二叉树，假设它的深度为d（d>1）。除第d层外，其他层的节点个数都达到了最大值，第d层的所有节点都是从左到右连续紧密排列。2.3.满二叉树：每层节点数达到最大值的二叉树。有两种表达形式。第一种，如下图（每一层都是满的），满足每层的节点数都达到了最大值2。3、二叉搜索树：英文名BinarySearchTree，即BST，需要满足以下条件：任意节点的左子树不为空，且左子树上所有节点的值都小于其根节点的值；任一节点的右子树都不为空，且右子树上所有节点的值都大于其根节点的值；任何节点的左子树和右子树也是二叉搜索树。3.1.平衡二叉树：二叉树当且仅当任意节点的两个子树的高度差不大于1。前苏联数学家Adelse-Velskil和Landis在1962年提出的高度平衡二叉树也是按照科学家的英文名字叫AVL树。平衡二叉树本质上是二叉搜索树，但是为了限制左右子树的高度差，避免出现倾向于线性演化的偏斜树，二叉搜索中每个节点的左右子树树的制作除了限制，左右子树的高度差称为平衡因子，树中每个节点的平衡因子的绝对值不大于1。平衡一棵二叉树的难度就是在删除或添加节点时，左撇子或右撇子如何保持左右平衡。红黑树是一种常见的平衡二叉树。节点是红色或黑色，通过颜色约束来维持二叉树的平衡：每个节点只能是红色或黑色。根节点是黑色的，每个叶子节点（NIL节点，空节点）都是黑色的。如果一个节点是红色的，那么它的两个孩子都是黑色的。也就是说，一条路径上不能出现两个相邻的红色节点。从任何节点到其每个叶子的所有路径都包含相同数量的黑色节点。4.B树：一种针对读写操作优化的自平衡二叉搜索树，可以保持数据有序，有两个以上的子树。5.B+树：B树的变种。HashMap中的TreeNode使用的是红黑树，而B-tree和B+树在数据库的索引原理上有典型的应用。2）哈希表哈希表（HashTable），也叫哈希表，是一种可以通过键值（key-value）直接访问的数据结构。它最大的特点是可以快速实现查找、插入和删除。使用的算法称为哈希，将任意长度的输入转换为固定长度的输出，输出就是哈希值。使用像MD5和SHA1这样的哈希算法。每个Java对象都有一个哈希值。默认情况下，hash算法是通过调用本地方法计算对象的内存地址+对象的value的key值来执行的。数组最大的特点就是查找容易，插入删除困难；而链表恰恰相反，很难找到，但很容易插入和删除。哈希表完美的结合了两者的优点，Java的HashMap也在这个基础上增加了树的优点。哈希表具有较快的（常量级）查询速度和相对较快的增删改查速度，因此非常适合在海量数据环境中使用。对于任意两个不同的数据块，哈希值相同的可能性是极小的，即对于给定的数据块，要找到一个哈希值相同的数据块是极其困难的。再者，对于一个数据块来说，哪怕只是改变了其中的一位，其哈希值的变化也会非常大——这正是Hash的值！虽然可能性极小，但还是会发生。如果hash有冲突，Java的HashMap会在数组的相同位置添加一个链表。如果链表的长度大于8，就会转成红黑树进行处理——这就是所谓的拉链法（数组+链表）。3）图是由有限的非空顶点集和顶点间的边集组成的复杂非线性结构，通常表示为：G(V,E)，其中G表示一个图，V是顶点的集合在图G中，E是图G中边的集合。上图有4个顶点V0、V1、V2、V3，4个顶点之间有5条边。在线性结构中，数据元素之间存在唯一的线性关系，每个数据元素（第一个和最后一个除外）都有唯一的“前任”和“后继”；在树形结构中，数据元素之间存在明显的层次关系，每个数据元素只与上层的一个元素（父节点）和下层的多个元素（子节点）相关；而在图结构中，节点之间的关系是任意的，图中任意两个数据元素之间都可能存在关联。
