Question

数组和顺序链表的区别是什么

Answer 1

数组和顺序链表的区别
1、数组的内存需要提前确定，一旦确定不能更改其大小；而链表会动态分配内存；
2、数组的内存空间在内存中是连续的；而链表的内存空间则不是连续的；
3、数组的元素在栈区分配空间（即数组存储的元素都是为基本数据类型）；而链表在堆区分配空间（即链表中存储的元素为对象）
4、数组查询元素利用下标定位，时间复杂度为O（1）；而链表定位元素的时间复杂度则为O（n）；
5、数组插入或删除元素的时间复杂度为O（n）；而链表插入和删除的时间复杂度为O（1）；
数组
数组的存储方式是将元素在内存中连续存放，由于每个元素占用内存相同，所以可以通过下标迅速访问数组中的任何元素。但是如果要在数组中增加一个元素则需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想要删除一个元素，同样需要移动大量元素去填充掉被删除的元素。所以说数组查询元素速度较快，而增删元素速度较慢。
链表
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起的。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果需要访问链表中的一个元素，则需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表结构就非常简单了，只要修改元素中的指针就可以了。所以说链表查询元素速度较慢，而增删元素速度较快。