线性表

顺序表

删除和插入操作，时间复杂度为 O(n)。 顺序表按位读取元素非常方便，其时间代价为 O(1)。

链表

顺序表至少存在以下两个方面的局限：

• 改变顺序表的大小需要重新创建一个新的顺序表并把原有的数据都复制过去。
• 因为逻辑关系是通过物理位置的相邻来表示的，增删元素平均需要移动一半的元素。

单链表 由于单链表没有指向前驱的指针，因此在第 i 个位置插入节点时，必须先获取位置 i-1 的指针，以便保持插入后链接正确。对于 n 个节点的线性表，插入点可以有 n+1 个；i=0 表示插入在表头，setPos(i-1)将返回头结点 head；i=n 表示在表尾插入。 head 与 tail 皆是虚拟结点。