线性表 linear list

把待插入的元素依次放到备用链表中，只需要把插入位置的前一个元素的游标改为插入元素的下标，然后把插入元素的游标改为前一个元素原来的游标即可。

线性表 linear list

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