顺序表和链表的对比

线性表有两种基本的物理存储实现方式：

• 顺序表：用一段连续的存储空间依次存储数据元素。
• 链表：用任意的存储空间存放元素，通过指针链接。

顺序表（Sequential List）

typedef struct {
    ElemType data[MaxSize];  // 静态分配
    int length;
} SqList;

链表（Linked List）

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

插入平均移动次数：在长度为 $n$ 的顺序表第 $i$ 个位置插入，平均移动

$$E = \frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1) = \frac{n}{2}$$

删除平均移动次数：

$$E = \frac{1}{n}\sum_{i=1}^{n}(n-i) = \frac{n-1}{2}$$

存储密度：单链表结点存 int（4B）+ 指针（4B），密度 $= 4/(4+4) = 0.5$。