[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. ・ ʻArrayList ・ LinkedList

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