关于ArrayList和LinkedList的性能问题疑问

春风得意马蹄疾 发布于 2016/06/04 18:03
阅读 470
收藏 1

背景:一次面试中的题目:由连续数字组成的环,每次数7个数然后取出扔到,直到环上剩最后一个数

小弟用程序进行了实现,分别使用了ArrayList和LinkedList,linkedList是双向链表的实现,对于频繁删除应该性能高,但是我却得出相反的结果,请大神解惑


package cn.sun;

import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
import java.util.List;

public class CircleTest {

	public static void main(String[] args) {
		//ArrayList test
		Date bdate = new Date();
		System.out.println("list result:"+getLastNumByList(100000, 7));
		Date edate = new Date();
		System.out.println("list cost:"+(edate.getTime()-bdate.getTime())+" 毫秒");
		
		//LinkedList test
		bdate = new Date();
		System.out.println("linkedlist result:"+getLastNumByLinkedList(100000, 7));
		edate = new Date();
		System.out.println("linkedlist cost:"+(edate.getTime()-bdate.getTime())+" 毫秒");


	}
	
	public static int getLastNumByList(int totleNum,int stepNum){
		List<Integer> list = new ArrayList<Integer>();
		for(int i =0;i<totleNum;i++){
			list.add(i);
		}
		int nowNum =0;
		while(list.size()>1){
			for(int i=0;i<stepNum;i++){
				nowNum ++;
				if(nowNum > list.size()){
					nowNum = 1;
				}
			}
			list.remove(nowNum-1);
		}
		return list.get(0);
		
	}
	public static int getLastNumByLinkedList(int totleNum,int stepNum){
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		for(int i =0;i<totleNum;i++){
			linkedList.add(i);
		}
		int nowNum =0;
		while(linkedList.size()>1){
			for(int i=0;i<stepNum;i++){
				nowNum ++;
				if(nowNum > linkedList.size()){
					nowNum = 1;
				}
			}
			linkedList.remove(nowNum-1);
		}
		return linkedList.get(0);
		
	}
}



测试结果:


list result:52036
list cost:1197 毫秒
linkedlist result:52036
linkedlist cost:13397 毫秒

加载中
1
朱宏青
朱宏青

明确告诉你时间到底消耗在哪里:

1.删除前的查找动作

删除前是需要有一个查找动作来找到这个删除的元素 这个动作ArrayList必然是最快的 因为只需要查找下标即可 array[index] 这个操作太快了

但是LinkedList是需要遍历节点找到那个位置才行 遍历的方式很暴力 就判断一下坐标是从前面数快 还是从后面数快 然后就开始循环直到找到一个元素

例:total 1000  removeIndex 400 判断400是否小于(1000/2);是的就从头开始找;否则从尾巴开始找

因此很明显 如果一个坐标经常出现在队列中间 那么LinkedList需要花费大量的时间去做这个操作;反观ArrayList就没有这个烦恼 

2.删除后保持列表的维护性操作

ArrayList在删除节点后,需要对列表里的节点重新挪动位置,挪动的方式很简单,假设total 1000 removeIndex 400 那么就需要将400~999 (从0开始 删除400其实是删除399)这个范围的节点全部向前移动1 最后将末节点设置为null

看起来好像很麻烦其实你追进去 会发现这里最后调用了一个native的方法 数组拷贝 有黑科技在里面做优化

而LinkedList就很简单了 只要将删除节点的父节点的的子节点指向删除节点的子节点 然后将删除节点的子节点的父节点指向删除节点的父节点就好 这个操作是非常快的 基本不耗费多少时间


最后结论:如果ArrayList耗时多了 肯定是删除时 挪动节点费了太多时间;如果LinkedList耗时多了 肯定是删除时 查找删除节点耗费了太多时间

自行根据使用场景正确选择吧 :)


最后建议:其实可以最简单的测试一下,比如从0坐标开始删,看看谁快(个人结论:LinkedList快);从最后一个坐标开始删,看看谁快(个人结论:差不多快)

以上!

0
蔡晓建
蔡晓建
问题在于 linkedList.remove(nowNum-1);,双向链表删除一个数虽然不用移动,但是找到这个数比较麻烦,要从头遍历过去,这个过程可能非常慢。
春风得意马蹄疾
春风得意马蹄疾
但是ArrayList删除一个,后边的都向前复制移动,复杂度也不低啊,另外我看网上说linkedlist适用于删除比较频繁的时候,如果是随机删除性能岂不下降的特别厉害
0
LucEsape
LucEsape
你看是读取多 还是删除多?
LucEsape
LucEsape
回复 @春风得意马蹄疾 : 你删除一次的前提是要读7次啊。
春风得意马蹄疾
春风得意马蹄疾
LinkedList的随机删除效率很低啊
春风得意马蹄疾
春风得意马蹄疾
我的这个例子应该是删的多吧
0
g
gongzg_test
我查底层的实现代码,这个应该和他的底层实现应该有关,ArrayLisr和linkedList的add方法都是在末尾追加,,ArrayLisr的remove是移除此列表中指定位置上的元素。向左移动所有后续元素(将其索引减 1)。而linkedList的remove是移除此列表中指定位置处的元素。将任何后续元素向左移(从索引中减 1)。返回从列表中删除的元素。其次,linked存放分时候是有node的,这应该是影响他删除时的效率的原因吧,
g
gongzg_test
而且你也指定了要删除的索引,所以JVM就不用去找了,直接删,然后挪位置
返回顶部
顶部