欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

深入浅析ArrayList 和 LinkedList的执行效率比较

程序员文章站 2024-02-16 23:01:19
一、概念:     一般我们都知道arraylist* 由一个数组后推得到的 list。作为一个常规用途的对象容器使用,用于替换原先的 ve...

一、概念:

    一般我们都知道arraylist* 由一个数组后推得到的 list。作为一个常规用途的对象容器使用,用于替换原先的 vector。允许我们快速访问元素,但在从列表中部插入和删除元素时,速度却嫌稍慢。一般只应该用listiterator 对一个 arraylist 进行向前和向后遍历,不要用它删除和插入元素;与 linkedlist 相比,它的效率要低许多linkedlist 提供优化的顺序访问性能,同时可以高效率地在列表中部进行插入和删除操作。但在进行随机访问时,速度却相当慢,此时应换用 arraylist。

二、测试

    本来自己写了一些测试类想测试下arraylist和linkedlist的性能比较,发现怎么写都差强人意,今天在《thinking in java》中看到了这样的一段代码,个人觉得写得不赖。

public class listperformance
{
 private static final int reps = 100;
 private abstract static class tester//内部抽象类,作为list测试。
 {
  string name;
  int size;
  tester(string name, int size)
  {
   this.name = name;
   this.size = size;
  }
  abstract void test(list a);
 }
 private static tester[] tests = {new tester("get", 300)//一个测试数组,存储get(随机取)、iteration(顺序遍历)、insert(中间插入)、remove(随机删除)
 {
  void test(list a)
  {
   for (int i = 0; i < reps; i++) {
    for (int j = 0; j < a.size(); j++) {
     a.get(j);
    }
   }
  }
 }, new tester("iteration", 300)
 {
  void test(list a)
  {
   for (int i = 0; i < reps; i++) {
    iterator it = a.iterator();
    while (it.hasnext()) it.next();
   }
  }
 }, new tester("insert", 1000)
 {
  void test(list a)
  {
   int half = a.size() / 2;
   string s = "test";
   listiterator it = a.listiterator(half);
   for (int i = 0; i < size * 10; i++) {
    it.add(s);
   }
  }
 }, new tester("remove", 5000)
 {
  void test(list a)
  {
   listiterator it = a.listiterator(3);
   while (it.hasnext()) {
    it.next();
    it.remove();
   }
  }
 },
          };
 public static void test(list a)
 {
  system.out.println("testing " + a.getclass().getname());//输出测试的类名称
  for (int i = 0; i < tests.length; i++) {
   fill(a, tests[i].size);//填充空集合
   system.out.print(tests[i].name);
   long t1 = system.currenttimemillis();
   tests[i].test(a);//进行测试
   long t2 = system.currenttimemillis();
   system.out.print(":" + (t2 - t1)+" ms ");
  }
 }
 public static collection fill(collection c, int size)
 {
  for (int i = 0; i < size; i++) {
   c.add(integer.tostring(i));
  }
  return c;
 }
 public static void main(string[] args)
 {
  test(new arraylist());
  system.out.println();
  test(new linkedlist());
 }
}

深入浅析ArrayList 和 LinkedList的执行效率比较

三、总结

    首先,真的夸一下,这段代码写得真是好啊,无论是内部类的应用还是对面向对象的认识,都考虑的恰到好处,哎,我什么时候才能写出这么棒的代码啊。

    测试结果每次都有些许的差异,但不难得出以下的结论:

        1、在 arraylist 中进行随机访问(即 get())以及循环反复是最划得来的 。原因在于,arraylist是基于数组而来的,所以每个元素都有其对应的index,所以随机定位一个元素要快捷的多。

        2、在 linkedlist 中进行顺序访问、插入、删除动作的话还是比较高效的。原因在于,插入、删除的话对于linkedlist来说只需要改变其排列的一个node结点就可以了,而对于arraylist来说删除一个元素,需要不断把后面的元素移到前面的位置上。

        3、至于顺序访问,之前一直认为arraylist 基于数组排列,在内存中是连续排列的,应该会快得多,然后多次测试发现并不是想象的那样,或者说arraylist没有表现出它该有的优势,甚至还不如linkedlist的访问速度。原因在于:linkedlist 提供了优化的顺序访问性能。

总结

以上所述是小编给大家介绍的arraylist 和 linkedlist的执行效率比较,希望对大家有所帮助