-
C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。
-
而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。
-
链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用malloc分配内存空间，不需要时用free将已分配的空间释放，不会造成内存空间的浪费。
从逻辑结构来看
- 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
-
链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
从内存存储来看
-
(静态)数组从栈中分配空间, 对于程序员方便快速,但是*度小
-
链表从堆中分配空间, *度大但是申请管理比较麻烦.
- 数组中的数据在内存中的按顺序存储的，而链表是随机存储的！
- 要访问数组中的元素可以按下标索引来访问，速度比较快，如果对他进行插入操作的话，就得移动很多元素，所以对数组进行插入操作效率很低！
-
由于连表是随机存储的，链表在插入，删除操作上有很高的效率（相对数组），如果要访问链表中的某个元素的话，那就得从链表的头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问的效率就比数组要低 。
- 数组在内存中开辟连续的一块区域，如果一个数据要两个内存单元，一组5个数据10个单元就够了，无需标记其地址，因为数组定义时候确定了数组的首地址，其他四个都知道了（根据数据类型确定）。
- 链表可以是连续的，也可以是不连续的，但一般都是不连续的。
简要概括：
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
