数组与链表的详细介绍

这篇文章主要讲解了“数组与链表的详细介绍”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“数组与链表的详细介绍”吧！

创新互联建站主打移动网站、做网站、成都网站制作、网站改版、网络推广、网站维护、国际域名空间、等互联网信息服务，为各行业提供服务。在技术实力的保障下，我们为客户承诺稳定，放心的服务，根据网站的内容与功能再决定采用什么样的设计。最后，要实现符合网站需求的内容、功能与设计，我们还会规划稳定安全的技术方案做保障。

数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表与非线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

比如二叉树、堆、图等叫非线性表，因为在非线性表中，数据之间并不是简单的前后关系。

连续的内存空间和相同类型的数据

优点：根据下标实现随机访问元素。
缺点：数组中插入、删除元素，可能需要迁移数据实现连续的内存空间，效率较低。

随机访问

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： a[i]_address = base_address + i * data_type_size
拓展：对于m*n的二维数组寻址公式： a[i][j]_address = base_address + ( i * n + j) * data_type_size

数组查找元素的时间复杂度为O(1)的表述是❌的，因为即使是通过二分查找排序好的数组时间复杂度也是O(logn)，正确的是数组支持随机访问，根据下标随机访问的时间复杂度为O(1);

低效的插入与删除

由于连续的内存空间特点，我们在插入或删除元素时需要将该元素之后的数据全部往后或者往前移动。即最好时间复杂度为O(1)，最坏时间复杂度为O(n)；由于每个位置操作元素的概率是一样的，所以平均时间复杂度为(1+2+…n)/n=O(n)。
如果存储的数据不是有序的，我们可以在插入时将原位置的元素插入到数组尾部，在删除时将数组尾部元素替换当前的位置的元素；这样插入或删除操作的时间复杂度为O(1)：

容器与数组

很多语言提供了基于数组的容器类 比如Java的ArrayList或者C++的vector；下面以ArrayList为例来看容器相比数组的优势：

容器可以将很多数组操作的细节封装起来，比如元素插入或者删除时其它元素的迁移工作，另外相比数组来讲，容器还可以动态扩容。

因为扩容操作涉及内存申请和数据搬移是比较耗时的，所以在创建容器时最好指定数据的大小，尽量避免扩容操作。

• 对于业务开发来讲，使用容器就足够了，省时省力；

• 对于网络框架、性能优化等底层开发，尽量使用数组。

链表

链表也是线性表结构，相比数组来讲不需要连续的内存空间，可通过“指针”将零散的内存块串联起来，对内存要求没数组那么高。

单链表

每个链表的结点除了储存数据外还需记录下一个结点的位置，即后继指针next。
在单链表中，第一个结点称为头结点，最后一个节点叫做尾结点；头结点记录链表的开始地址，尾结点后继指针指向空地址NULL。

高效的插入与删除

在上面数组低效的插入与删除中我们讲过，数组为了保证内存的连续需要搬移操作元素之后的元素，所以时间复杂度为O(n)，而在链表中我们只需考虑相邻节点的后继指针改变，所以对应的时间复杂度为O(1)。

低效的查询

因为链表中内存地址不是连续的，所以不能根据开始地址和下标计算对应元素的内存地址，需要根据后继指针一一遍历找到指定节点。

循环链表

循环链表跟单链表唯一的区别在于单链表尾结点后继指针指向空地址NULL，而循环链表尾结点后继指针指向头结点，像环一样首尾相连。

双向链表

单向链表每个结点只有一个后继指针next，而双向链表结点除了next还有一个前驱指针prev。

存储同样多的数据时，双向链表虽然比单链表占用更多内存空间，但是比单链表更为灵活支持双向遍历，使其在某些情况下插入删除操作比单链表更为简单、高效。
其实在讨论单链表时，我们说插入和删除的时间复杂度为O(1)，其实这个描述是不准确的，下面我们已删除操作为例：

通过结点的值比较删除

尽管删除操作的时间复杂度为O(1)，但是我们要根据值从头结点开始遍历比较找到要删除的结点，遍历查询对应的时间复杂度为O(n)；根据加法法则，此种删除的时间复杂度为O(n)。

通过结点删除

这种情况我们已经找到了要删除的结点，但是如果是单链表，我们还需要遍历单链表查询其前驱结点信息，所以时间复杂度仍然为O(n)；
但双向链表可以直接通过当前结点prev找到其前驱结点信息，所以时间复杂度为O(1)。

空间换时间

双链表的实现就是用空间换时间的设计思想；当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。
相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

双向循环链表

双向循环链表就是整合了双向链表和循环链表的新版本

链表与数组的对比

数组访问效率高；但是不支持动态扩容，需要整块内存空间。
链表天然支持动态扩容，插入删除操作更快；但是占用更多内存，频繁插入删除时容易造成内存碎片，可能导致频繁的GC。

感谢各位的阅读，以上就是“数组与链表的详细介绍”的内容了，经过本文的学习后，相信大家对数组与链表的详细介绍这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！