1. 顺序存储
   1. 优点
      1. 分配连续的内存区域，无需为数据间的关系增加额外的存储空间
      2. 查找数据非常方便,只需返回链表的下表即可
         1. 时间复杂度为O(1)
   2. 缺点
      1. 增加/删除数据需要移动后面所有的数据
      2. 移动过程中容易产生存储空间碎片
      3. 难以确定存储空间的容量
   3. 因为插入和删除会移动后面n个元素，所以时间复杂度为O(n)
2. 链式存储
   1. 数据元素的内存不连续
   2. 单链表
      1. 一个节点包含数据域和指针域，指针指向下一个节点的地址
   3. 头指针
      1. 指向链表第一个元素的指针
      2. 是链表的必要要素，无论链表是否为空，头指针偶读存在
      3. 如果存在头结点，就指向头结点
      4. 如果头结点不存在，就指向第一个元素结点
   4. 空链表
   5. 头结点
      1. 在链表第一个元素之前，这样如果在第一个元素之前插入数据，就和在中间插入一样了
      2. 不是链表的必要要素
      3. 头结点的数据域通常不存数据，而是存储关于这个链表的一些元数据
   6. p指向第i个元素
      1. 数据
         1. p -> data
      2. 指针域
         1. p -> next
   7. 插入
      1. 1. s -> next = p -> next; 2. p - > next = s;
      2. 如果头结点存在，在链表的第一个元素前面执行插入操作于在中间插入一样
      3. 若在链表尾端插入
      4. 时间复杂度O(n)
         1. 时间主要用在了查找上，因为不像顺序存储那样能直接通过下表返回特定值，所以如果要找一个值，只有从头开始 如果找到了特定值，再执行插入，时间复杂度为O(1)
   8. 删除
      1. p -> next = q -> next;
      2. 时间复杂度O(n)
         1. 时间主要用在了查找上，因为不像顺序存储那样能直接通过下表返回特定值，所以如果要找一个值，只有从头开始 如果找到了特定值，再执行删除，时间复杂度为O(1)
   9. 空间可以无限分配
3. 总结
   1. 因为顺序存储查找的时间复杂度为O(1)，所以如果需要频繁地查找，就使用顺序存储
   2. 虽然顺序存储和链表在插入和删除上的时间复杂度一样，但链表的优势在于，一旦找到了需要插入的位置，就只需要O(1)的时间去改变指针的指向，无论需要连续插入多少个连续数据都一样。而顺序操作如果想在某个位置插入多个数据，就需要每次都移动后面的数据，每次都需要O(n)的时间。所以如果插入和删除操作频繁，就应该用链表
   3. 如果事先知道数据的多少，应该用顺序存储。否则用链表
   4. 线性表指的是元素之间具有线性关系（即前驱后继）的一个表
4. 循环链表
   1. 和单链表唯一的区别在于尾结点指向头结点
5. 双向链表
   1. 和单链表很像，只不过在每一个结点多了一个指针域指向其前驱结点
6. 双向循环链表
   1. 插入
      1. 1. s -> next = p -> next; 2. p -> next ->prior = s; 3.p ->next = s; 4. s -> prior = p;
   2. 删除
      1. 1. p -> prior -> next = p -> next; 2. p -> next -> prior = p -> prior;
7. 静态链表
   1. 用数组代替指针来模拟单链表
   2. 链表中每一个元素都有数据域和一个int型的域，用来存放下一个元素在数组中的位置
   3. 头结点和最后一个结点不存放数据
      1. 头结点的指针域存放备用链表第一个结点的下标
      2. 尾结点的指针域存放第一个插入元素的下标
   4. 插入
      1. 把待插入的元素依次放到备用链表中，只需要把插入位置的前一个元素的游标改为插入元素的下标，然后把插入元素的游标改为前一个元素原来的游标即可
   5. 删除
      1. 和插入类似，只需要改待删除位置上一个元素的游标，让他的游标设为待删除元素的游标即可
      2. 每释放一个结点，就得把它的位置空出来然后接入到备用链表的首段
   6. 优点
      1. 插入和删除时不需要移动元素
   7. 缺点
      1. 失去了顺序存储的优点
      2. 依然得提前分配很多空间，会有浪费