Traversal and performance analysis of ArrayList and LinkedList in Java
- 2020-05-19 04:53:14
- OfStack
preface
In this article, you can learn about the five traversal modes of List and their respective performance, as well as the implementation of foreach and Iterator, and learn more about the implementation of ArrayList and LinkedList. Let's take a look.
1. Five traversal methods of List
1. for each cycle
List<Integer> list = new ArrayList<Integer>();
for (Integer j : list) {
// use j
}
2. Display the call collection iterator
List<Integer> list = new ArrayList<Integer>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
or
List<Integer> list = new ArrayList<Integer>();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
iterator.next();
}
3. The subscript increments the loop, and the termination condition is the comparison judgment of size() function every time it is called
List<Integer> list = new ArrayList<Integer>();
for (int j = 0; j < list.size(); j++) {
list.get(j);
}
4. The subscript increases the loop, and the termination condition is judged by comparing with the temporary variable equal to size()
List<Integer> list = new ArrayList<Integer>();
int size = list.size();
for (int j = 0; j < size; j++) {
list.get(j);
}
5. Subscript decreasing cycle
List<Integer> list = new ArrayList<Integer>();
for (int j = list.size() - 1; j >= 0; j--) {
list.get(j);
}
Performance testing and comparison of List5 traversal methods
The following is the performance test code that outputs the amount of time it takes to traverse ArrayList and LinkedList in different orders of magnitude.
package cn.trinea.java.test;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* JavaLoopTest
*
* @author www.trinea.cn 2013-10-28
*/
public class JavaLoopTest {
public static void main(String[] args) {
System.out.print("compare loop performance of ArrayList");
loopListCompare(getArrayLists(10000, 100000, 1000000, 9000000));
System.out.print("\r\n\r\ncompare loop performance of LinkedList");
loopListCompare(getLinkedLists(100, 1000, 10000, 100000));
}
public static List<Integer>[] getArrayLists(int... sizeArray) {
List<Integer>[] listArray = new ArrayList[sizeArray.length];
for (int i = 0; i < listArray.length; i++) {
int size = sizeArray[i];
List<Integer> list = new ArrayList<Integer>();
for (int j = 0; j < size; j++) {
list.add(j);
}
listArray[i] = list;
}
return listArray;
}
public static List<Integer>[] getLinkedLists(int... sizeArray) {
List<Integer>[] listArray = new LinkedList[sizeArray.length];
for (int i = 0; i < listArray.length; i++) {
int size = sizeArray[i];
List<Integer> list = new LinkedList<Integer>();
for (int j = 0; j < size; j++) {
list.add(j);
}
listArray[i] = list;
}
return listArray;
}
public static void loopListCompare(List<Integer>... listArray) {
printHeader(listArray);
long startTime, endTime;
// Type 1
for (int i = 0; i < listArray.length; i++) {
List<Integer> list = listArray[i];
startTime = Calendar.getInstance().getTimeInMillis();
for (Integer j : list) {
// use j
}
endTime = Calendar.getInstance().getTimeInMillis();
printCostTime(i, listArray.length, "for each", endTime - startTime);
}
// Type 2
for (int i = 0; i < listArray.length; i++) {
List<Integer> list = listArray[i];
startTime = Calendar.getInstance().getTimeInMillis();
// Iterator<Integer> iterator = list.iterator();
// while(iterator.hasNext()) {
// iterator.next();
// }
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
endTime = Calendar.getInstance().getTimeInMillis();
printCostTime(i, listArray.length, "for iterator", endTime - startTime);
}
// Type 3
for (int i = 0; i < listArray.length; i++) {
List<Integer> list = listArray[i];
startTime = Calendar.getInstance().getTimeInMillis();
for (int j = 0; j < list.size(); j++) {
list.get(j);
}
endTime = Calendar.getInstance().getTimeInMillis();
printCostTime(i, listArray.length, "for list.size()", endTime - startTime);
}
// Type 4
for (int i = 0; i < listArray.length; i++) {
List<Integer> list = listArray[i];
startTime = Calendar.getInstance().getTimeInMillis();
int size = list.size();
for (int j = 0; j < size; j++) {
list.get(j);
}
endTime = Calendar.getInstance().getTimeInMillis();
printCostTime(i, listArray.length, "for size = list.size()", endTime - startTime);
}
// Type 5
for (int i = 0; i < listArray.length; i++) {
List<Integer> list = listArray[i];
startTime = Calendar.getInstance().getTimeInMillis();
for (int j = list.size() - 1; j >= 0; j--) {
list.get(j);
}
endTime = Calendar.getInstance().getTimeInMillis();
printCostTime(i, listArray.length, "for j--", endTime - startTime);
}
}
static int FIRST_COLUMN_LENGTH = 23, OTHER_COLUMN_LENGTH = 12, TOTAL_COLUMN_LENGTH = 71;
static final DecimalFormat COMMA_FORMAT = new DecimalFormat("#,###");
public static void printHeader(List<Integer>... listArray) {
printRowDivider();
for (int i = 0; i < listArray.length; i++) {
if (i == 0) {
StringBuilder sb = new StringBuilder().append("list size");
while (sb.length() < FIRST_COLUMN_LENGTH) {
sb.append(" ");
}
System.out.print(sb);
}
StringBuilder sb = new StringBuilder().append("| ").append(COMMA_FORMAT.format(listArray[i].size()));
while (sb.length() < OTHER_COLUMN_LENGTH) {
sb.append(" ");
}
System.out.print(sb);
}
TOTAL_COLUMN_LENGTH = FIRST_COLUMN_LENGTH + OTHER_COLUMN_LENGTH * listArray.length;
printRowDivider();
}
public static void printRowDivider() {
System.out.println();
StringBuilder sb = new StringBuilder();
while (sb.length() < TOTAL_COLUMN_LENGTH) {
sb.append("-");
}
System.out.println(sb);
}
public static void printCostTime(int i, int size, String caseName, long costTime) {
if (i == 0) {
StringBuilder sb = new StringBuilder().append(caseName);
while (sb.length() < FIRST_COLUMN_LENGTH) {
sb.append(" ");
}
System.out.print(sb);
}
StringBuilder sb = new StringBuilder().append("| ").append(costTime).append(" ms");
while (sb.length() < OTHER_COLUMN_LENGTH) {
sb.append(" ");
}
System.out.print(sb);
if (i == size - 1) {
printRowDivider();
}
}
}
PS: if run report exception
in thread “main” java.lang.OutOfMemoryError: Java heap space
, please send
main
Inside the function
list size
The magnitude of theta goes down.
Among them
getArrayLists
The function will return differently
size
ArrayList,
getLinkedLists
The function will return differently
size
LinkedList.
loopListCompare
The function iterates through the list of each list array (containing different sizes of list) using the 1-5 traversal method above.
print
The starting function is the output auxiliary function.
The test environment was Windows7 32-bit system 3.2G dual-core CPU 4G memory, Java 7, Eclipse-Xms512m-Xmx512m
The final test results are as follows:
compare loop performance of ArrayList
-----------------------------------------------------------------------
list size | 10,000 | 100,000 | 1,000,000 | 10,000,000
-----------------------------------------------------------------------
for each | 1 ms | 3 ms | 14 ms | 152 ms
-----------------------------------------------------------------------
for iterator | 0 ms | 1 ms | 12 ms | 114 ms
-----------------------------------------------------------------------
for list.size() | 1 ms | 1 ms | 13 ms | 128 ms
-----------------------------------------------------------------------
for size = list.size() | 0 ms | 0 ms | 6 ms | 62 ms
-----------------------------------------------------------------------
for j-- | 0 ms | 1 ms | 6 ms | 63 ms
-----------------------------------------------------------------------
compare loop performance of LinkedList
-----------------------------------------------------------------------
list size | 100 | 1,000 | 10,000 | 100,000
-----------------------------------------------------------------------
for each | 0 ms | 1 ms | 1 ms | 2 ms
-----------------------------------------------------------------------
for iterator | 0 ms | 0 ms | 0 ms | 2 ms
-----------------------------------------------------------------------
for list.size() | 0 ms | 1 ms | 73 ms | 7972 ms
-----------------------------------------------------------------------
for size = list.size() | 0 ms | 0 ms | 67 ms | 8216 ms
-----------------------------------------------------------------------
for j-- | 0 ms | 1 ms | 67 ms | 8277 ms
-----------------------------------------------------------------------
The first table shows the ArrayList comparison results, and the second table shows the LinkedList comparison results.
The table shows the time consumption of list traversal in the same 1 traversal mode with different sizes horizontally, and the time consumption of list traversal in the same 1list traversal mode in the vertical.
PS: since it takes a little longer to traverse List for the first time,
for each
The results of the test code are slightly biased. If you switch the order of several Type in the test code, you will find that,
for each
Time-consuming and
for iterator
Close to.
Performance test results analysis of traversal mode
1. Introduction to foreach
foreach is a highly functional loop structure introduced by Java SE5.0.
for (Integer j : list)
Should be read
for each int in list
.
for (Integer j : list)
Implementation is almost equivalent to
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
Integer j = iterator.next();
}
The foreach code is easy to write and is not susceptible to errors because it doesn't have to worry about subscript initialization and termination values and bounds
2. ArrayList ergodic result analysis
a. Before the size of ArrayList was 100,000, the five traversal methods consumed almost one time
b. After 100,000, the fourth and fifth traversal method is faster than the first three, get is better than Iterator, and
int size = list.size();
for (int j = 0; j < size; j++) {
list.get(j);
}
Replace with the temporary variable size
list.size()
Better performance. Let's look at the iterator in ArrayList
Iterator
and
get
Method implementation
List<Integer> list = new ArrayList<Integer>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
0
And you can see that
get
and
Iterator
the
next
The function also retrieves the element by locating the data directly, but with a few more judgements.
c. It can be seen from the above that even in ArrayList of tens of millions, the difference between several traversal methods is only about 50ms, and it is almost the same in the common time of about 100,000. Considering the advantages of foreach, we can choose foreach as a simple method for traversal.
3. LinkedList traversal method results analysis
a. When the size of LinkedList approaches 10,000,
get
Way and
Iterator
It's about two orders of magnitude different, 100,000 hours
Iterator
Mode performance is already much better than get.
Let's look at the iterator and in LinkedList
get
Method implementation
List<Integer> list = new ArrayList<Integer>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
1
You can see from the code above what the LinkedList iterator looks like
next
The function simply takes the next element through the next pointer and returns it. The get method traverses all the way to index subscript, finding an element with a time complexity of oh O(n), and the traversal time complexity reaches O(n2).
So foreach is recommended for LinkedList traversal, avoid it
get
Method traversal.
4. Comparison and analysis of ArrayList and LinkedList traversal results
From the above order of magnitude, the same foreach loop traversal, ArrayList and LinkedList are about the same time, this example can be slightly modified to increase
list size
You'll find that they're basically on the order of magnitude.
but
ArrayList get
The time complexity of the method of function direct location acquisition is O(1), while the time complexity of LinkedList's get function is O(n).
Considering the space consumption, ArrayList is recommended to be the first choice. LinkedList can be used for very large Numbers of individual inserts and deletions.
The conclusion summarizes
From the above analysis, we can basically summarize:
Whether ArrayList or LinkedList, it is recommended to use foreach for traversal, especially LinkedList to avoid using get for traversal when there is a large amount of data.List USES ArrayList preferred. LinkedList can be used for very large number of individual inserts and deletions.
It may be necessary to use subscripts within the traversal of the List loop, so consider whether to use foreach and self-incrementing count or get.
conclusion
The above is the whole content of this article, I hope the content of this article can help you to learn or use Java, if you have any questions, you can leave a message to communicate.