静态与动态结构的权衡及垃圾收集

数据结构设计中一个关键的前置判断是：这个结构的大小和形状会不会随时间改变。静态结构（大小固定）管理起来简单得多，只需提供访问和修改指定位置数据的方式；动态结构（会增长或缩小）则必须处理”添加/删除项时去哪找空间、旧空间怎么回收”这类额外问题，设计不当时，插入一项可能引发大规模重排，甚至要把整个结构搬到一块更大的存储区域。随动态结构增减而产生的”不再使用的存储空间”需要被系统性回收以便复用，这个过程称为垃圾收集；如果回收机制不完善、总有空间该收回却没被收回，可用空间就会持续变少，这种现象称为内存泄漏。发散：一个数据结构在设计之初就该先问”它是静态的还是动态的”，这个问题的答案会连锁决定后续几乎所有实现细节——选择邻接存储还是链式存储、要不要引入垃圾收集机制，都是这个前置判断的自然推论，而不是可以事后修补的细枝末节。