线性表&顺序表思维导图

O（1）时间找到第i个元素

使用静态数组实现，无法改变大小

L.data = (ElemType*) malloc(sizeof(ElemType) * size);

存满时用malloc动态拓展，将数据元素复制到新的存储区域并用free释放原区域

n/2

有n+1个位置可插入，第一个位置插入移动n个，第二个位置插入移动n-1个……累加/(n + 1)

(n - 1)/2

有n个位置可删除，删除第一个移动后面n-1个，删除第二个移动后面n-2个……累加/n

最好O(1)，此时插入表尾，不需要移动元素

最坏O(N)，此时插入表头，原有n个元素全部后移

平均O(N)

将L的第i个元素删除，并用e返回

最好O(1)，此时删除表尾，不需要移动元素

最坏O(N)，此时删除表头，后续n-1个元素全部前移

平均O(N)

获取表中第i个位置的元素的值

L.data[i - 1]：时间复杂度O(1)

在顺序表L中查找第一个元素值等于e的元素，并返回其位序

时间复杂度：最好O(1),最坏O(N),平均O(N)

第一个元素称为首元

最后一个元素称为尾元

除了第一个元素外，其余每个元素只有一个直接前驱；除了最后一个元素外，其余每个元素只有一个直接后继