ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构。在一次实验中偶然发现并实验了这两者的不同之处，很有意思
Head Pic: 「オリジナル」/「100％」[pixiv]
ArrayList 与 LinkedList
在写编程实验的时候因为用到了它俩，就突然想测试一下他们的效率，特别是在添加组员这方面
使用学生类作为测试对象
一开始的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14public 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));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public 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");
}
}
主要目的就是想测试一下加入成员的时候哪个效率更高，结果如下：
1
2
3
4
5
6
7ArrayList: Initialization: 166ms Add 1000000 students: 127ms LinkedList: Initialization: 1358ms Add 1000000 students: 1302ms
一开始看到这个我稍微有点意外，感觉和我想的不太一样……
因为我觉得链表添加成员，如果是动态数组的话，你需要new一个更大的数组，把原来的数据拷贝过去，然后在末尾将新成员的值拷贝过去；而链表，只需要在末尾加上一个新链就可以了
（懒得翻他们的源代码，想了想）觉得是因为分配内存空间和拷贝操作的速度是真的远远大于新建链表节点的操作，而且因为链表需要指针，也许指针相关操作也要消耗不少时间，大概只能这样解释
于是忽然又想到，因为List的add()操作默认是在末尾添加成员，如果是在列首又会如何？
修改后的代码
1
2
3
4
5
6
7
8public 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));
}
//...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public 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)
);
}
//...
}
}
结果：
1
2
3
4
5
6
7ArrayList: Initialization: 31ms Add 1000000 students: 2028ms LinkedList: Initialization: 30ms Add 1000000 students: 21ms
链表LinkedList的优势瞬间就体现出来了，这次和预想的没有什么偏差
如果是动态数组，在首位插入的话，就需要new一个数组，然后将原来的数组移过去，并且每次都要相对往后移一位，空出首位给新添加的成员，也许就是因为这个移动操作导致效率变得很低
（当然我自己也瞎想过，如果是在拷贝的时候直接就错开一位去拷贝，而不是事后移动，那么会不会更快？那为什么一开始编写这些源码的人没有这样考虑？又或者是因为考虑到系统底层的拷贝操作效率之类的而没有选择这么做？……然而我还要写实验，先饶了自己的大脑，而且也没时间去自己写一个来实验了……）
如果是链表，那么只需要在头指针处加入一个新节点就好了，不需要进行繁重的遍历赋值工作
而且我发现，在首位插入和在末尾插入，对LinkedList来说，几乎是一样的，也就是说实际上LinkedList是有两个指针，一个头一个尾？
有了点想法，于是又稍微改了一下函数来实验
修改²后的代码
1
2
3
4
5
6
7
8
9
10
11
12
13public class WithStruct {
//...
private static void test() {
//...
//添加10000名学生（数量级再次调小）
for(int i=10000;i<20000;i++) {
//在中间位置插入（pos = i/2）
sl.add(i/2, //...
);
}
//...
}
}
结果：
1
2
3
4
5
6
7ArrayList: Initialization: 6ms Add 10000 students: 12ms LinkedList: Initialization: 8ms Add 10000 students: 501ms
这就对了，在中间插入插入的时候，LinkedList要比ArrayList慢上不止一点，比末尾插入还惨很多，而且数量级越大差的也越大，因为LinkedList只有首位有指针，因此在中间插入的时候指针移动造成的时间开销是最大的
结论
如果是今后使用的话，也许ArrayList还是首选，从添加/删除数据的角度来说，只要操作的位置不是很靠近头部，ArrayList都具有明显优势；而对于访问数据来说，ArrayList更具有优势，因为LinkedList访问成员需要移动指针
版权声明：本文为原创文章，版权归 神代綺凜 所有。
本文链接：https://moe.best/java/java-array-and-linked.html
所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。
第二，Java的链表是单向循环链表，链表指针指向表尾，因为是循环链表，寻址到表头也非常快。
第三，List的操作不仅是添加和插入，还有删除！你没有测试删除。如果你测试删除，注意不是根据索引来删除，而是根据对象来删除，就能看出线性表和链表的区别了。
第四，Java的ArrayList会动态扩展数组容量，每次多一倍的容量（10，20，40，80。。。），你在表的末尾添加元素，在绝大部分情况下，那里都正好有一个空位，不需要移动任何元素，也不需要扩展容量，所以速度非常快。在表头插入元素，就需要移动元素，所以慢。
第五，在中间的某个索引位置插入元素的话，ArrayList是立即寻址，复杂度O（1），LinkedList要顺着指针链遍历，复杂度O（n），这是LinkedList较慢的主要原因。
总结，如果链表较大，且经常插入删除，还是要使用LinkedList。因为添加/插入通常都是在表头或者表尾发生，极少在表的中间，而在删除的时候，我们通常是要删除一个对象，且极少能事先知道对象在List里的索引，在不知道索引的情况删除元素，ArrayList就很慢了。
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }并且只有在jdk1.6及以前的版本中才是循环链表，之后的版本中改为了非循环链表，虽然只是换了种实现方法，功能还是一致的。（jdk1.6中只有Node header；之后的为Node first;Node last；两个）。
是不是直接把这款代码写在commer.php那里呢⌇●﹏●⌇大佬
如果从0开始弄的话，你还需要判断邮箱是不是qq邮箱，然后提取qq号，然后使用qlogo头像地址