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.


Related articles: