对java数组进行插入和删除比链表快很多（一）
我们都知道，当数据量比较大时，数组适合做查找和修改频繁的操作，链表适合插入和删除频繁的操作，今天索性做个实验，比较一下二者进行各项操作耗时会相差多远，结果可能会让你很意外。
测试环境：
ubuntu 16.04
I5CPU 2.6hz
8G RAM
128g SSD1.ArrayList和LinkedList 随机修改10W个元素耗时
import java.util.*;
public class TestModify{
private static List<T> arrayList = new ArrayList<>();
private static List<T> linkedList = new LinkedList<>();
public static void main( String args[] ) {
long startTime = 0;
long endTime = 0;
initElems();
/* 随机修改100000个对象耗时对比*/
int j = 0;
Random random = new Random();
while(j++ < 5) {
startTime = System.currentTimeMillis();
for(int i = 1; i < 100000; i++ ) {
arrayList.set(random.nextInt(i), new T());
}
endTime = System.currentTimeMillis();
System.out.println("数组随机修改100000个对象耗时：" + (endTime - startTime) + "ms");
startTime = System.currentTimeMillis();
for(int i = 1; i < 100000; i++ ) {
linkedList.set(random.nextInt(i), new T());
}
endTime = System.currentTimeMillis();
System.out.println("链表随机修改100000个对象耗时：" + (endTime - startTime) + "ms");
System.out.println("");
}
}
/**
*各填充100000个元素
*/
private static void initElems() {
arrayList.clear();
linkedList.clear();
for(int i = 0; i < 100000; i++ ) {
arrayList.add(new T());
}
for(int i = 0; i < 100000; i++ ) {
linkedList.add(new T());
}
}
}
class T {
}运行结果：随机修改元素数组完胜，这个毫无疑问，因为数组可以直接定位要修改的元素，链表每次都要从头部或者从尾部定位到目标元素。
数组随机修改100000个对象耗时：23ms
链表随机修改100000个对象耗时：5438ms
数组随机修改100000个对象耗时：3ms
链表随机修改100000个对象耗时：5292ms
数组随机修改100000个对象耗时：2ms
链表随机修改100000个对象耗时：5331ms
数组随机修改100000个对象耗时：2ms
链表随机修改100000个对象耗时：5292ms
数组随机修改100000个对象耗时：3ms
链表随机修改100000个对象耗时：5312ms
2.ArrayList和LinkedList 随机删除10W个元素耗时
import java.util.*;
public class TestDelete{
private static List<T> arrayList = new ArrayList<>();
private static List<T> linkedList = new LinkedList<>();
public static void main( String args[] ) {
long startTime = 0;
long endTime = 0;
initElems();
Random random = new Random();
int j = 0; while(j++ < 5) {
initElems();
startTime = System.currentTimeMillis();
for(int i = 100000; i > 0; i--) {
arrayList.remove(random.nextInt(i));
}
endTime = System.currentTimeMillis();
System.out.println("数组删除10w 个元素耗时：" + (endTime - startTime) + "ms");
startTime = System.currentTimeMillis();
for(int i = 100000; i > 0; i--) {
linkedList.remove(random.nextInt(i));
}
endTime = System.currentTimeMillis();
System.out.println("链表删除10w 个元素耗时：" + (endTime - startTime) + "ms");
System.out.println("");
}
}
/**
*各填充100000个元素
*/
private static void initElems() {
arrayList.clear();
linkedList.clear();
for(int i = 0; i < 100000; i++ ) {
arrayList.add(new T());
}
for(int i = 0; i < 100000; i++ ) {
linkedList.add(new T());
}
}
}
class T {
}运行结果：
数组删除10w 个元素耗时：390ms
链表删除10w 个元素耗时：7520ms
数组删除10w 个元素耗时：378ms
链表删除10w 个元素耗时：7372ms
数组删除10w 个元素耗时：377ms
链表删除10w 个元素耗时：7221ms
数组删除10w 个元素耗时：390ms
链表删除10w 个元素耗时：7961ms
数组删除10w 个元素耗时：478ms
链表删除10w 个元素耗时：7743ms
对结果表示很吃惊，看了一下二者的实现源码：
ArrayList的remove方法源码：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}LinkedList的remove方法源码：
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}ArrayList的remove方法，有这样一行：
System.arraycopy(elementData,index+1,elementData,index,numMoved);这是系统提供的拷贝数组的方法，用来将数组elementData往前移动移位，这样就删除了指定元素，其实java的ArrayList对remove的实现,可以说和数据结构书上用c语言对删除数组元素所描述的一模一样， java中LinkedList对remove的实现过程也和书上描述的一样，大概过程是先定位到要删除元素的位置，然后修改该元素前一个元素对后一个元素的引用，比如a->b->c,改成a->c，这样就删除了b;按理说,数组进行元素的移动比较耗时，链表定位元素的位置比较耗时，元素移动耗时应该远大于链表定位元素耗时。
我又做了测试，把元素的删除位置定在6000，二者耗时基本持平，代码如下：
import java.util.*;
public class TestDelete{
private static List<T> arrayList = new ArrayList<>();
private static List<T> linkedList = new LinkedList<>();
public static void main( String args[] ) {
long startTime = 0;
long endTime = 0;
initElems();
int j = 0; while(j++ < 5) {
initElems();
startTime = System.currentTimeMillis();
for(int i = 100000; i > 10000; i--) {
arrayList.remove(6000);
}
endTime = System.currentTimeMillis();
System.out.println("数组第6000的位置删除90000个对象耗时：" + (endTime - startTime) + "ms");
startTime = System.currentTimeMillis();
for(int i = 100000; i > 10000; i--) {
linkedList.remove(6000);
}
endTime = System.currentTimeMillis();
System.out.println("链表在第6000的位置删除90000个对象耗时：" + (endTime - startTime) + "ms");
System.out.println("");
}
}
/**
*各填充100000个元素
*/
private static void initElems() {
arrayList.clear();
linkedList.clear();
for(int i = 0; i < 100000; i++ ) {
arrayList.add(new T());
}
for(int i = 0; i < 100000; i++ ) {
linkedList.add(new T());
}
}
}
class T {
}结果如下：
数组第6000的位置删除90000个对象耗时：684ms
链表在第6000的位置删除90000个对象耗时：822ms
数组第6000的位置删除90000个对象耗时：732ms
链表在第6000的位置删除90000个对象耗时：792ms
数组第6000的位置删除90000个对象耗时：678ms
链表在第6000的位置删除90000个对象耗时：793ms
数组第6000的位置删除90000个对象耗时：681ms
链表在第6000的位置删除90000个对象耗时：784ms
数组第6000的位置删除90000个对象耗时：681ms
链表在第6000的位置删除90000个对象耗时：795ms
6000在10W个元素中已经接近20分之1的位置，算上尾部也是10分之1，可见数组的平均删除元素耗时远少于链表。
3.ArrayList和LinkedList插入 10W个元素耗时
通过删除元素的实验已经可以看出，插入肯定也是数组快于列表，因为对数组来说，插入和删除都是对元素的移动，插入是向后移动元素，删除是向前移动元素，对链表来说，插入和删除都是定位，再修改引用（指针可能更好理解）。
代码如下：
import java.util.*;
public class TestInsert{
private static List<T> arrayList = new ArrayList<>();
private static List<T> linkedList = new LinkedList<>();
public static void main( String args[] ) {
long startTime = 0;
long endTime = 0;
initElems();
Random random = new Random();
int j = 0; while(j++ < 5) {
initElems();
startTime = System.currentTimeMillis();
for(int i = 100000; i > 0; i--) {
arrayList.add(random.nextInt(i), new T());
}
endTime = System.currentTimeMillis();
System.out.println("数组随机插入10w 个元素耗时：" + (endTime - startTime) + "ms");
startTime = System.currentTimeMillis();
for(int i = 100000; i > 0; i--) {
linkedList.add(random.nextInt(i), new T());
}
endTime = System.currentTimeMillis();
System.out.println("链表随机插入10w 个元素耗时：" + (endTime - startTime) + "ms");
System.out.println("");
}
System.out.println("size of arrayList : " + arrayList.size());
System.out.println("size of linkedList: " + linkedList.size());
}
/**
*各填充100000个元素
*/
private static void initElems() {
arrayList.clear();
linkedList.clear();
for(int i = 0; i < 100000; i++ ) {
arrayList.add(new T());
}
for(int i = 0; i < 100000; i++ ) {
linkedList.add(new T());
}
}
}
class T {
}运行结果如下:
数组随机插入10w 个元素耗时：2514ms
链表随机插入10w 个元素耗时：45534ms
数组随机插入10w 个元素耗时：2467ms
链表随机插入10w 个元素耗时：39717ms
数组随机插入10w 个元素耗时：2497ms
链表随机插入10w 个元素耗时：48627ms
数组随机插入10w 个元素耗时：2597ms
链表随机插入10w 个元素耗时：43840ms
数组随机插入10w 个元素耗时：2625ms
链表随机插入10w 个元素耗时：41139ms
size of arrayList : 200000
size of linkedList: 200000
总结：在java中用链表来实现插入和删除频繁的操作，速度并不见得比数组快，当插入和删除的位置极其靠近元素的头部时，链表会占优势，所以链表适合用来做队列这种会频繁操作头部的操作。最后，感觉以后写java代码可以少考虑LinkedList了。不知道这个结果是因为我的代码有问题，还是java底层实现起来确实链表比数组慢，有时间会再用C语言做这个实验。
声明：该文观点仅代表作者本人，牛骨文系教育信息发布平台，牛骨文仅提供信息存储空间服务。
- 上一篇： java 对数组进行插入删除修改
- 下一篇： php正则分割字符串中数字与字母
