链表和数组的区别是什么?

链表和数组的区别是什么?

1、内存不同
数组静态分配内存，链表动态分配内存。
2、连续情况不同
数组在内存中连续，链表不连续。

3、元素位置不同
数组元素在栈区，链表元素在堆区。

4、复杂度不同
数组利用下标**，时间复杂度为O(1)，链表**元素时间复杂度O(n);数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

数组和链表的区别

数组和链表是两种基本的数据结构，他们在内存存储上的表现不一样，所以也有各自的特点。 大致总结一下特点和区别，拿几个人一起去看**时坐座位为例。

在内存中，数组是一块连续的区域。

拿上面的看**来说，这几个人在**院必须坐在一起。 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。 比如看**时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。

但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。

插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。

当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。 随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。

并且不利于扩展，数组定义的空间不够时要重新定义数组。 在内存中可以存在任何地方，不要求连续。 在**院几个人可以随便坐。 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。

**个人知道第二个人的座位号，第二个人知道第三个人的座位号…… 增加数据和删除数据很容易。 再来个人可以随便坐，比**了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从**个数据开始访问，然后根据**个数据保存的下一个数据的地址找到第二个数据，以此类推。

要找到第三个人，必须从**个人开始问起。 不指定大小，扩展方便。链表大小不用定义，数据随意增删。 各自的优缺点 1、随机访问性强 2、查找速度快 1、插入和删除效率低 2、可能浪费内存 3、内存空间要求高，必须有足够的连续内存空间。

4、数组大小固定，不能动态拓展 1、插入删除速度快 2、内存利用率高，不会浪费内存 3、大小没有固定，拓展很灵活。

数组和链表的区别,各有何优缺点

链表与数组的区别
（1）数组的元素个数是固定的,而组成链表的结点个数可按需要增减;
（2）数组元素的存诸单元在数组定义时分配，链表结点的存储单元在程序执行时动态向系统申请;
（3）数组中的元素顺序关系由元素在数组中的位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。
（4）对于不是固定长度的列表,用可能**长度的数组来描述，会浪费许多内存空间。

（5）对于元素的插人、删除*作非常频繁的列表处理场合,用数组表示是不适宜的。

若用链表实现，会使程序结构清晰，处理的方法也较为简便。

数组的优点
随机访问性强
查找速度快
数组的缺点
插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展
链表的优点
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。

链表和数组有什么区别

二者都属于一种数据结构从逻辑结构来看1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数;当数据减少时，造成内存浪费;数组可以根据下标直接存龋2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。