643
《数据结构与抽象：Java语言描述（原书第4版）》一2.3 使用数组实现ADT包的优缺点
本节书摘来华章计算机《数据结构与抽象：Java语言描述（原书第4版）》一书中的第2章 ，第2.3节，［美］弗兰克M.卡拉诺（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 着 罗得岛大学 新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.3 使用数组实现ADT包的优缺点
本章讨论了使用数组存储项的ADT包的两种实现。数组易于使用，并且如果知道任何下标，就能对它立即进行访问。因为我们知道数组中最后项的下标，所以删除它是简单且快的。类似地，在数组末尾添加一项也同样简单和快速。另一方面，删除某项，如果它位于其他项的中间，则需要避免数组内的空隙。为此，用数组的最后一项来替换被删除的项。这只增加一点点的执行时间，因为时间都花在了寻找所需项上。本书后面将详细讨论这样的查找机制。
使用固定大小的数组，限制了包的容量，这常常是不利因素。调整数组大小能动态增大数组的大小，但需要复制数据。你应该知道，我们复制的数组项是引用，所以不会占据很大空间，也不会占用很多时间来移动。除了Java以外的有些语言，在数组中保存数据本身。这样的情形下，移动大量的复杂对象可能会相当耗时。
注：当使用数组来实现ADT包时，
- 向包中添加项是快的。
- 删除未指定的项是快的。
- 删除某个项需要找到这个项的时间。
- 增大数组的大小需要复制项的时间。
最后更新：2017-06-26 18:02:04