$PS：$邓书里的向量实际上就是顺序表、而列表则相当于链表。接下来以殷书为主，王道和邓书作为补充。一些太简单的就懒得记录了。
顺序表
顺序表
顺序表逻辑结构为线性，存储结构为顺序存储；性能分析如下：
$$
\begin{cases}
\frac{n+1}{2}& \text{查找}\\
\frac{n-1}{2}& \text{删除}\\
\frac{n}{2}& \text{插入}\\
\end{cases}
$$
链表
单链表
附加头节点的目的是：方便运算的实现；
单链表具有头节点和尾指针时，删除最后一个元素的复杂度是$O(n)$，因为需要尾指针的前驱；
双向链表为空则其前后驱均为自己。
$$
\begin{cases}
O(n)& \text{访问}\\
O(n)& \text{查找}\\
O(1)& \text{插入}\\
O(1)& \text{删除}\\
\end{cases}
$$
殷书习题精选
顺序表
链表
