• 如果删除位置不合理，抛出异常；
    • 取出删除元素；
    • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
    • 表长减1。

    实现代码如下：

    1. /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    2. /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    3. Status ListDelete(SqList *L, int i, ElemType *e) {
    5.     int k;
    6.     /* 线性表为空 */
    7.     if (L->length == 0)
    8.         return ERROR;
    10.     /* 删除位置不正确 */
    11.     if (i < 1 || i > L->length)
    12.         return ERROR;
    14.     *e = L->data[i - 1];
    16.     /* 如果删除不是最后位置 */
    17.     if (i < L->length) {
    19.         /* 将删除位置后继元素前移 */
    20.         for (k = i; k < L->length; k++)
    21.             L->data[k - 1] = L->data[k];
    22.     }
    24.     L->length--;
    26.     return OK;
    27. }

    现在我们来分析一下，插入和删除的时间复杂度。

    先来看最好的情况，如果元素要插入到最后一个位置，或者删除最后一 个元素，此时时间复杂度为O(1)，因为不需要移动元素的。

    最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，此 时时间复杂度是多少呢？那就意味着要移动所有的元素向后或者向前， 所以这个时间复杂度为O(n)。

    至于平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要 移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为(n-1)/2。

    我们前面讨论过时间复杂度的推导，平均时间复杂度还是O(n)。

    这说明什么？线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。