线性关系 1.顺序表： 数据逻辑有连续性，物理存储上也具有连续性 （中间不能空，要紧紧相连这点和数组区别） 2.链表： 数据逻辑有连续性，物理存储上不一定具有连续性 3.顺序表： 创建/销毁 增删查改 增：头插/尾插/插入（给定下标） 删：头删/尾删/删除（给定下标） 查：indexOf(element); 改：set(int index,int value); 访问 get(int index); 访问第n个元素，时间复杂度要求O(1)，
头插：（size为数据个数，数组为array） a.需要从后往前遍历，否则数据将会被覆盖 b.数据下标遍历范围[size-1,0] (也就是插入之前的范围) c.空间下标遍历范围[size,1] (也就是遍历之后的范围) d.搬移的过程 array[空间]=array[数据] e.空间的下标=数据的下标+1 4.扩容 a.扩容的条件 在插入之前，size==array.length; b.如何扩容 1.申请新房子 （1.5倍-2倍） 2.把东西搬过去 3.公布自己的新房子 4.把旧的房子推掉 c.哪些方法需要考虑扩容 所有插入 5.时间复杂度 头插/头删/中间插入/中间删除 O(n) 尾插 平均O(1) (因为过一阵子就会需要扩容) 尾删 O(1) 6.属性的初始化 普通属性：（发生在构造每一个对象时） 1.定义时初始化 2.构造方法中初始化 3.构造代码块时初始化 静态属性：（发生在类加载时） 1.定义时初始化 2.静态代码块初始化 7.复杂度 衡量算法好坏的刻度尺/标杆 时间复杂度|空间复杂度 计算数据规模n和执行基本指令的个数F(n)的关系 时间复杂度： 第一反应：算法的运行时间 因为运行环境的不确定，所以，直接拿运行时间去衡量不合理。 考察算法的运行时间----考察算法运行需要的指令个数 算法运行的指令个数和因素（数据规模n）有关系 指令个数=F(n) 考察算法的复杂度，一般来说，只关注最坏的情况 大O渐进表示 1.保留最高次项 2.系数为1 空间复杂度： 算法执行过程中，占用的额外空间和数据规模n的关系的大O渐进表示法 开辟空间： 1.栈上的局部变量/形参 2.堆上的对象（数组，其他对象) 3.如果是递归方法，考虑调用栈的占用情况 常见的复杂度 O(1) O(log(n)) O(n) O(n*log(n)) O(n^2) （递归方法画调用栈去推算时间复杂度） 二分查找 （包含完全二叉树）O(log(n))
