数组和链表

数组的优劣

摘自维基百科：

数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有>以下特性：

• 请求空间以后大小固定，不能再改变（数据溢出问题）；
• 在内存中有空间连续性的表现，中间不会存在其他程序需要调用的数据，为此数组的专用内存空>间；

因为数组连续，可以根据初始地址+偏移量（下标）直接得到指定位置的值
但是在存储的时候，如果要存储在指定位置，代价就是指定位置及之后的数据全都向后迁移
时间复杂度：存O(n) 取O(1)

链表的优劣

链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）

链表是一种线性表，与数组不同的是，他的前后关系是由自己维护一个指针。
因此，线性表具有存方便（直接修改前后节点的指针），取不方便（只能从头扫到尾）的特性
时间复杂度：存O(1) 取O(n)