数据结构那些事

本篇大多参考于《我的第一本算法书》，有兴趣的同学可以去购买阅读，书内有非常多的插图非常便于理解，也是比较推荐入门算法的一本书。

相信一定会让你对算法有很大程度的了解。当然如果有囊中羞涩的同学，也可以联系我下载电子版的。

什么是数据结构？

     在学习任何东西前我们得先知道他是什么，他是用来干嘛的，这是学习一样东西的惯性思维;

     数据结构这一名词其实在开发中经常用到，从字面意思我们也可以知道它是指代组织数据的结构描述，我们经常问到到的就是在与前端或者后端对接api时会问到“接口的传参数据结构发一下”类似话语，而我们平时用到的这个名词确实是字面意思，当然如果是这样的话这篇博客也就到这里了。

     而我接下来要说的就是更加学术化，专业化上所认知的数据结构。

     我们先看看百度百科怎么说的：

“数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。”

     我们可以看到，在百度百科的解释里出现了很多陌生的名词词汇，当然我们可以先忽略他们，从中提取重要信息点：“精心选择的数据结构可以带来更高的运行或者存储效率。”，从这句话我们可以知道，数据结构在编程世界里的重要地位，为什么这么说呢？作为一名合格的程序员你应当知道，高速度低损耗是所有程序设计的终极目标，而数据结构的实际作用主要在计算机底层（这里的话需要你有一定的计算机原理知识可能才能看懂这句），从底层优化永远是比你在外层优化要得到收益更高的。其实说这么多，也还没有对数据结构这一名词进行一句话的总结，其实在我看来数据结构无非就是：

     “同样的数据，你用不同的组织方式决定了数据的顺序和位置关系传输给了电脑。”

     想要算法学的好，数据结构少不了。

     磨练算法会让个人的编程思维指数性上升，短时间的提升是很大的，当然也对个人的未来发展起关键作用。

（算法的重要性我会在一篇博客专门说到）–鸽警告

电话簿里的数据结构

     不管是电脑还是任何发明都是人类智慧的结晶，而是这些结晶一定是能从现实生活中找到它们的影子的。（科学技术一定是符合宇宙规律的，生活也是）。

     所以数据结构也是能在现实生活中找到影子的，我们就说电话薄吧，相信90后应该都多多少少用过，00后也应该听说过，在那个没有手机的年代只有大哥大和电话的时代，电话薄充当的就是我们现在手机自带的“联系人”app这一角色的，而我们等会讲到的电话薄就是一个典型的连续性数组结构。

     假设我们现在有 1 个电话簿，它是纸质电话簿（废话），每当我们得到了新的电话号码，就按从上往下的顺序把它们记在电话簿上

姓名	电话号码
武小小	010-uuuu-uuuu
田美丽	010-xxxx-xxxx
王野	010-yyyy-yyyy
小明	021-zzzz-zzzz
……	……

     假设我们现在要给小明打电话，但是我们现在并不知道小明的电话号码，而电话簿都是从上到下排的，因此我们去电话簿查找小明的电话号码时并不知道小明的电话具体排在哪个位置，所以就需要从上往下一个一个的去对去找（当然我们也可以从下往上，也可以随机一个位置去找，但是这都不一定比从上往下找要快。），就像上图所示电话薄存的电话号码比较少我们一眼就看到了小明的电话号码，但是当我们的电话簿中的号码数量为500时显然找起来就不是那么简单了。

     应该有些同学看到这里的时候就有感而发了：“欸，这不是遍历集合嘛？”。所以确实如同我上面所说的“科学技术一定是符合宇宙规律的，生活也是”。虽说也是遍历集合，但是好在我们人眼一下子可以看好几条，而计算机只会一条一条读（忽略多线程），话是这样不过还是计算机快啊，别人一秒可以计算1 万亿次，你可以吗？！！(〃￣︶￣)人(￣︶￣〃)

500条电话号码怎么去快速查找呢？

     接下来，我们试试以联系人姓名的拼音顺序排列吧。因为数据都是以字典顺序（a~z，别告诉我你拼音都不会）排列的，所以它 们是有“结构”的。

姓名	电话号码
啊小小	010-uuuu-uuuu
部美丽	010-xxxx-xxxx
小野	010-yyyy-yyyy
小明	021-zzzz-zzzz
……	……

     使用这种方式给联系人排序的话，想要找到目标人物就轻松多了。通过姓名的拼音首字母 就能推测出该数据的大致位置，我们可以直接定位在第一个名字以小为开头的人的位置，从这个位置开始读，读到名字开头不是小的人时就可以说根本没有小明这个人。

     但是！这个时候又出现了新的问题，如果我们后续需要添加新的联系人到电话簿时怎么办？（现在我们是纸质电话薄，再次废话）同样我们还是跟查一样，我们现在加入小红的联系方式，我们直接定位到第一个名字开头为小的人的位置，直接把名字写在他下面。只是想象很美好现实很骨感，纸质电话簿你只能撕掉全部重写，当然如果走运也可以加在最后（小开头刚好在最后）。这显然比之前无脑往后面写麻烦的多。

当然就算是计算机去这样新增电话，也会导致后续电话坐标全部移动一格，这显然也不优雅。

两种方法的优缺点

     总的来说，数据按获取顺序排列的话，虽然添加数据非常简单，只需要把数据加在最后就 可以了，但是在查询时较为麻烦；以拼音顺序来排列的话，虽然在查询上较为简单，但是添加 数据时又会比较麻烦。

     虽说这两种方法各有各的优缺点，但具体选择哪种还是要取决于这个电话簿的用法。如果 电话簿做好之后就不再添加新号码，那么选择后者更为合适；如果需要经常添加新号码，但不怎么需要再查询，就应该选择前者。

将获取顺序与拼音顺序结合起来怎么样

     我们还可以考虑一种新的排列方法，将二者的优点结合起来。那就是分别使用不同的表存储不同的拼音首字母，比如表 L、表 M、表 N 等，然后将同一张表中的数据按获取顺序进行排列。

     这样一来，在添加新数据时，直接将数据加入到相应表中的末尾就可以了，而查询数据时， 也只需要到其对应的表中去查找即可。 因为各个表中存储的数据依旧是没有规律的，所以查询时仍需从表头开始找起，但比查询整个电话簿来说还是要轻松多了

总结

     通过以上现实生活中的案例我们已经初步了解了数据结构在生活中运用，相信大家应该稍微明白了一些数据结构的作用。

     其实编程当中数据结构方面的思路也和制作电话簿时的一样。将数据存储于内存时，根据使用目的选择 合适的数据结构，可以提高内存的利用率。

计算机中最基本的数据结构

     就拿我自己说吧，其实我也不清楚其他语言内部或者第三方框架封装的一些数据结构，就java的话（我所学习的编程语言）Java它自己JDK所封装的就有部分数据结构，而且也都是常用到的像list（数组、链表）、map（哈希表）、Stack （栈）、Queue （队列）、Tree（树）等；

     大家都知道的就是在java中是没有指针的，所以像一些数据结构实现会让人没头没脑，但是其实了解jvm（Java虚拟机）的同学应该知道，java还是有指针的只不过不需要我们手动去管理。如果是计算机基础和java基础比较扎实的同学可能就知道——根本上的数据结构只有两种：数组和链表。

计算机中的数组结构

     首先在计算机里，计算机存储信息的最低单元应该是一个电极（比特bit），只能存储一个0或者1，而实际上在我们操作系统当中的最低存储单元是一个Byte（也就是8个电极一个字节，至于为什么是8个电极，这个可以后期专门写一下计算机原理），而这些都是足够微观的视角。现在我们进入内存的视角，我们想象一下，计算机的内存是一个大型的快递柜，每一格都只可以存储一个数字或者字母（也就是一个字节）。

     如上图我们可以看到，每一个格子里都有自己在计算机内存当中的内存坐标（实际上的内存地址比这个复杂的多），计算机是如何组织或者说开辟一个数组结构的呢？现在我们假设有三个快递分别是A、B、C,他们放在了内存当中的不同位置（如下图），我们需要去根据“取件码”（内存地址）拿出它们，我们需要打开三次快递柜的门，而且它们的位置七上八下的很是浪费时间。

     这个时候我们打电话给客服小姐姐抱怨：“你们下次派人配送快递的时候能不能把名字电话一样的放一排啊，我找着太费劲了，如果这样我就只需要知道第一个快递在哪就行了！”（当然这在现实生活中是不大可能实现的哈哈！！）。听了这个建议后，第二次小哥又配送了你的快递，而且是四个！！！（你真有钱）这次小哥把你的四个快递A、B、C、D全放在了一排（太感动了(/≧▽≦)/），而且在内部还打通了一个通道，可以从A连续拿到D去。然后你就开开心心的去拿快递了~

     以上就是你和快递柜的故事了，当然也引出了我们最熟悉的数据结构：数组；计算机组织数组结构的时候与这大差不差，只不过需要提前指定开辟数组的长度，如我需要长度为4的数组，计算机会直接帮我预约一块长度为4的连续内存，哪怕我没有存入值去使用它，计算机也不会让其他人去存储这块位置，除非我自己说不要了去释放了它。

     这里就必须提一嘴了，所有编程语言的建立都必须遵循当今计算机原理的，这是生态发展的必然，也是先有鸡后有蛋（别骂我！！！）的必然。所以任何编程语言当中的数据存储和读取是必须遵循计算机存储原理的，接下来我们继续讲链表结构，之后我们就可以去介绍一些比较炫酷的数据结构了。

计算机中的链表结构

     链表其实和数组同理，也是由多个“内存格子”组成，不过链表的表现方式并不像数组一样一路排开。要说元素的排布规律的话其实也是毫无规则可言。因此就肯定有一个问题，链表这种表达方式是如何去存储和获取数据的，又是怎样区分数据的归属的？

     如果要解答这些问题我们首先需要知道的就是链表是什么？

     为了简单理解，我们先讲一个范例，因为我们在上面已经比较粗略的介绍过数组了，我们可以通过一个范例凸显出链表的特点，同时也算是对数组的一个总体特点介绍。

     我们现在假设有十位同学，体育课老师叫他们按数组的方式进行依次排队，排好后，通常这个时候需要重新整队变成从低到高排，就会进行位置的调换或者去除，这时老师把第二位同学拉了出来，因为他是最高的，这时就会发现后面的八位同学都需要向前走一个身位为这次调换位置进行填补，最后再把这位同学调到最后去，显然我们发现了问题数组的特点：因为他们站在一条我们很容易就可以找到一个目标同学，我们只需要从头找到尾或者从尾找到头（我们这时要忽略一个距离概念，因为连续性的数组可以当作是一个整体一个部分），但是显然它有一个很大的弊端，就是当我们要对数组中的某一个元素进行修改调整去除时，就会发现为了迎合数组的特点每次数组的更改都需要极大的内耗，动一发而牵动全身，这样的效率是非常低的！

     那么我们的链表就出来了，当然我举一个这样的例子，大致你也能猜出链表有什么样的特点了。那正如你想的那样链表就是数组的一个纯反面教材（查询慢、插入删除快），那为什么他查询慢插入快呢？为方便理解，接下来我们用非常简单的链表来进行说明（它在内存中呈现出排成一排的架势）

     与数组相同的是在声明需要创建一个链表时，也会像数组一样在电脑内存中预约一片内存空间，但不同的是数组会直接告诉你我有多长，开始在哪里，结束在哪里，会把整体呈现在你眼前，而链表呢，它只表现这个内存中单一一个元素的状态并且它都不告诉你它处在什么位置。

     那这样不就问题来了：那我们怎样在链表中寻找一个自己想要的数据呢？（或者说目标数据）

     我们举一个如同链表名字一样的例子吧，我们假设现在同样有十个同学，但和之前不一样的是他们是手拉着手的，但是头尾的同学只会拉住一个同学（重点，之后会说到）。那么同学之间手拉着手我们可以看作是链子一样，同样他们也表达出了一个隐性信息，那就是他们每一个同学的前后一个同学到底是谁。假设现在是一个很混乱的操场，特别多的人，我只告诉了你排在第一个的同学在操场最中间，要你找到其他九位同学（当然我们现在知道同学是在一排的，但是我们要忽略这个因素，因为电脑只会一个一个去判断数据），现在你到了操场中间找到了第一个同学，这时你可以顺着第一个同学的手找到第二个同学，同时顺着第二个同学的手找到第三个同学，最终找到一个同学他的另一只手并没有牵人，就说明你已经找到了所有同学了。

     欸嘿！？上面就是一个典型的链表，然后我们就介绍了链表是怎样遍历数据的了，但有同学就疑问了，这不就是手拉手的数组嘛？和数组有什么区别？稍安勿躁 稍安勿躁，我们现在把链表变复杂一点，稍后你就明白了，因为为了方便理解过度，上面的例子我们把链表恰好是一排去解释，这样你们会容易介绍这样的概念，那我们现在对上面的例子进行一个变体：

     我们假设现在十位同学是分散的在不同地方，那么我们这个手牵手怎么解释呢？好了 高级的来了，注意听，我们抛开现象看本质，这个手拉手的行为到底表达的是什么意思？动动你的小脑袋瓜好好想想~

     没错它只是一个信息表达而已，它只是告诉了你它的下一个同学是谁而已，那我们现在把手拉手变体成，每一个同学都有两个纸条，它说明了它的下一个和上一个同学的位置，那现在告诉你第一个同学在操场中间，请你找到其他九名同学……（省略过程 相信你也能脑部过程了），以上就是一个排列并不规则的链表的解释

     那么请问？现在它还是数组嘛？你还能说链表和数组有一点像嘛？那链表和数组就不是一回事，那我们之前说的链表查询慢修改和删除快又是怎么回事呢，相信聪明的同学已经想到了，但我们还是讲一个例子，当然这个例子就很微观了，我们这次从电脑内部的角度来解释这个问题。

     我们首先要明白一个玩意，名叫指针的东西，它可以看作就是上面说的小纸条，它会指向一个内存空间，在链表中充当链子的作用。那我们试想一下，如果我们要在100个元素中寻找名字叫张三的同学，在数组中，我们最多只需要询问100次，而在链表中，数据的排布不一定是一排，100个元素每个都在不同的地方，位置不可预测只能通过他们手中的指针进行下一步定位，每次访问一个数据，都需要通过指针再去找到下一个数据的位置，而指针我们可以视为本身就是一个内存空间，那同样的100个元素，数组在内存中所需要的内存肯定是比链表要小的，并且遍历效率肯定是比链表不知道快多少的。

     但是，数组却不具备链表的一个很重要的特征，那就是变化适应性，假设我们需要把第二个数据移动到最后，我们上面讲过数组是牵一发而动全身，而在链表我们只需要把相应的指针数据进行修改，让他们指向的内存空间进行变化就行了，而这个过程是局部的细小的，所以链表的修改效率是明显快于数组的。

补充：在链表中，我们称只有一个指向的链表为单向链表（每个节点元素只有一个指针且指向它的下一个目标）另外还有双向链表，每个节点拥有两个指针，分别指向他们的前后元素，还有一种特殊的链表名叫环形链表，在双向链表的基础上，头尾部分的节点数据也是相连的，构成了一个闭环的数据结构。

链表和数组总结：

     由此我们已经简单介绍了数组和链表，我们可以看到他们都有各自的特点，相信现在你应该对数据结构有了一定的认识，我们通过不同场景使用不同的数据结构去解决问题，可以得到事半功倍的效益，所以数据结构在计算机编程中占据着非常重要的地位，并且从严谨角度来说它甚至是编程语言的根本计算机的根本，学好数据结构你才能更好的去认识计算机。

     而我们现在介绍完的数组和链表其实也是所有数据结构的根本，等你们真正理解数据结构的时候就会知道，真正的数据结构只有两种：数组和链表。所有其他复杂数据结构的实现都离不开它两，可谓是非常重要。

     那如果我现在问你数据结构是什么？相信你心里已经有了不少答案，它是构成数据心态的规则，是组织数据的方式，是一种约束更是一种反向的便利，生活中处处都有数据结构。

计算机中其他复杂的数据结构

（未完待续）

• 本文作者：慕小璃吖~
• 本文链接：https://mu-li.cn/2021/05/10/java/java-data-structure/
• 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。