Don‘t lost link!
list与vector不同之处在于元素的物理地址可以任意。
为保证对列表元素访问的可行性，逻辑上互为前驱和后继的元素之间，应维护某种索引关系。这种索引关系，可抽象地理解为被索引元素的位置（position），故列表元素是“循位置访问”（call-by-position）的；也可形象地理解为通往被索引元素的链接（link），故亦称作“循链接访问”（call-by-link）。这种访问方式，如同通过你的某位亲朋，找到他/她的亲朋、亲朋的亲朋、...。注意，向量中的秩同时对应于逻辑和物理次序，而位置仅对应于逻辑次序。
本章的讲解，将围绕列表结构的高效实现逐步展开，包括其ADT接口规范以及对应的算法。此外还将针对有序列表，系统地介绍排序等经典算法，并就其性能做一分析和对比。
引入list结构的目的，就在于弥补向量结构在解决某些应用问题时，在功能和性能方面的不足。二者之间的差异，表面上是体现于对外的操作方式，但根源在于其内部存储方式的不同。
数据结构支持的操作无非是静态和动态两种：静态仅从中获取信息，后者则会修改数据结构的局部甚至是整体。
静态举例：
size(); get(); //可在常数时间内完成
insert(); remove(); // 需要线性时间，原因在于各元素的物理地址连续
原文：https://www.cnblogs.com/ccpang/p/11420806.html