78.链表和数组的区别在哪里？
分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，谁比较仔细，谁获
胜的机会就大。
/* 78.链表和数组的区别在哪里？ 分析：主要在基本概念上的理解。 但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，谁比较仔细，谁获 胜的机会就大。 1.数组静态分配内存，链表动态分配内存； 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况， 即在使用数组之前，就必须对数组的大小进行确定。当数据增加时，可能超出原先定义的元素个数； 当数据减少时，造成内存浪费。数组中插入、删除数据项时，需要移动其它数据项。 而链表采用动态分配内存的形式实现，可以适应数据动态地增减的情况， 需要时可以用new/malloc分配内存空间，不需要时用delete/free将已分配的空间释放， 不会造成内存空间浪费，且可以方便地插入、删除数据项。 2.数组在内存中连续，链表不连续； 数组中的数据在内存中是顺序存储的，而链表是随机存储的。 数组的随机访问效率很高，可以直接定位，但插入、删除操作的效率比较低。 链表在插入、删除操作上相对数组有很高的效率，而如果要访问链表中的某个元素的话， 那就得从表头逐个遍历，直到找到所需要的元素为止，所以，链表的随机访问效率比数组低。 3.数组元素在栈区，链表元素在堆区； 数组从栈中分配空间，对于程序员方便快速，但是自由度小。 链表从堆中分配空间，自由度大，但是申请管理比较麻烦。 4.数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)； 5.数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。 链表不存在越界问题，数组有越界问题。数组便于查询， 链表便于插入删除，数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。 如果需要快速访问数据，很少或不插入和删除元素，就应该用数组； 相反,如果需要经常插入和删除元素就需要用链表数据结构了 */