1。让我们来谈谈它。本文主要和大家分享一下数组和链表的内存组织方式的异同，帮助大家正确理解这两种数据结构并合理应用。二、数组和链表简介1、数组数组---具有相同元素的有序、连续的存储结构。特点：元素类型相同；顺序存储；通过下标直接访问。2.链表链表---一种不一定有序、不一定连续、不一定相同元素的存储结构。特点：元素不一定相同，只需要链接信息；不需要记忆连续性；非下标访问，遍历链接信息。三、数组和链表的异同点1、相同点和相同点很少。两者都是内存数据的一种组织方式。数组利用相同元素连续分配的特性访问节点，而链表利用链接关系（索引访问一般通过指针链接）。（下面所有的数组项和链表项统称为节点）2.不同点和相同点比较少，否则必须用一个代替另一个，所以这里重点说说区别：1）通过前两者动态扩展特点我们知道，数组属于连续分配，一般在定义时分配给定的大小，而链表可以实现动态节点的插入和移除。这样，对于一些内存利用空间可变的情况，使用链表会带来更多的灵活性和内存利用率。如下图：如果之前分配的数组只有7个节点空间，当需要插入7个节点时，需要将内存全部复制到更大的内存空间，然后再插入7个。对于链表来说，有其实扩容是没有问题的。如果空间足够，指针可以被索引，就可以“无限”扩展。2）更好的使用Cache在有Cache的系统中，由于CPU的访问速度与普通内存的访问速度不在一个档次，为了不拖CPU，会使用Cache作为中间的缓冲区，这可以大大提高CPU访问。节省速度。那么数组作为一种连续的内存组织，更容易同时加载到Cache中，从而提高CPU对内存数据的命中率，提高运行速度和效率。3）访问节点的方法显而易见。数组可以通过下标直接访问对应的节点，而链表需要通过头指针不断遍历才能找到对应的节点。比如：我们想直接访问数组的第三个节点，直接传Array[2]就可以了，而对于链表来说，我们就是利用头指针不断寻找下一个节点，最后找到第三个节点的位置，所以链表的时候复杂度比数组大。4）节省内存对于数组，由于其固定的顺序存储格式，可以直接通过下标访问。但是，对于链表的不连续性，每个节点都必须存储其前导或后继链接信息，因此需要使用额外的内存空间来存储信息。当节点很多的时候，内存开销是不小的。4.一个讨论点的分析当被问到数组和链表的应用时，大家一般都会想到一句话：“数组是用来查询和修改的，链表是用来插入和删除的”。那么虫菌就在这里和大家分析一下这句话：1.案例1上面的数组中，在第四个元素之后插入了一个节点。这样，节点4、5、6需要依次向后移动一个节点，然后添加新的元素。要在上图中链表的四个位置插入一个新节点，首先需要通过遍历知道第四个节点，然后通过改变指针直接将新节点插入到链表中。案例一总结：在这种情况下，数组和链表的复杂度相差不大。数组需要移动新插入点之后的所有节点，再插入新节点。对于链表，需要先遍历找到对应的节点，然后再插入。2、情况2：在上图中的数组中数据1后面插入一个新节点。首先数组需要遍历知道数据1，然后移动数据节点3、5、6，插入新的节点。上图中的数组在数据1后面插入了一个新节点，首先链表需要遍历知道数据1，然后直接插入新节点。案例2总结：那么对于这种情况，链表的复杂度低于数组，所以具体情况具体分析，比如在头节点直接插入新节点的情况，链表列表优于数组。两者只是查找和修改没有太大区别，但是数组更方便。4.最后总结看完这篇文章，你应该对数组和链表有了更清晰的认识。其实这些对比对你以后优化设计一些代码很有帮助。请体验一下！
