Preface
Through this article, you can understand the five traversal methods of List, their respective performances and the implementation of foreach and Iterator, and deepen your understanding of ArrayList and LinkedList implementations. Let’s take a look together below.
1. Five ways to traverse List
1. For each loop
List<Integer> list = new ArrayList<Integer>();for (Integer j : list) { // use j}2. Display 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. Incremental loop of subscript, the termination condition is to compare and judge each time the size() function is called
List<Integer> list = new ArrayList<Integer>(); for (int j = 0; j < list.size(); j++) { list.get(j);}4. Incremental cycle of subscript, comparison and judgment of temporary variables whose termination conditions are sum 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 test and comparison of five traversal methods of List
The following is the performance test code, which outputs the time spent on various traversal methods of ArrayList and LinkedList of 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, 100000, 9000000)); System.out.print("/r/n/r/ncompare loop performance of LinkedList"); loopListCompare(getLinkedLists(100, 1000, 10000, 10000)); } 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 the run report an exception in thread “main” java.lang.OutOfMemoryError: Java heap space , please reduce the size of list size in main function.
The getArrayLists function will return an ArrayList with different size , and the getLinkedLists function will return a LinkedList with different size .
loopListCompare function will use the above traversal method 1-5 to traverse the list in each list array (including lists of different sizes).
The function starting with print is an output helper function.
The test environment is Windows 7 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 is the comparison result of ArrayList, and the second table is the comparison result of LinkedList.
The horizontal direction of the table is the time consumption of traversal of different sizes of lists in the same traversal method, and the vertical direction is the time consumption of traversal of different traversal methods of the same list.
PS: Since the first traversal of List will take a little more time, the results of for each are slightly deviated. If you swap several Types in the test code, you will find that for each time is close to that of for iterator .
Analysis of performance test results of traversal method
1. Foreach introduction
foreach is a very powerful 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 simple to write, and there is no need to care about the initial value, terminating value, and cross-border, so it is not easy to make mistakes.
2. Analysis of results of ArrayList traversal method
a. Before the ArrayList size was 100,000, the time consumption of the five traversal methods was almost the same
b. After 100,000, the fourth and fifth traversal methods are faster than the first three, the get method is better than the Iterator method, and
int size = list.size();for (int j = 0; j < size; j++) { list.get(j);} Replacing list.size() with temporary variable size is better performance. Let's take a look at the implementation of Iterator and get methods in ArrayList
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } …} public E get(int index) { rangeCheck(index); return elementData(index);} From this we can see that the next functions of get and Iterator also obtain elements by directly positioning data, but there are only a few more judgments.
c. From the above, we can see that even in the ArrayList of tens of millions, the difference between the several traversal methods is only about 50ms, and the time is almost equal to about 100,000. Considering the advantages of foreach, we can choose to use the simple method of foreach foreach for traversal.
3. Analysis of results of LinkedList traversal method
a. When the size of LinkedList is close to 10,000, the get method and Iterator method are already about two orders of magnitude different. When the 100,000, the performance of Iterator method is far better than the get method.
Let's take a look at the implementation of iterators and get methods in LinkedList
private class ListItr implements ListIterator<E> { private Node<E> lastReturned = null; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } …} public E get(int index) { checkElementIndex(index); return node(index).item;} /** * Returns the (non-null) Node at the specified element index. */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; }} From the above code, we can see that the next function of the LinkedList iterator just quickly gets the next element through the next pointer and returns. The get method will traverse from the beginning until the index subscript, and find an element with a time complexity of O(n), and the time complexity of the traversal will reach O(n2).
Therefore, it is recommended to use foreach for traversal of LinkedList to avoid using get .
4. Comparative analysis of the results of ArrayList and LinkedList traversal methods
From the above order of magnitude, it is also a foreach loop traversal, and the time of ArrayList and LinkedList are similar. If you modify this example slightly and increase list size you will find that the two are basically on the same order of magnitude.
However, the time complexity of ArrayList get function is O(1), while the time complexity of the LinkedList get function is O(n).
If you consider space consumption, it is recommended to choose ArrayList first. For individual insertion and deletion, you can use LinkedList.
Conclusion summary
Through the above analysis, we can basically summarize:
Summarize
The above is the entire content of this article. I hope the content of this article will be helpful to everyone when learning or using Java. If you have any questions, you can leave a message to communicate.