本文转载自微信公众号“bigsai”，作者bigsai。转载本文请联系bigsai公众号。前言数据结构和算法是程序员内功的重要标准之一，数据结构也用在了方方面面。业界有一个程序=数据结构+算法的等式。各种中间件开发人员和架构师都在努力优化中间件、项目结构和算法，以提高运行效率和减少内存使用，其中数据结构发挥了非常重要的作用。另外，数据结构中还包含了一些面向对象的思想，所以学习掌握数据结构，逻辑思维的抽象能力会大大提高。为什么要研究数据结构和算法？如果你还是学生，那这门课就是必修课，考研基本上是必修课。内向严重的大厂找工作的数据结构和算法，也是面试和笔试必备的一个非常重要的考察点。如果在数据结构和算法上下功夫，也是内功提升的一个很重要的体现。对于程序员来说，想要得到满意的结果，数据结构和算法是必备的技能！数据结构的概念数据结构是计算机存储和组织数据的方式。数据结构是相互之间具有一个或多个特定关系的数据元素的集合。通常，精心选择的数据结构可以带来更高的操作或存储效率。简而言之，数据结构是由一系列存储结构按照一定的执行规则和一定的执行算法形成的高效存储结构。在我们熟悉的关系数据库、非关系数据库、搜索引擎存储、消息队列等，都是大规模数据结构比较好的应用。当然，这些应用中间件不应只考虑简单的结构问题。还考虑了其??他因素，例如实际操作系统和网络。以及数据结构和算法的专栏。我们程序员首先要掌握的是运行在内存中的抽象数据结构。是一种比较单一的数据结构，如线性结构、树、图等。数据结构和算法中的相关术语，数据，数据对象，数据元素，数据项，很多人搞不清楚它们之间的关系他们。下面我们通过画图来看一下，然后举个例子和大家分享一下。用户信息表usersidnamesex001bigsaiman002smallsaiman003CaiXukunwomanListlist;//数据对象listclassusers{//缩写intid;Stringname;Stringsex;}//list和woman均为数据Listlist;//dataobjectlistListwoman;//数据对象womanlist.add(newusers(001,"bigsai","man"));//添加数据元素一个users由三个数据项(001,bigsai,man)组成list.add(newusers(002,"smallsai","man"));//数据元素list.add(newusers(003,"蔡徐坤","woman"));//数据元素woman.add(list.get(2));//003，由“蔡徐坤”和“女人”三个数据项组成的数据元data：客观事物的符号表示，指所有可以输入计算机的数据和由计算机使用程序处理的符号集合的统称。上表中的三个用户信息记录是数据（多表多集合可能只有一个）。这些数据一般由用户输入或由自定义结构完成。当然，有些图像和声音也是数据。数据元素：数据元素是数据的基本单位。一个数据元素由多个数据项组成！可以认为是一个pojo对象或者数据库中的一条记录。比如蔡徐坤的记录就是一个数据元素。数据项：用户字段/属性包括id、姓名、性别等，这些都是数据项。数据项是构成数据元素的最小的不可分割字段。可以看成是一个pojo对象的值，也可以看成是一个表（人）的属性/字段。数据对象：是具有相同性质的数据元素的集合。是数据的一个子集。比如上面的users表，list集合，woman集合都是数据对象。一个表，一个集合可以是一个数据对象。一般来说，数据的范围是最广的，所有的数据都是数据，数据对象只是一个性质相同的集合。这个集合是数据的子集，但不是数据的基本单位，数据元素是数据的基本单位。比如cat和dog这两个表都是数据，cat这个表是一个数据对象（因为他们都是描述cat对象），但是数据的基本单位不是cats和dogs，而是它们各自具体的item，比如小猫1号、大猫2号、哈士奇1号、藏獒2号是数据的基本单位。很容易混淆数据类型和抽象数据类型。注意区分：数据类型原子类型：其值不能进一步划分的类型。如int、char、double、float等。结构类型：一种数据类型，其值可以细分为组件。例如，由结构构造的各种结构等。抽象数据类型（ADT）：抽象数据类型（ADT）是一种实现，包括用于存储数据元素的存储结构和用于实现基本操作的算法。可以在不考虑其实现细节的情况下研究和使用其结构。比如我们在使用List、Map、Set等时只需要了解它的api以及属性和功能即可，具体实现可能会有不同的方案。例如，List的实现对数组和链表有不同的选择。三元素逻辑结构：数据元素之间的逻辑关系。逻辑结构分为线性结构和非线性结构。线性结构有时序表、链表等。非线性是指集合、树和图等结构。存储结构：数据结构在计算机中的表示（也称图像，也称物理结构），存储结构主要分为顺序存储、链式存储、索引存储和散列（hash）存储，这些存储类型通过下图简单看一下这张图（仅供理解，不考虑更多）：数据操作：应用于数据的操作包括操作的定义和实现，操作的定义基于逻辑结构，以及操作的实现基于存储结构。这里容易混淆的是逻辑结构和存储结构的概念。对于逻辑结构，不难看出logic这个词，逻辑关系就是在不考虑物理地址关系的情况下，两个数据之间的关系，比如线性结构和非线性结构，它们描述的是一种连接方式setofdata和form，他针对的是数据。我喜欢的是数据结构的功能。例如，线性表是有序的。我需要一个有序的集合来使用线性表。存储结构链接到物理地址。因为同样的逻辑结构采用不同的存储结构来实现适用的场景，性能可能会有所不同。比如如果也是线性表，那么存储结构的实现方式可能有多种。例如，顺序表和链表（Arraylist、Linkedlist）的存储结构不同，一种是顺序存储（数组）实现，一种是链表存储（链表）实现。它关注计算机运行的物理地址之间的关系。但通常同类型存储结构实现的一些数据结构具有一些相同点和不足点（线性易查难插入，链式易插入难查等）。算法分析上面讨论了数据结构相关的概念，下面介绍算法分析的一些概念。算法的五个重要特征：有限性、确定性、可行性、输入和输出。这些可以从字面理解，有限性强调算法结束时不能无限循环；确定性是指每条指令都有自己的意义，相同的输入得到相同的输出；可行性是指算法的每一步都需要经过多次执行才能实现；输入为0个或多个输入（可以为0）；输出是1个或多个输出（必须有一个输出）。对于一个好的算法，效率和空间资源占用（时间复杂度和空间复杂度）通常是比较重要的考虑因素。通常，复杂性更多地被描述为一个数量级，很少用具体数字来描述。空间复杂度的概念：是衡量一个算法在运行过程中临时占用存储空间大小的指标，记为S(n)=O(f(n))。算法的空间复杂度其实比较低（我们经常使用牺牲空间换取时间的数据结构和算法），但是空间复杂度的重要性不容忽视。无论是刷题还是实际项目制作记忆都是一个巨大的指标。对于Java来说更是如此。内存本身很大。如果使用的存储逻辑不好，会占用更多的系统资源，给服务带来压力。在许多情况下，该算法会牺牲空间换取时间（效率）。比如我们熟悉的字符串匹配String.contains()方法，我们都知道是暴力破解，时间复杂度为O(n^2)，不需要额外的内存。KMP算法在效率和速度上是原生的暴力方法，但是KMP需要使用其他数组（next[]）来进行标记存储操作。使用空间开销。再比如，归并排序在递归除法中也会使用新的数组进行逐级计算，提高效率，但增加内存开销影响不大。当然算法的最大空间开销不能超过jvm设置的最大值，一般为2G。(2147483645)如果打开一个二维数组和多个多维数据，不要打开太多，可能会导致heapOutOfMemoryError。时间复杂度概念：在计算机科学中，算法的时间复杂度是一个定性描述算法运行时间的函数。这是表示算法输入值的字符串长度的函数。时间复杂度通常用大O表示法表示，不包括该函数的低阶项和前导系数。当这样使用时，时间复杂度可以说是渐近的，看输入值的大小趋近于无穷大的情况。时间复杂度排序：O(1)
