神代綺凛の随波逐流

[Java] ArrayList 与 LinkedList

当前页面是本站的「Baidu MIP」版。查看和发表评论请点击：完整版 »

ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构。在一次实验中偶然发现并实验了这两者的不同之处，很有意思

Head Pic: 「オリジナル」/「100％」[pixiv]

ArrayList 与 LinkedList

在写编程实验的时候因为用到了它俩，就突然想测试一下他们的效率，特别是在添加组员这方面

使用学生类作为测试对象

一开始的代码

public class StudentList {
    private ArrayList<Student> list;
    //private LinkedList<Student> list;

    public StudentList() {
        list = new ArrayList<Student>();
        //list = new LinkedList<Student>();
    }

    //添加学生
    public void add(int _id,String _name,int _age,boolean _sex,int _score,int _grade) {
        list.add(new Student(_id, _name, _age, _sex, _score, _grade));
    }
}
public class WithStruct {
    private static StudentList sl = new StudentList();

    public static void main(String[] args) {
        test();
    }

    private static void test() {
        //固定随机数种子，生成固定数据方便比较
        Random rd = new Random(1234567890);
        //初始化数据，随机生成学生信息并加入 List
        Timer tm = new Timer(); //Timer 是自己写的一个很简单的计时器类
        for(int i=0;i<1000000;i++) {
            sl.add(2010000000+(int)(rd.nextDouble()*1000000),
                    "s."+i, 18+(int)(rd.nextDouble()*4),
                    rd.nextDouble()>0.5?true:false,
                    100+(int)(rd.nextDouble()*300),
                    1+(int)(rd.nextDouble()*3)
            );
        }
        tm.stop();
        System.out.println("Initialization: "+tm.getTimeMillis()+"ms");
        //添加1000000名学生
        tm.start();
        for(int i=1000000;i<2000000;i++) {
            sl.add(2010000000+(int)(rd.nextDouble()*1000000),
                    "sd."+i, 18+(int)(rd.nextDouble()*4),
                    rd.nextDouble()>0.5?true:false,
                    100+(int)(rd.nextDouble()*300),
                    1+(int)(rd.nextDouble()*3)
            );
        }
        tm.stop();
        System.out.println("Add 10000 students: "+tm.getTimeMillis()+"ms");
    }
}

主要目的就是想测试一下加入成员的时候哪个效率更高，结果如下：

ArrayList:
Initialization: 166ms
Add 1000000 students: 127ms

LinkedList:
Initialization: 1358ms
Add 1000000 students: 1302ms

一开始看到这个我稍微有点意外，感觉和我想的不太一样……

因为我觉得链表添加成员，如果是动态数组的话，你需要new一个更大的数组，把原来的数据拷贝过去，然后在末尾将新成员的值拷贝过去；而链表，只需要在末尾加上一个新链就可以了

（懒得翻他们的源代码，想了想）觉得是因为分配内存空间和拷贝操作的速度是真的远远大于新建链表节点的操作，而且因为链表需要指针，也许指针相关操作也要消耗不少时间，大概只能这样解释

于是忽然又想到，因为List的add()操作默认是在末尾添加成员，如果是在列首又会如何？

修改后的代码

public class StudentList {
    //...
    //添加一个指定加入位置的函数
    public void add(int pos,int _id,String _name,int _age,boolean _sex,int _score,int _grade) {
        list.add(pos,new Student(_id, _name, _age, _sex, _score, _grade));
    }
    //...
}
public class WithStruct {
    //...
    private static void test() {
        //初始化过程还是一样的，在末尾插入，并且将实验将数量级调小成 100000，后续因为会很慢
        //...
        //添加100000名学生（数量级调小）
        for(int i=100000;i<200000;i++) {
            //在首位插入（pos = 0）
            sl.add(0, 2010000000+(int)(rd.nextDouble()*1000000),
                    "sd."+i, 18+(int)(rd.nextDouble()*4),
                    rd.nextDouble()>0.5?true:false,
                    100+(int)(rd.nextDouble()*300),
                    1+(int)(rd.nextDouble()*3)
            );
        }
        //...
    }
}

结果：

ArrayList:
Initialization: 31ms
Add 1000000 students: 2028ms

LinkedList:
Initialization: 30ms
Add 1000000 students: 21ms

链表LinkedList的优势瞬间就体现出来了，这次和预想的没有什么偏差

如果是动态数组，在首位插入的话，就需要new一个数组，然后将原来的数组移过去，并且每次都要相对往后移一位，空出首位给新添加的成员，也许就是因为这个移动操作导致效率变得很低
（当然我自己也瞎想过，如果是在拷贝的时候直接就错开一位去拷贝，而不是事后移动，那么会不会更快？那为什么一开始编写这些源码的人没有这样考虑？又或者是因为考虑到系统底层的拷贝操作效率之类的而没有选择这么做？……然而我还要写实验，先饶了自己的大脑，而且也没时间去自己写一个来实验了……）

如果是链表，那么只需要在头指针处加入一个新节点就好了，不需要进行繁重的遍历赋值工作

而且我发现，在首位插入和在末尾插入，对LinkedList来说，几乎是一样的，也就是说实际上LinkedList是有两个指针，一个头一个尾？

有了点想法，于是又稍微改了一下函数来实验

修改²后的代码

public class WithStruct {
    //...
    private static void test() {
        //...
        //添加10000名学生（数量级再次调小）
        for(int i=10000;i<20000;i++) {
            //在中间位置插入（pos = i/2）
            sl.add(i/2, //...
            );
        }
        //...
    }
}

结果：

ArrayList:
Initialization: 6ms
Add 10000 students: 12ms

LinkedList:
Initialization: 8ms
Add 10000 students: 501ms

这就对了，在中间插入插入的时候，LinkedList要比ArrayList慢上不止一点，比末尾插入还惨很多，而且数量级越大差的也越大，因为LinkedList只有首位有指针，因此在中间插入的时候指针移动造成的时间开销是最大的

结论

如果是今后使用的话，也许ArrayList还是首选，从添加/删除数据的角度来说，只要操作的位置不是很靠近头部，ArrayList都具有明显优势；而对于访问数据来说，ArrayList更具有优势，因为LinkedList访问成员需要移动指针