[Note] Java: Speed of List processing by purpose

Introduction

A collection is a box that can store multiple elements such as ʻArrayList and LinkedList. This time I will write about the following two collections. The answer is written in the reference book, but I would like to try it for myself and experience it. If possible, compare it with the array. ・ ʻArrayListLinkedList

Conclusion

Addition is a little faster with ʻArrayList. (LinkedList is also fast enough) Acquisition is much faster with ʻArrayList. The deletion is by far the fastest LinkedList.

Since it takes a long time to get the LinkedList When making a list with acquisition, I think ʻArrayList` is fine.

Add x Get=> `ArrayList`
Add x Delete=> `LinkedList`
Add x Get x Delete=> `ArrayList`

1, Add element

CompareList.java


import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class CompareList {
    public static void main(String[] args) {
        //Start measuring arrayList
        long arrayStart = System.currentTimeMillis();
        //Preparation
        List<String> addArrayList = new ArrayList<String>();
        //Additional processing
        for (int num = 0; num<1000000; num++) {
            addArrayList.add("element");
        }
        //End of measurement of arrayList
        long arrayEnd = System.currentTimeMillis();
        System.out.println("arrayList(add to) : "+(arrayEnd - arrayStart)  + "ms");
        //Confirm additional quantity
        int arraylistSize = addArrayList.size();
        System.out.println(arraylistSize);

        //Start measurement of linkedList
        long linkedStart = System.currentTimeMillis();
        //Preparation
        List<String> addLinkedList = new LinkedList<String>();
        //Additional processing
        for (int num = 0; num<1000000; num++) {
            addLinkedList.add("element");
        }
        //End of measurement of linkedList
        long linkedEnd = System.currentTimeMillis();
        System.out.println("linkedList(add to) : "+(linkedEnd - linkedStart)  + "ms");
        //Confirm additional quantity
        int linkedListSize = addLinkedList.size();
        System.out.println(linkedListSize);
    }
}

result.java


        arrayList(add to) : 35ms
        1000000
        linkedList(add to) : 259ms
        1000000

2, delete element

CompareList.java



import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class CompareList {
    public static void main(String[] args) {
        //Prepare a list with 30000 elements
        String elem = "elem";
        List<String> array30000elems = new ArrayList<String>();
        List<String> linked30000elems = new LinkedList<String>();
        for(int i = 0; i<300000; i++){
            array30000elems.add(elem);
            linked30000elems.add(elem);
        }

        //arrayList measurement start
        long arrayStart = System.currentTimeMillis();
        int num = 0;
        //Delete process
        while(array30000elems.size() > 0){
            num += 1;
            array30000elems.remove(elem);
        }
        System.out.println("processing time: "+num+"Times");
        long arrayEnd = System.currentTimeMillis();
        System.out.println("arrayList(Delete) : "+(arrayEnd - arrayStart)  + "ms");

        //linkedList measurement start
        long linkedStart = System.currentTimeMillis();
        int num2 = 0;
        //Delete process
        while(linked30000elems.size() > 0){
            num2 += 1;
            linked30000elems.remove(elem);
        }
        System.out.println("processing time: "+num2+"Times");
        long linkedEnd = System.currentTimeMillis();
        System.out.println("linkedList(Delete) : "+(linkedEnd - linkedStart)+"ms");
    }
        
}

result.java


processing time:300,000 times
        arrayList(Delete) : 5387ms
processing time:300,000 times
        linkedList(Delete) : 16ms

3, get element

CompareList.java


import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class CompareList {
    public static void main(String[] args) {
        //Prepare a list with 30000 elements
        String elem = "elem";
        List<String> array30000elems = new ArrayList<String>();
        List<String> linked30000elems = new LinkedList<String>();
        for(int i = 0; i<300000; i++){
            array30000elems.add(elem);
            linked30000elems.add(elem);
        }

        //arrayList measurement start
        int count = 0;
        long arrayStart = System.currentTimeMillis();
        //Acquisition process
        for(int i = 0; i < array30000elems.size(); i++){
            count += 1;
            array30000elems.get(i);
        }
        long arrayEnd = System.currentTimeMillis();
        System.out.println("arrayList(Get) : "+(arrayEnd - arrayStart)  + "ms");
        System.out.println("processing time: "+count+"Times");

        //linkedList measurement start
        int count2 = 0;
        long linkedStart = System.currentTimeMillis();
        //Acquisition process
        for(int i = 0; i < linked30000elems.size(); i++){
            count2 += 1;
            linked30000elems.get(i);
        }
        long linkedEnd = System.currentTimeMillis();
        System.out.println("linkedList(Get) : "+(linkedEnd - linkedStart)  + "ms");
        System.out.println("processing time: "+count2+"Times");

    }
        
}

result.java


        arrayList(Get) : 7ms
processing time:300,000 times
        linkedList(Get) : 38475ms
processing time:300,000 times

4, combination of addition and deletion

CompareList.java


import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class CompareList {
    public static void main(String[] args) {
        String elem = "elem";

        List<String> samplelist = new ArrayList<String>();
        long start1 = System.currentTimeMillis();
        for(int i =0; i < 30000; i++){
            samplelist.add(elem);
        }
        System.out.println("After addition: "+samplelist.size());
        while(samplelist.size() > 0){
            samplelist.remove(elem);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("arrayList(Add delete) : "+(end1 - start1)  + "ms");
        System.out.println("After deletion: "+samplelist.size());

        List<String> samplelist2 = new LinkedList<String>();
        long start2 = System.currentTimeMillis();
        for(int i =0; i < 30000; i++){
            samplelist2.add(elem);
        }
        System.out.println("After addition: "+samplelist2.size());
        while(samplelist2.size() > 0){
            samplelist2.remove(elem);
        }
        long end2 = System.currentTimeMillis();
        System.out.println("linkedList(Add delete) : "+(end2 - start2)  + "ms");
        System.out.println("After deletion: "+samplelist2.size());
    }
        
}

result.java


After addition: 30000
        arrayList(Add delete) : 78ms
After deletion: 0
After addition: 30000
        linkedList(Add delete) : 21ms
After deletion: 0

5, combination of addition, acquisition and deletion

CompareList.java


import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class CompareList {
    public static void main(String[] args) {
        String elem = "elem";

        // arrayList
        List<String> samplelist = new ArrayList<String>();
        long start1 = System.currentTimeMillis();

        //Added 300,000
        for(int i =0; i < 300000; i++){
            samplelist.add(elem);
        }
        System.out.println("After addition: "+samplelist.size());

        //Get 300,000
        for(int i = 0; i < samplelist.size(); i++){
            samplelist.get(i);
        }
        //Output the time taken for additional acquisition
        long half1 = System.currentTimeMillis();
        System.out.println("arrayList(Additional acquisition) : "+(half1 - start1)  + "ms");

        //Delete 300,000
        while(samplelist.size() > 0){
            samplelist.remove(elem);
        }

        //Output the time taken from addition to deletion
        long end1 = System.currentTimeMillis();
        System.out.println("arrayList(Add acquisition delete) : "+(end1 - start1)  + "ms");
        System.out.println("After deletion: "+samplelist.size());


        // linkedList
        List<String> samplelist2 = new LinkedList<String>();
        long start2 = System.currentTimeMillis();

        //Added 300,000
        for(int i =0; i < 300000; i++){
            samplelist2.add(elem);
        }
        System.out.println("After addition: "+samplelist2.size());

        //Get 300,000
        for(int i = 0; i < samplelist2.size(); i++){
            samplelist2.get(i);
        }

        //Output the time taken for additional acquisition
        long half2 = System.currentTimeMillis();
        System.out.println("linkedList(Additional acquisition) : "+(half2 - start2)  + "ms");

        //Delete 300,000
        while(samplelist2.size() > 0){
            samplelist2.remove(elem);
        }

        //Output the time taken from addition to deletion
        long end2 = System.currentTimeMillis();
        System.out.println("linkedList(Add acquisition delete) : "+(end2 - start2)  + "ms");
        System.out.println("After deletion: "+samplelist2.size());
    }
        
}

result.java


After addition: 300000
        arrayList(Additional acquisition) : 34ms
        arrayList(Add acquisition delete) : 5152ms
After deletion: 0
After addition: 300000
        linkedList(Additional acquisition) : 37727ms
        linkedList(Add acquisition delete) : 37745ms
After deletion: 0

Recommended Posts

[Note] Java: Speed of List processing by purpose
[Note] Java: Measures the speed of string concatenation
Summary of java error processing
[Java] Basic summary of Java not covered by Progate ~ Part 2 · List ~
[Java] Speed comparison of string concatenation
[Java] Delete the elements of List
Sort a List of Java objects
[Java] Output by FormatStyle of DateTimeFormatter
[Note] Handling of Java decimal point
List of members added in Java 9
Surprisingly deep Java list inversion-Stream processing
Basic processing flow of java Stream
List of types added in Java 9
Basic knowledge of Java development Note writing
List of download destinations for oracle java
[Java] Note how to use RecyclerView and implementation of animated swipe processing.
[Java] Contents of Collection interface and List interface
[Java] Dynamic method call by reflection of enum (enum)
[Java / Spring Boot] Spring security ⑤ --Implementation of logout processing
Java memorandum (list)
Clone Java List.
Java thread processing
Java string processing
[Introduction to Java] List of things that got caught by the 14th day of programming
[Java] Multi-thread processing
[Java] Overview of Java
[Java] Stream processing
About List [Java]
Simple statistical analysis of monetary value from the list searched by Mercari Java development
java iterative processing
[Java] Basic summary of Java not covered by Progate ~ Part 1 ~
List processing to understand with pictures --java8 stream / javaslang-
Get a list of MBean information for Java applications
Please note the division (division) of java kotlin Int and Int
Summary of revisions (new era) support by Java version
Implementation example of simple LISP processing system (Java version)
Stream processing of Java 8 can be omitted so far!
Image processing: The basic structure of the image read by the program
Comparative study of TLS Cipher Suite supported by Java 8
List of frequently used Java instructions (for beginners and beginners)