(一). 基于数组的列表实现ArrayList
这些天一直纠结于散列表的总结, 感觉自己对散列表的理解还可以, 源代码也深究了一些, 但是一到要写的时候就找不到好的思路, 只好从基本的开始写, 希望能为后续的散列表总结找到一些思路...
ArrayList是基于数组实现的, 它在一个连续的储存块中储存元素, 不过与数组不同的是: ArrayList可以进行动态的增长, 通俗一点说就是: 当数组不足以容纳更多的元素时, 我们就再建立一个新的,更长的数组, 将原数组的元素拷贝到新数组里, 再对这个新数组进行操作.?
?
首先分析一下它的基本功能:
1.添加操作:将指定索引位置后所有元素向后移动, 再将要插入的数据插入到空出来的指定索引位置.
?
2.删除操作:
删除操作和插入操作有点类似, 是将指定索引后的元素都向前移动, 想当于插入操作的逆过程.
3.查找操作:
1)给定索引, 可直接查找指定索引出的元素
2)给定值, 则需要遍历
4.修改操作: ?
给定索引直接替换原值
下面看一下具体的代码实现:
?
下面请看测试:
?
?
?
?
结果为:
自实现列表的需要所需要的时间为 : 486
系统列表所需要的时间为 : 453
?
?
?
结果为:
自实现列表的需要所需要的时间为 : 967
系统列表所需要的时间为 : 811
?
?
?
? 结果为:
自实现列表的需要所需要的时间为 : 998
系统列表所需要的时间为 : 842
总结:?
1. ArrayList可以高效的随机访问元素
2.?在ArrayList中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;
3.?ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间
也就是说: ?当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能; 但是如果需要频繁的进行插入删除等操作, ArrayList的缺点就会很明显了, 这时可以选择LinkedList, 有关LinkedList的实现, 将在下一篇博客中分析.
