概念

线性表属于（一对一）的逻辑结构，它分别拥有顺序存储结构和链式存储结构

顺序存储 是将数据元素按顺序放在一起，相邻元素通过内存地址相邻产生联系
链式存储 中包含两部分（数据域：实际数据）+（指针域：后继节点地址），每个元素除了存放数据，也保存了其相邻元素的内存地址来实现线性关系

顺序存储结构别称（数组），通过元素相邻的方式实现1对1
链式存储结构别称（链表），通过保存指针域的方式实现1对1


线性表的基本操作（增，删，改）

顺序表新增/删除元素😀

给定长度为 n 的顺序表，在指定位置 i 插入一个新元素，插入完成后,新元素位于位置 i
给定长度为 n 的顺序表，删除位置 i 的元素。
方式：
• 需要将位置 i 到位置 n-1 的所有元素都向后或向前挪一格
• 在最坏情况(i=0)下，需要挪动全部的 n 个元素 => 时间复杂度为O(n)
• 无需利用额外空间的话，它的空间复杂度为O(1)

顺序表更新元素😀

给定长度为 n 的顺序表，更新位置 i 的元素

无论 i 的值如何，都可以通过 i 直接访问位置 i 元素，将其更新为 v’=> 时间复杂度
为O(1) => 随机存取

(单)链表新增元素😀

给定长度为 n 的单链表，在第 i 个结点插入一个新元素，插入完成后新元素是链表的第 i 个结点
1.首先需要从头结点开始逐个向后找 i-1 次 => 这一步的时间复杂度为O(n)
2.找到后插入只需要修改第 i-1 个结点的[后继结点地址1] 和 待插入结点的 [后继结点地址2] 即可 =>这一步的时间复杂度为 O(1)
无需利用额外空间 => 空间复杂度为O(1)
注意：两步顺序不能反。

(单)链表删除元素😀

给定长度为 n 的单链表，删除第 i 个结点

1.需要移动到第 i 个结点的前驱结点，最坏情况下移动n-1次 => 时间复杂度为 O(n)
2.修改前驱结点的后继指针 => O(1)
无需利用额外空间 => 空间复杂度为O(1)

(单)链表更新元素😀

给定长度为 n 的单链表，更新第 i 个结点的值
需要从头结点开始 一个个地 找到第 i 个结点才能访问并更新它 => 顺序存取
最坏情况遍历整个链表 => 时间复杂度为 O(n)
练习：
设顺序表中有n个元素，往其插入或从其删除一个元素，平均要移动的元素个数为     

答：n/2  解析N个元素的顺序表可插入的位置有N+1个，
移动次数总数为0+1+2…+n=(0+n)*(n+1)/2
平均次数为 总数/(N+1）= n/2

线性表的合并操作

集合表合并：只合并不同元素



对于B表中的每个元素，都需要先判断其是否已经存在A里 => O(m n)
• 如果存在，无需插入，如果不存在，将其插入在A的末尾 => O(1)
• 总时间复杂度为 O(m n)

空间复杂度
• 顺序表：O(m+n)
• 链表：O(1)


有序表合并：本来分别有序，合并结果仍然有序



两个有序的顺序表的合并

设A表长度为n, B表长度为m
• 先预留结果表空间：n+m个元素
• 从表头开始同时逐个访问A表和B表元素，将当前位置上较小者放入结果表并后移一位
• 总时间复杂度为 O(m+n)
• 空间复杂度为 O(m+n)

两个有序的单链表的合并

设A表长度为n, B表长度为m
• 先创建一个头结点(哑结点dummy)，其数据没有实际意义，只为用它的[指针域]
• 从表头开始逐个同时遍历A和B，将当前已完成合并的表尾元素的后继节点设置为当前A和B游
标中较小的一个，并将该游标向后移动一位
• 时间复杂度为 O(m+n)
• 空间复杂度为 O(1)