java中链表和数组的区别？

综述：数组是线性结构，可以直接索引，即要去第i个元素，a[i]即可。链表也是线性结构，要取第i个元素，只需⽤指针往后遍历i次就可。貌似链表⽐数组还要⿇烦些，⽽且效率低些。

想到这些相同处中的⼀些细微的不同处，于是他们的真正不同处渐渐显现了：链表的效率为何⽐数组低些？先从两者的初始化开始。数组⽆需初始化，因为数组的元素在内存的栈区，系统⾃动申请空间。⽽链表的结点元素在内存的堆区，每个元素须⼿动申请空间，如malloc。也就是说数组是静态分配内存，⽽链表是动态分配内存。链表如此⿇烦为何还要⽤链表呢？数组不能完全代替链表吗？为何那时候要⽤链表？因为管理系统中的插⼊，删除等操作都很灵活，⽽数组则⼤⼩固定，也⽆法灵活⾼效的插⼊，删除。因为堆操作灵活性更强。数组每次插⼊⼀个元素就需要移动已有元素，⽽链表元素在堆上，⽆需这么⿇烦。

说了这么多，数组和链表的区别整理如下：数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组元素在栈区，链表元素在堆区；

数组利⽤下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；数组插⼊或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。 1.数组的特点：

　　i 在内存中，数组是⼀块连续的区域。 例如看电影来说，⼏个去在电影院看电影必须坐在⼀起。

ii 数组需要预留空间，在使⽤前要先申请占内存的⼤⼩，可能会浪费内存空间。 ⽐如看电影时，为了保证10个⼈能坐在⼀起，必须提前订好10个连续的位置。这样的好处就是能保证10个⼈可以在⼀起。但是这样的缺点是，如果来的⼈不够10个，那么剩下的位置就浪费了。如果临时有多来了个⼈，那么10个就不够⽤了，这时可能需要将第11个位置上的⼈挪⾛，或者是他们11个⼈重新去找⼀个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。

iii 插⼊数据和删除数据效率低，插⼊数据时，这个位置后⾯的数据在内存中都要向后移。删除数据时，这个数据后⾯的数据都要往前移动。 ⽐如原来去了5个⼈，然后后来⼜去了⼀个⼈要坐在第三个位置上，那么第三个到第五个都要往后移动⼀个位⼦，将第三个位置留给新来的⼈。 当这个⼈⾛了的时候，因为他们要连在⼀起的，所以他后⾯⼏个⼈要往前移动⼀个位置，把这个空位补上。

iiii 随机读取效率很⾼。因为数组是连续的，知道每⼀个数据的内存地址，可以直接找到给地址的数据。并且不利于扩展，数组定义的空间不够时要重新定义数组。　2 .链表的特点

　　i 在内存中可以存在任何地⽅，不要求连续。 在电影院⼏个⼈可以随便坐。

ii 每⼀个数据都保存了下⼀个数据的内存地址，通过这个地址找到下⼀个数据。 第⼀个⼈知道第⼆个⼈的座位号，第⼆个⼈知道第三个⼈的座位号……

iii 增加数据和删除数据很容易。 再来个⼈可以随便坐，⽐如来了个⼈要做到第三个位置，那他只需要把⾃⼰的位置告诉第⼆个⼈，然后问第⼆个⼈拿到原来第三个⼈的位置就⾏了。其他⼈都不⽤动。

iiii 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第⼀个数据开始访问，然后根据第⼀个数据保存的下⼀个数据的地址找到第⼆个数据，以此类推。要找到第三个⼈，必须从第⼀个⼈开始问起。

iiiii 不指定⼤⼩，扩展⽅便。链表⼤⼩不⽤定义，数据随意增删。3.各⾃的优缺点：　　（1）数组的优点：　　　　i：随机访问性强　　　　ii：查询速度快　　（2）数组的缺点：　　　　i：增删速度慢　　　　ii：可能浪费内存

　　　　iii：内存空间要求⾼，必须有⾜够⼤的连续内存存储空间。　　　　iiii：数组的⼤⼩固定，不能动态扩展。　　（3）链表的优点　　　　i：插⼊删除速度快

　　　　ii：⼤⼩不固定，可以动态扩展。　　　　iii：内存利⽤率⾼，不会浪费内存　　（4）链表的缺点：

　　　　i：不能随机查找，必须从第⼀个开始遍历，查找效率低