-
1 先比较下Arraylist和Linkedlist的存取数据的速度
@Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_content_detail); ButterKnife.bind(this); System.out.println("ArrayList添加" + N + "条耗时：" + addElements(new ArrayList())); System.out.println("LinkedList添加" + N + "条耗时：" + addElements(new LinkedList())); List list1 = addList(new ArrayList<>()); List list2 = addList(new LinkedList<>()); System.out.println("ArrayList查找" + N + "条耗时：" + readList(list1)); System.out.println("LinkedList查找" + N + "条耗时：" + readList(list2)); }private long addElements(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(0, "" + i);
}
return System.currentTimeMillis() - start;
}private long readList(List list) {
long start = System.currentTimeMillis();
for (int i = 0, j = list.size(); i < j; i++) {
list.get(i);
}
return System.currentTimeMillis() - start;
}private List addList(List list) {
for (int i = 0; i < N; i++) {
list.add(0, "" + i);
}
return list;
}
输出结果：
03-28 15:09:30.321 14873-14873/com.amazingokc.zhihucolumn I/System.out: ArrayList添加50000条耗时：2249
03-28 15:09:30.551 14873-14873/com.amazingokc.zhihucolumn I/System.out: LinkedList添加50000条耗时：233
03-28 15:09:32.911 14873-14873/com.amazingokc.zhihucolumn I/System.out: ArrayList查找50000条耗时：5
03-28 15:09:45.451 14873-14873/com.amazingokc.zhihucolumn I/System.out: LinkedList查找50000条耗时：12540
可以看到各有优缺点
其实从Linkedlist的源码可以知道，对于统一个链表而言，从指定位置添加数据与获取数据消耗时间是几乎相同的，将上面代码稍微改改
private long addElements(List list) {
for (int i = 0; i < 40000; i++) {
list.add(0, "" + i);
}
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(20000, "" + i);
}
return System.currentTimeMillis() - start;
}
private long readList(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.get(20000);
}
return System.currentTimeMillis() - start;
}
输出：
03-28 16:24:37.178 23163-23714/com.amazingokc.zhihucolumn I/System.out: ArrayList添加10000条耗时：410
03-28 16:24:41.658 23163-23714/com.amazingokc.zhihucolumn I/System.out: LinkedList添加10000条耗时：4321
03-28 16:24:43.928 23163-23714/com.amazingokc.zhihucolumn I/System.out: ArrayList查找10000条耗时：1
03-28 16:24:48.228 23163-23714/com.amazingokc.zhihucolumn I/System.out: LinkedList查找10000条耗时：4298
之前耗时相差之所以这么大，是因为开始的时候链表是慢慢变长的，读取的时候链表一直是最大值，所以遍历链表的时候总的时间就不一样了。
-
1 Arraylist的add(int index, E object)方法
Arraylist的add(int index, E object)方法之所以耗时比较大，是由数组的结构所决定的，数组是连续存储的，在操作数组中的数据时就可以根据首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间。与之相反，链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。看下源码实现：
/**
*Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
*
* @param index
* the index at which to insert the object.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
一般情况下应该进入到else里面，第一个arraycopy会将原来的数组a从0开始的位置复制index个元素放到新建数组newArray的0位置排放，第二个arraycopy会将原来的数组a的其他元素放到新建数组newArray的index + 1位置排放，此时newArray的index位置是没有放元素的，这个位置就是我们需要添加元素的位置，a[index] = object;完成了添加操作。所以每次添加一个元素的时候，都会对原来数组的元素进行复制工作，add(E object)方法是在尾部添加元素，只需要将全部元素放在新数组的前面，然后在新数字尾部添加一个元素即可，速度应该会相对快一些。删除remove(int index)的源码原理基本相似，这就是Arraylist的增删操作比较耗时的原因。
