数据结构

一批数值放在哪里、怎样联系、根据什么规则访问，都会影响程序能做的操作。数组、链表、树和字典等结构提供不同组织方式，既可保存原始数据，也可保存长度、索引等辅助信息。额外信息增加存储，却可能避免后续每次操作都重新寻找同一个关系。

参考：[1]

抽象数据类型说明允许的操作，数据结构则给出落实这些操作的一种表示。队列可以用数组或链表实现，仍然维持先入先出的规则。使用者看到相同接口，并不表示两种实现插入、删除和扩容的成本一样；讨论选择时，需要把功能约定与具体表示分开。

参考：[2]

树的顺序、链表的连接及索引与内容之间的对应，都是操作需要维护的性质。若插入只改数据而忘了修改辅助计数，之后的查找或遍历可能得出错误结果。数据结构因此不仅是一张静态布局图，还包括保证每次修改以后布局仍然有效的操作规则。

参考：[1]

适合随机访问的结构，未必适合频繁在中间插入；适合内存的小结构，也可能不适合需要磁盘读取的大集合。分析还要考虑缓存、局部性和所需操作比例。不存在脱离工作负载的一种“最好数据结构”，应先明确程序怎样使用数据，再比较结构与算法的组合。

参考：[2]