comparison of Linkedlist over arraylist
This question already has an answer here:
Linkedlist is indeed faster on insertion, the problem is with your example. In your code you insert by appending to the end all the time. For ArrayList it is as easy as for LinkedList. What you should do is to build a list of say 5000 items and then start inserting in the middle. Here array becomes slow - you have to shift all the time the rest of the array after the insertion position. This is what will show the difference. Analyzing how the things work, it is not difficult to understand why. Here is the modified code:
import java.util.Date;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
public class Prob {
public static void main(String[] args) {
long lStartTime = new Date().getTime();
System.out.println("lStartTime:: " + lStartTime);
List<Integer> integerList = new LinkedList<Integer>();
for (int i = 0; i < 5000; i++) {
integerList.add(0, i);
}
for (int i = 0; i < 100000; i++) {
integerList.add(1000, i);
}
long lEndTime = new Date().getTime();
System.out.println("lEndTime:: " + lEndTime);
long difference = lEndTime - lStartTime;
System.out.println("Elapsed milliseconds: " + difference);
}
}
LinkedList is not faster than ArrayList in insertion. ArrayList is backed by an array, so inserting an element is trivial. Insertion to a LinkedList involves creation of a new Entry instance, which is slower.
The only time insert to an ArrayList may be slower is when the insert causes the ArrayList capacity to be increased, which requires a new array to be created and the old array copied to it.
上一篇: 数组列表操作的运行时间按索引添加和删除