Who is faster ArrayList or LinkedList
- 2021-09-12 01:15:09
- OfStack
1. Who is faster, ArrayList or LinkedList
ArrayList and LinkedList should both be known in Java,
1 What is the straight concept
ArrayList in get (index) This should be faster than LinkedList;
LinkedList is faster than ArrayList in add (index, element);
The two traversal together, should be a kind of fast, after all, have to cycle traversal once.
Until I wrote a test class
package com.lw;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import org.junit.Test;
public class TestJDKList {
List<Integer> linkedList = new LinkedList<>();
List<Integer> 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 = 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
}
}
2. Results
Run it twice and the result is as follows:
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
Subverting the 3 views, ArrayList is faster than LinkedList anyway? ?
3. Circulating Add
ArrayList add source code, it is to put data in an array
transient Object[] elementData;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
And LinkedList source code, is to put data in Node object, there is a pointer before and after.
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
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;
}
}
Did the front and back pointers take time here?
4. Specify location Get
Looking at get method,
get of ArrayList, because it is continuous memory, so fetch data quickly.
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Look at get of LinkedList again, which is traversed by pointer until it is this index.
There is also a judgment of size here. If it is the first half of size, look back through first node, and if it is in the last half, look forward through last node, which will be faster, so the search of LinkedList is actually not slow.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
5. Specify location Add
add of ArrayList (index, element)
It can be expanded here. Copy the second half of index to index+1, and then insert a new one in index, but I didn't expect it to be so fast.
In fact, you can also think of System. arraycopy is native, so you can understand it quickly
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++;
}
Then there is add of LinkedList (index, element)
It is nothing more than the pointing change of the pointer, but I didn't expect it to be slower than the above System. arraycopy, which is worthy of the native method.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> 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<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Therefore, it is understandable that most of the projects use ArrayList.
However, ArrayList is a continuous memory space, and the memory utilization rate of LinkedList is higher when the memory space is very tight.