浅谈ArrayList和LinkedList到底谁更快

浅谈ArrayList和LinkedList到底谁更快

一、ArrayList和LinkedList究竟谁快

在java中应该都知道ArrayList和LinkedList，

一直以来的概念呢是

ArrayList在get(index)这个应该比LinkedList快；

LinkedList比ArrayList在add(index,element)快；

两者共同遍历呢，应该是一样快的，毕竟都要循环遍历一遍。

直到我写了一个测试类

package com.lw;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import org.junit.Test;

public class TestJDKList {

List linkedList = new LinkedList<>();

List arrayList = new ArrayList<>();

int length = 1000000;

@Test

public void testLinkedInsert(){

for (int i = 0; i < length; i++) {

linkedList.add(i);

}

long currentMi2 = System.currentTimeMillis();

linkedList.add(length/2,3);

long endTime2 = System.currentTimeMillis();

System.out.println("testLinkedInsert:" + (endTime2 - currentMi2)); // 9

}

@Test

public void testArrayInsert(){

for (int i = 0; i < length; i++) {

arrayList.add(i);

}

long currentMi2 = System.currentTimeMillis();

arrayList.add(length/2,3);

long endTime2 = System.currentTimeMillis();

System.out.println("testArrayInsert:" + (endTime2 - currentMi2)); // 1

}

@Test

public void testLinkedGet(){

for (int i = 0; i < length; i++) {

linkedList.add(i);

}

long currentMi2 = System.currentTimeMillis();

linkedList.get(length/2);

long endTime2 = System.currentTimeMillis();

System.out.println("testLinkedGet:" + (endTime2 - currentMi2)); // 5

}

@Test

public void testArrayGet(){

for (int i = 0; i < length; i++) {

arrayList.add(i);

}

long currentMi2 = System.currentTimeMillis();

arrayList.get(length/2);

long endTime2 =vAfMQL System.currentTimeMillis();

System.out.println("testArrayGet:" + (endTime2 - currentMi2)); // 0

}

@Test

public void testLinkedIter(){

for (int i = 0; i < length; i++) {

linkedList.add(i);

}

long currentMi2 = System.currentTimeMillis();

for (Integer i : linkedList) {

};

long endTime2 = System.currentTimeMillis();

System.out.println("testLinkedIter:" + (endTime2 - currentMi2)); // 26

}

@Test

public void testArrayIter(){

for (int i = 0; i < length; i++) {

arrayList.add(i);

}

long currentMi2 = System.currentTimeMillis();

for (Integer i : arrayList) {

};

long endTime2 = System.currentTimeMillis();

System.out.println("testArrayIter:" + (endTime2 - currentMi2)); // 11

}

@Test

public void testLinkedAdd() {

long currentMi2 = System.currentTimeMillis();

for (int i = 0; i < length; i++) {

linkedList.add(i);

}

long endTime2 = System.currentTimeMillis();

System.out.println("testLinkedAdd:" + (endTime2 - currentMi2)); // 53

}

@Test

public void testArrayAdd(){

long currentMi1 = System.currentTimeMillis();

for (int i = 0; i < length; i++) {

arrayList.add(i);

}

long endTime1 = System.currentTimeMillis();

System.out.println("testArrayAdd:" + (endTime1 - currentMi1)); // 35

}

}

二、结果

运行了两遍结果如下：

testLinkedInsert:7

testArrayInsert:0

testLinkedAdd:218

testArrayAdd:23

testLinkedGet:4

testArrayGet:0

testLinkedIter:14

testArrayIter:11

----------------第二遍分割线---------------------------------

testLinkedInsert:12

testArrayInsert:0

testLinkedIter:13

testArrayIter:12

testLinkedGet:3

testArrayGet:0

testLinkedAdd:119

testArrayAdd:23

颠覆三观，ArrayList竟然无论怎样都比LinkedList快？？

三、循环Add

ArrayList的add源码，它是把数据放在一个数组中

transient Object[] elementData;

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

而LinkedList源码，是把数据放在Node对象中，有个前后指针。

public boolean add(E e) {

linkLast(e);

return true;

}

void linkLast(E e) {

final Node l = last;

final Node newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

private static class Node {

E item;

Node next;

Node prev;

Node(Node prev, E element, Node next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

难道是前后指针这里花时间了么？

四、指定位置Get

再看get方法，

ArrayList的get，因为是连续的内存，所以取数据很快。

public E get(int index) {

rangeCheck(index);

return elementData(index);

}

E elementData(int index) {

vAfMQL return (E) elementData[index];

}

再看LinkedList的get，是通过指针遍历的，直到是这个index为止。

这里还有判断size，如果是size的前一半，则通过first节点往后去找，如果在后一半则通过last节点往前找，这样会更快，所以LinkedList的查找其实也不慢。

public E get(int index) {

checkElementIndex(index);

return node(index).item;

}

Node node(int index) {

// assert isElementIndex(index);

if (index < (size >> 1)) {

Node x = first;

for (int i = 0; i < index; i++)

x = x.next;

return x;

} else {

Node x = last;

for (int i = size - 1; i > index; i--)

x = x.prev;

return x;

}

}

五、指定位置Add

ArrayList的add(index,element)

这里是可以扩容的，将index后半段拷贝到index+1，然后在index插入一个新的，但没想到这么快。

其实也能想到System.arraycopy是native，所以快也能理解

public void add(int index, E element) {

rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!

System.arraycopy(elementData, index, elementData, index + 1,

size - index);

elementData[index] = element;

size++;

}

然后是LinkedList的add(index,element)

无非是指针的指向变化而已，但没想到比上面的System.arraycopy还要慢，果然不愧为native方法。

public void add(int index, E element) {

checkPositionIndex(index);

if (index == size)

linkLast(element);

else

linkBefore(element, node(index));

}

void linkBefore(E e, Node succ) {

// assert succ != null;

final Node pred = succ.prev;

final Node newNode = new Node<>(pred, e, succ);

succ.prev = newNode;

if (pred == null)

first = newNode;

else

pred.next = newNode;

size++;

modCount++;

}

void linkLast(E e) {

final Node l = last;

final Node newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

所以项目中大部分用ArrayList也就是可以理解。

不过ArrayList是连续的内存空间，在内存空间很紧张情况下，LinkedList内存利用率更高。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。