数组与链表解析-CSDN博客

本文链接：https://blog.csdn.net/java_green_hand0909/article/details/79387797

链表与数组是最基础的数据的结构，堆栈.队列等逻辑上的数据结构都是基于这两种数据结构实现的。

链表与数组的区别在于数组的内存分配是连续的（即数组的每一项内存地址是连续的），而链表则可能连续也可能不连续。

从性能上看，数组支持随机存储，查询速度相对于链表更快，但每一次插入或删除都要将操作数组项后面的元素逐一向前移动一位，效率为O（n）。而链表的查询每次都要从表头开始逐一查询，查询效率为O（n）,查询速度相对数组更慢，但其插入删除速度由于只需要改变节点指针,所以操作速度更快。

首先从逻辑结构上说，两者都是数据结构的一种。

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了

　(1) 从逻辑结构角度来看
　　   a, 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
　　 b,链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
　　(2)从内存存储角度来看
　　   a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
　　   b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

综合以上，对于快速访问数据，不经常有添加删除操作的时候选择数组实现，而对于经常添加删除数据，对于访问没有很高要求的时候选择链表。

1 、链式存储概念

(1)顺序存储：

我们所学的数组是一种连续的顺序存储方式，知道了数组某一个元素的地址，由于连续，则可以通过地址的计算能够算出每一个元素的地址。

(2)链式存储:

该方式是每个单元的存储位置是不连续的，随机的，但是可以通过在前一个存储单元中记录下一个存储单元的地址来把所有的存储单元联系起来，就像生活中的链条一样一环套一环,每个存储单元我们叫做节点。

每个节点可以分为两部分，数据域和地址域，数据域用来存储相关数据，地址域用来存储下一个节点的地址

如下图：

节点1 地址为 0x90, 存储数据1；

节点2 地址为 0x20，存储数据2；

节点3 地址为 0x40，存储数据3；

节点4 地址为 0x70，存储数据4；

通过节点1可以找到节点2的地址，找到节点2的地址就能找到节点3的地址，从而找到节点4的地址，这样逻辑上的链表就建成了。

1 数组

数组是最最基本的数据结构，很多语言都内置支持数组。数组是使用一块连续的内存空间保存数据，保存的数据的个数在分配内存的时候就是确定的：

图 1.1 包含 n 个数据的数组

访问数组中第 n 个数据的时间花费是 O(1) 但是要在数组中查找一个指定的数据则是 O(N)。当向数组中插入或者删除数据的时候，最好的情况是在数组的末尾进行操作，时间复杂度是O(1) ，但是最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。