前几天和敖兵沟通过。他说我们作家在不断的燃烧自己，所以需要不断的加油。 我不能再认同他的观点了——于是我开始补计算机基础知识，包括我比较薄弱的数据结构。 百度将数据结构定义为相互之间具有一种或多种特定关系的数据元素的集合。 定义很笼统，需要大声读几遍才有感觉。 如何让这种感觉更强烈，更亲切？我来列举八种常见的数据结构:数组、链表、栈、队列、树、堆、图和哈希表。 这八种数据结构有什么区别？①数组的优点:根据索引查询元素非常快；通过索引遍历数组也很方便。 缺点:数组的大小是创建后确定的，不能扩展；数组只能存储一种类型的数据；添加和删除元素的操作非常耗时，因为必须移动其余的元素。 ②链表《算法》(第四版)这本书对链表的定义是这样的:链表是一种递归的数据结构，它要么是空的，要么是对一个节点的引用，这个节点有一个元素和对另一个链表的引用。 Java LinkedList类可以用代码的形式形象地表示链表的结构:public class Linked List < E & gt{瞬时节点& ltE & gt第一；瞬时节点& ltE & gt最后；私有静态类节点& ltE & gt{ E项；节点& ltE & gt接下来；节点& ltE & gtprev节点(节点& ltE & gtprev，E元素，节点& ltE & gtnext){ this . item = element；this.next = nextthis.prev = prev}}}这是一个双链表。当前元素项既有prev又有next，但第一个的prev为空，最后一个的next为空。 如果是单向链表，只有next，没有prev。 单向链表的缺点是只能从头到尾遍历，而双向链表可以来回遍历，既可以找到下一个，也可以找到上一个——每个节点需要多分配一个存储空间。 链表中的数据以“链式”结构存储，因此可以达到不连续存储的效果。该数组必须是连续的内存。 因为不需要顺序存储链表，所以插入和删除链表的时间复杂度可以达到O(1)(只要你想重新指向引用，就不需要像数组一样移动其他元素)。 此外，链表还克服了数组必须事先知道数据大小的缺点，实现了灵活的动态内存管理。 优点:无需初始化容量；您可以添加任何元素；插入和删除时，只需升级引用即可。 缺点:包含大量引用，占用内存空间大；查找元素需要遍历整个链表，需要时间。 (3)堆栈就像一个水桶，底部是密封的，顶部是敞开的，水可以进出。 用过水桶的朋友应该明白这个道理:先进去的水在桶底，后进去的水在桶顶；进去的水先倒出来，先进去的水后倒出来。 同样，堆栈按照“后进先出”和“先入后出”的原则存储数据。第一个插入的数据被推到堆栈的底部，后面插入的数据在堆栈的顶部。读取数据时，从栈顶依次读取。 (4)队列队列就像一段水管，两头敞开。水从一端进入，然后从另一端出来。 先进的水先出来，后面进去的水再出来。 和水管不同，队列定义了两端，一端叫队列头，另一端叫队列尾。 只有删除操作(出列)允许在队列的头部，插入操作(入队)允许在队列的尾部。 注意，栈是FIFO，队列是FIFO——虽然两者都是线性表，但规则和结构不同。 ⑤ Tree-tree是一种典型的非线性结构，由n (n >: 0)个具有层次关系的有限节点集合组成。 之所以称之为“树”，是因为这种数据结构看起来像一棵倒挂的树，只不过根在上面，叶子在下面。 树形数据结构具有以下特点:每个节点只有有限数量的子节点或没有子节点；没有父节点的节点称为根节点；每个非根节点只有一个父节点；除了根节点之外，每个子节点都可以分成多个不相交的子树。 下图显示了树的几个术语:根节点是0级，其子节点是1级，子节点的子节点是2级，以此类推。 深度:对于任意节点N，N的深度是从根到N的唯一路径长度，根的深度为0。 高度:对于任意节点N，N的高度是从N到一片叶子的最长路径长度，所有叶子的高度都是0。 树有很多种，常见的有:无序树:树中任意节点的子节点之间没有顺序关系。 那你怎么知道无序树，它长什么样？如果有三个节点，一个是父节点，两个是同一级别的子节点，那么就有三种情况:如果有三个节点，一个是父节点，两个是不同级别的子节点，那么就有六种情况:三个节点组成的无序树，组成九种情况。 二叉树:每个节点最多包含两个子树。 根据二叉树的不同形式，可以分为很多种。 完全二叉树:对于二叉树，假设其深度为d (d >: 1) 除了D层，其他层的节点数都达到了最大值，D层的所有节点都是从左到右连续紧密排列的。这样的二叉树叫做完全二叉树。 如图，D为3。除了第三层，第一层和第二层都达到了最大值(2个子节点)，第三层所有节点从左到右紧密排列(H，I，J，K，L)，符合一棵完整二叉树的要求。 全二叉树:每层节点数最大的二叉树。 有两种形式。首先如下图所示(每一层都是满的)，满足每一层的节点数达到了最大值2。 第二，如下图(虽然每层都不满意)，每层的节点数仍然达到最大值2。 二叉查找树:英文名为二叉查找树，即BST，需要满足以下条件:任意节点的左子树不为空，且左子树中所有节点的值小于其根节点的值；任意节点的右子树不为空，右子树中所有节点的值大于其根节点的值；任何节点的左右子树也是二分搜索法树。 基于二叉查找树的特点，与其他数据结构相比，其优势在于查找和插入的时间复杂度低，为O(logn) 如果要从上图中找到五行，就要从根节点7开始，5一定在7的左边，找到4，那么5一定在4的右边，找到6，那么5一定在6的左边，找到了。 理想情况下，通过BST搜索节点，要检查的节点数量可以减半。 平衡二叉树:当且仅当任一节点的两个子树之间的高度差不大于1时，才是二叉树。 前苏联数学家Adelse-Velskil和Landis在1962年提出的高度平衡二叉树，根据科学家的英文名字也叫AVL树。 平衡二叉树本质上是一个二叉查找树。但是，为了限制左右子树的高度差，避免倾斜的树趋向于线性结构演化的情况，二叉查找树中每个节点的左右子树都受到限制。左右子树的高度差称为平衡因子，树中每个节点的平衡因子的绝对值不大于1。 平衡二叉树的难点在于删除或添加节点时，如何通过向左或向右旋转来保持左右平衡。 Java中最常见的平衡二叉树是红黑树。节点为红色或黑色，二叉树的平衡由颜色约束来维持:1)每个节点只能是红色或黑色；2)根节点为黑色；3)每个叶节点(空节点，空节点)都是黑色的。 4)如果一个节点是红色的，它的两个子节点都是黑色的。 也就是说，两个相邻的红色节点不能出现在一条路径上。 5)从任何节点到每个叶子的所有路径包含相同数量的黑色节点。 B-tree:一种自平衡二叉查找树，可以优化读写操作。它可以保持数据有序，并且有两个以上的子树。 b树用于数据库的索引技术。 ⑥堆可以看作一棵树的数组对象，它具有以下特征:堆中一个节点的值总是不大于或小于其父节点的值；总是堆一个完整的二叉树。 根节点最大的堆称为最大堆或大根堆，根节点最小的堆称为最小堆或小根堆。 ⑦图图是一个复杂的非线性结构，它由一个有限的非空的顶点集和顶点之间的一组边组成。通常表示为:G(V，E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 上图中有四个顶点V0、V1、V2和V3，四个顶点之间有五条边。 在线性结构中，数据元素满足唯一的线性关系，每个数据元素(除了第一个和最后一个)都有唯一的“前任”和“继任者”；在树形结构中，数据元素之间存在显著的层次关系，每个数据元素只与上层的一个元素(父节点)和下层的几个元素(子节点)相关。在图结构中，节点之间的关系是任意的，并且图中的任意两个数据元素可能是相关的。 ⑧哈希表Hash Table也称哈希表，是一种可以通过键值直接访问的数据结构。它最大的特点是可以快速查找、插入和删除。 array最大的特点就是容易找到，但是很难插入和删除。相反，链表很难找到，但很容易插入和删除。 哈希表完美结合了两者的优点，Java HashMap在此基础上增加了tree的优点。 哈希函数在哈希表中起着重要的作用。它可以将任意长度的输入转换为固定长度的输出，即哈希值。 哈希函数使数据序列的访问过程更快、更有效。通过哈希函数，可以快速定位数据元素。 如果关键字是k，它的值存储在hash(k)的存储位置 所以不需要遍历就可以直接得到k对应的值。 任何两个不同的数据块具有相同的哈希值的可能性极小，也就是说，对于给定的数据块，要找到具有相同哈希值的数据块是极其困难的。 再者，对于一个数据块来说，哪怕只改变其中的一位，其hash值的变化也会非常大——这就是Hash存在的价值！虽然可能性极小，但还是会发生。如果哈希冲突，Java的HashMap会在数组的相同位置添加一个链表。如果链表长度大于8，就转换成红黑树来求解——这就是所谓的拉链法(数组+链表)。 说实话，这样的步伐我觉得自己秃了，但如果我能变得更强，那就值了——是的，会的。 也有几个朋友想让我推荐几本算法和数据结构方面的书。我在GitHub上收集了几本热门书籍，你可以点击链接下载。希望我的心能帮到你。 链接:https://pan.baidu.com/s/1rB-CCjjpKPidOio7Ov_0YA密码:g5pl我是沉默的王二，一个沉默却有趣的程序员。注意力可以提高学习效率。 喜欢这篇文章的朋友，请不要忘记四联，喜欢，收藏，转发，留言。你是最漂亮最帅的！