[자료구조] ArrayList, LinkedList 차이

yookyungmin·2023년 9월 13일

ArrayList 와 LinkedList의 차이를 묻는 질문은 단골 질문이라고 해서 찾아 보고 어떠한 블로그를 참고하여 실습을 진행 해보았습니다.
LinkedList보다 ArrayList만 주로 사용해와서 ArrayList가 익숙하긴 합니다

package main.dataStructure;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;

public class ArrayLinked {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();

        LinkedList linkedList = new LinkedList();

        //ArrayList add
        long startTime = System.nanoTime();
        for(int i = 0; i< 100000; i++){
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        long duration = endTime - startTime;

        System.out.println("ArrayList add:" + duration);

        //LinkedList add
        startTime = System.nanoTime();
        for(int i = 0; i< 100000; i++){
            linkedList.add(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList add : " + duration);

        //ArrayList get
        startTime = System.nanoTime();
        for(int i = 0; i< 100000; i++){
            arrayList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList get : " + duration);

        //LinkedLiST get
        startTime = System.nanoTime();
        for(int i = 0; i< 100000; i++){
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList get : "  + duration);

        //ArrayList remove
        startTime = System.nanoTime();
        for(int i = 9999; i< 0; i--){
            arrayList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList remove : " + duration);

        //LinkedList remove
        startTime = System.nanoTime();
        for(int i = 9999; i< 0; i--){
            linkedList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList remove : " + duration);
    
    
        System.out.println("=============================================================");

        ArrayList ary = new ArrayList(2000000);
        LinkedList lkd = new LinkedList();

        System.out.println("======순차적으로 추가하기======");
        System.out.println("ArrayList = " + addF(ary));
        System.out.println("LinkedList = " + addF(lkd));

        System.out.println("\n======중간에 추가하기======");
        System.out.println("ArrayList = " + addM(ary));
        System.out.println("LinkedList = " + addM(lkd));

        System.out.println("\n======중간에 삭제하기======");
        System.out.println("ArrayList = " + removeM(ary));
        System.out.println("LinkedList = " + removeM(lkd));

        System.out.println("\n======순차적으로 삭제하기======");
        System.out.println("ArrayList = " + removeF(ary));
        System.out.println("LinkedList = " + removeF(lkd));

    }

    public static long addF(List list){
        long startTime =  System.nanoTime();
        for(int i = 0; i< 1000000; i++){
            list.add(i);
        }
        long end = System.nanoTime();

        return end - startTime;
    }

    public static long addM(List list) {
        long start = System.nanoTime();
        for(int i = 0; i < 10000; i++) {
            list.add(500,"X");
        }
        long end = System.nanoTime();
        return end - start;
    }

    public static long removeF(List list) {
        long start = System.nanoTime();
        for(int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }
        long end = System.nanoTime();
        return end - start;
    }

    public static long removeM(List list) {
        long start = System.nanoTime();
        for(int i = 0; i < 10000; i++) {
            list.remove(i);
        }
        long end = System.nanoTime();
        return end - start;
    }
}

코드를 직접 실행해본 결과 아래와 같은 속도로 결과가 나왔습니다.

이러한 결과로 나오는 이유는

ArrayList

배열과 같은 구조
각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에 해당 index의 데이터를 한번에 가져올 수 있다.
값을 추가하거나 삭제 할 땐, 특정값을 지우고 뒤의 값을 모두 한칸씩 떙겨오거나 특정값을 추가 하고 뒤의 값을 모두 한칸씩 미는 식으로 진행하기 때문에 추가/삭제에 있어서 매우 느리다.