个人编程学习网

大O表示法,表示时间复杂度,专门用于计算性能相关的,在这里我们简单分析下ArrayList的性能:

针对ArrayList存储数据的增删改查(CRUD);

1):保存操作:

如果把数据保存在数组的最后一个位置,至少需要操作一次.

如果把数据保存在数组的第一个位置,如果存在N个元素,此时需要操作N次(后面的元素要整体后移).

平均:  (N+1) /2 次.  N表示数组中元素的个数. 如果要扩容,更慢,性能更低.

2):删除操作:

如果删除最后一个元素,操作一次.

如果删除第一个元素,操作N次.

平均: (N+1)/2次.

3):修改操作:  操作1次.

4):查询操作:

如果根据索引查询元素:  操作1次.

如果根据元素查询索引: 此时使用线性搜索,操作:平均: (N+1)/2次:

---------------------------------------------------------------------------------

发现:基于数组的结构做查询是和修改是非常快的,但是做保存和删除操作比较慢了.

如何现在就想保证保存和删除操作的性能,怎么办?

数据结构:链表.