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