Code Bye

关于LinkedList与ArrayList的remove效率的问题

码拜 
public class LinkList_ArrayList {
	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		getRemoveTime(500000,490000,250000);//当element越靠后remove OBJ  ArrayList效率比LinkedList越明显，小的时候相差无极
	}
	public static void getRemoveTime(int count,int element,int index){
		ArrayList<String> arr = new ArrayList<String>();//默认长度为10
		LinkedList<String> linl = new LinkedList<String>();
		ArrayList<String> con = new ArrayList<String>();
		for(int i=1;i<=count;i++){
			arr.add(i+"");//当数组空间已满，增加原有长度的1/2

		}
		for(int i=1;i<=count;i++){
			linl.add(i+"");

		}
		for(int i=1;i<=10;i++){
			int p = 200000;
			con.add((p+i)+"");//当数组空间已满，增加原有长度的1/2
		}

		Long start_remove = new Date().getTime();
		arr.remove(index);
		Long end_remove = new Date().getTime();
		System.out.println("ArrayList方法remove 在"+count+"条数据中，第"+index+"个位置需删除元素要耗时"+(end_remove-start_remove));
		Long startlinl_remove = new Date().getTime();
		linl.remove(index);
		Long endlinl_remove = new Date().getTime();
		System.out.println("LinkedList方法remove 在"+count+"条数据中，第"+index+"个位置需删除元素要耗时"+(endlinl_remove-startlinl_remove));
		Long start_remove_OBJ = new Date().getTime();
		arr.remove(element+"");
		Long end_remove_OBJ = new Date().getTime();
		System.out.println("ArrayList方法remove  OBJ 在"+count+"条数据中，删除"+element+"元素要耗时"+(end_remove_OBJ-start_remove_OBJ));
		Long startlinl_remove_OBJ = new Date().getTime();
		linl.remove(element+"");
		Long endlinl_remove_OBJ = new Date().getTime();
		System.out.println("LinkedList方法remove OBJ 在"+count+"条数据中，删除"+element+"元素要耗时"+(endlinl_remove_OBJ-startlinl_remove_OBJ));
		Long start_removeAll = new Date().getTime();
		arr.removeAll(con);
		Long end_removeAll = new Date().getTime();
		System.out.println("ArrayList方法removeAll 在"+count+"条数据中，删除容器元素要耗时"+(end_removeAll-start_removeAll));
		Long startlinl_removeAll = new Date().getTime();
		linl.removeAll(con);
		Long endlinl_removeAll = new Date().getTime();
		System.out.println("LinkedList方法removeAll 在"+count+"条数据中，删除容器元素要耗时"+(endlinl_removeAll-startlinl_removeAll));

	}
	public static void getIndexOfTime(int count,int count_con,int index){
		ArrayList<String> arr = new ArrayList<String>();//默认长度为10
		LinkedList<String> linl = new LinkedList<String>();
		ArrayList<String> con = new ArrayList<String>();
		for(int i=1;i<=count;i++){
			arr.add(i+"");//当数组空间已满，增加原有长度的1/2

		}
		for(int i=1;i<=count;i++){
			linl.add(i+"");//当数组空间已满，增加原有长度的1/2

		}
		for(int i=1;i<=count_con;i++){
			int p = 400000;
			con.add((p+i)+"");//当数组空间已满，增加原有长度的1/2
		}
		Long start_indexof = new Date().getTime();
		arr.indexOf(index+"");
		Long end_indexof = new Date().getTime();
		System.out.println("ArrayList方法indexOf 在"+count+"条数据中，第"+index+"个位置需要耗时"+(end_indexof-start_indexof));
		Long startlinl_indexof = new Date().getTime();
		linl.indexOf(index+"");
		Long endlinl_indexof = new Date().getTime();
		System.out.println("LinkedList方法indexOf 在"+count+"条数据中，第"+index+"个位置需要耗时"+(endlinl_indexof-startlinl_indexof));
		Long start_contains = new Date().getTime();
		arr.contains(index+"");
		Long end_contains = new Date().getTime();
		System.out.println("ArrayList方法contains 在"+count+"条数据中，第"+index+"个位置需要耗时"+(end_contains-start_contains));
		Long startlinl_contains = new Date().getTime();
		linl.contains(index+"");
		Long endlinl_contains = new Date().getTime();
		System.out.println("LinkedList方法contains 在"+count+"条数据中，第"+index+"个位置需要耗时"+(endlinl_contains-startlinl_contains));
		Long start_containsAll = new Date().getTime();
		arr.containsAll(con);
		Long end_containsAll = new Date().getTime();
		System.out.println("ArrayList方法containsAll 在"+count+"条数据中，第"+index+"个位置需要耗时"+(end_containsAll-start_containsAll));
		Long startlinl_containsAll = new Date().getTime();
		linl.containsAll(con);
		Long endlinl_containsAll = new Date().getTime();
		System.out.println("LinkedList方法containsAll 在"+count+"条数据中，第"+index+"个位置需要耗时"+(endlinl_containsAll-startlinl_containsAll));

	}
}

运行结果
ArrayList方法remove 在500000条数据中，第250000个位置需删除元素要耗时0
LinkedList方法remove 在500000条数据中，第250000个位置需删除元素要耗时6
ArrayList方法remove  OBJ 在500000条数据中，删除490000元素要耗时4
LinkedList方法remove OBJ 在500000条数据中，删除490000元素要耗时7
ArrayList方法removeAll 在500000条数据中，删除容器元素要耗时52
LinkedList方法removeAll 在500000条数据中，删除容器元素要耗时47
为什么调用在remove(int index)与remove(Objec obj)方法时，ArrayList效率要高于LinkedList？
查看源码的时候，removeAll方法调用的都是同一个父类方法，在这个父类方法中的iterator所产生next与remove方法最终都是调用本类的get(Int index)与remove(Int index),这种情况下显然ArrayList的效率应该更高才对，为什么测试结果却是LinkedList的效率高呢？
希望知道原因的大拿给解释一下！

解决方案

20

哪个性能更好，这些集合已经有成熟的比较了，建议你先去搜一搜看看
参考

20

引用:
Quote: 引用:

先问一句，题主你上面那个答案就执行一次么？假如你多执行几次你会发现结果可能不太一样啊！这说明你的举例数据类型过于简单，这点数据对于你的电脑来说，秒秒钟搞定，分不出来好坏。不信你看看本人电脑的运行结果：

那么我们经常说LinkedList在删除插入的时候比ArrayList快，这个从源码应该很好理解吧。

public E remove(int index) {
	RangeCheck(index);
	modCount++;
	E oldValue = (E) elementData[index];
	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work
	return oldValue;
    }

ArrayList之所以耗时，就是这里有个System.arraycopy(),而LinkedList只是修改前后节点的对应关系，

private E remove(Entry<E> e) {
	if (e == header)
	    throw new NoSuchElementException();
        E result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
	size--;
	modCount++;
        return result;
    }

从上述源码看，LinkedList删除操作确实要高于ArrayList，但是LinkedList并没有直接调用这个方法，在调用之前还有一个遍历操作。
本人将参数改变为getRemoveTime(3000000,1,1000)后得到一下运行结果：
ArrayList方法remove 在3000000条数据中，第1000个位置需删除元素要耗时2
LinkedList方法remove 在3000000条数据中，第1000个位置需删除元素要耗时1
ArrayList方法remove  OBJ 在3000000条数据中，删除1元素要耗时2
LinkedList方法remove OBJ 在3000000条数据中，删除1元素要耗时0
ArrayList方法removeAll 在3000000条数据中，删除容器元素要耗时119
LinkedList方法removeAll 在3000000条数据中，删除容器元素要耗时136
这次符合正常的理解，LinkedList效率高于ArrayList。貌似遍历的时间复杂度对性能的影响要远大于操作本身的所耗费的时间？

LinkedList也不是全部遍历啊，是先跟size >>1 也就是size 二分之一比较，然后再遍历到这个inde的数据。Arraylist删改的时候就是原因是那个copy函数，当数据量大的时候，你觉得是复制对象更耗时间还是遍历更耗时间？

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明关于LinkedList与ArrayList的remove效率的问题！