浅谈数组和链表

男娘i 2023-02-28 08:54 71阅读 0赞

**什么是数组？**  
  
相同**数据类型**的元素**按一定顺序连续排列**的[集合][Link 1]。内存结构是连续的，每个内存大小是相等的。

**内存结构图：**

![2020072021315169.png][]  
**数组的优点**  
  
索引速度快，因为数组有下标，获取到数组的引用可以快速根据下标获取到某一元素。数组的二分查找时间复杂度小，都是O(1)

**数组的缺点**  
  
从头部删除、从头部插入的效率低，时间复杂度是O(n),因为需要相应的向前搬移和向后搬移。数组的存储区间是连续的，占用内存比较大，内存空间要求高，必须要有足够的连续的内存空间。数组的空间大小是固定的，不能进行动态扩展。比如：当我们要新增一个元素的话，就需要重新在内存中申请一个比之前大一个内存结构的数组，然后将原来数组中的数组放到新的数组中，特别消耗性能。

**什么是链表？**

链表是一种物理存储单元上**非连续、非顺序的存储结构**，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。**每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。** 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。**链表的空间是从堆中分配的。（堆：先进先出，后进后出）**

**单项链表内存结构图：**  
  
![20200720214222933.png][]  
**链表的优点：**  
  
任意位置插入元素和删除元素的速度快，时间复杂度是O(1)，内存利用率高，不会浪费内存，链表的空间大小不固定，可以动态拓展。

**当新增一个数据元素：只需要申请一个数据内存，将新增的元素放入该内存中，将上有一个元素的指针指向新增的元素，而新增元素的指针指向下一个元素。**  
![20200720214404893.png][]

**链表的缺点：**  
  
查找数据时间效率低，时间复杂度是O(n)，因为链表的空间是分散的，所以不具有随机访问性，如果需要访问某个位置的数据，需要从第一个数（也就是头元素）开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度是O(n)。  
文章部分摘于：[https://blog.csdn.net/Jasminexjf/article/details/88847127][https_blog.csdn.net_Jasminexjf_article_details_88847127]

[Link 1]: http://baike.baidu.com/subview/15216/10703233.htm
[2020072021315169.png]: /images/20230209/ca5d5b05d06a4da599b5a8065dc3ee56.png
[20200720214222933.png]: /images/20230209/53fe560ee6734c30b2886fd8aa318b2a.png
[20200720214404893.png]: /images/20230209/4c951125115e4cf38d7ff26505364abf.png
[https_blog.csdn.net_Jasminexjf_article_details_88847127]: https://blog.csdn.net/Jasminexjf/article/details/88847127