[Algorithm/DataStructure] ArrayList와 LinkedList의 성능 비교 (feat. 왜 Queue는 LinkedList를 사용할까?)

pintegral·2023년 2월 14일

ArrayList List algorithm datastructure linkedlist queue

Algorithm/Data Structure

목록 보기

1/1

Why?

알고리즘 문제를 푸는 중 문득 Queue는 왜 ArrayList가 아닌 LinkedList로 생성을 할까 궁금해졌다. 'Queue는 FIFO이기 때문에 ArrayList 처럼 인덱스를 통한 접근이 필요없어서가 아닐까?'라고 생각은 해보았다. 그러나 이 index 존재 여부로 ArrayList와 LinkedList가 성능 면에서 정확히 차이를 보이는지 궁금해졌다.

ArrayList vs LinkedList

Structure 차이점

ArrayList
- index 존재
LinkedList
- 이전, 다음 노드의 데이터 주소값 존재
  - 각 포인터 변수의 주소도 따로 존재

Performance 차이점

index가 존재하는 ArrayList는 조회 시 평균적으로 좋은 성능을 보이지만, 삽입/삭제 시 인덱스 재배치를 통해 공간을 조절하기 때문에 비효율적인 성능을 보인다.

순차적으로 삽입/삭제하거나 조회하는 경우에는 ArrayList가 빠르지만, 중간 데이터(비 순차적)를 삽입/삭제하는 경우에는 LinkedList가 더 빠르다.

즉, FIFO(First In First Out)나 FILO(First In Last Out)처럼 삽입/삭제가 일정하게 앞이나 뒤에서 일어나는 경우를 제외하고는
삽입/삭제가 잦은 경우 LinkedList를, 조회가 잦은 경우 ArrayList를 이용하면 조금 더 효율적인 퍼포먼스를 낼 수 있을 것이다.

Time Complexity

	method	ArrayList	LinkedList
add at last index	add(value) (LinkedList -> add(value),addLast())	O(1)	O(1)
add at given index	add(index,value)	O(N)	O(1)
remove by index	remove(index) (LinkedList->remove(index),removeFirst())	O(N)	O(1)
remove by value	remove(value)	O(N)	O(1)
get by index	get(index)	O(1)	O(N)
search by value	contain(value), indexOf(value)	O(N)	O(N)

get(index)와 indexOf(value) 성능 테스트

참고한 블로그에 삽입/삭제 성능 테스트가 있었는데 흥미로웠다. 성능 차이가 얼마나 나는지 눈으로 정확한 수치를 확인하니 그랬던 것 같다.

그래서 조회 성능도 테스트해보았다.
랜덤 단어를 생성하여 각 List(LinkedList, ArrayList)에 추가한 뒤, get()과 indexOf()의 실행시간을 출력하여 비교해봤다.

Test Code


public class ListPerformanceTest {

    public static void main(String[] args){
        final int testDataSize = 5000;
        final int leftLimit = 97; // letter 'a'
        final int rightLimit = 122; // letter 'z'
        final int targetStringLength = 5;
        Random random = new Random();
        ArrayList arList = new ArrayList<>();
        LinkedList lkList = new LinkedList();

        for(int i=0; i<testDataSize; i++){
            String ran = random.ints(leftLimit,rightLimit + 1)
                    .filter(k -> (k <= 57 || k >= 65) && (k <= 90 || k >= 97))
                    .limit(targetStringLength)
                    .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                    .toString();

            arList.add(ran);
            lkList.add(ran);
        }

        System.out.println("=====search by value======");
        System.out.println("ArrayList = " + test_search_by_value(random,testDataSize, leftLimit, rightLimit, targetStringLength, arList));
        System.out.println("LinkedList = " + test_search_by_value(random,testDataSize, leftLimit, rightLimit, targetStringLength, lkList));

        System.out.println("\n=====get by index======");
        System.out.println("ArrayList = " + test_search_by_index(random,testDataSize, leftLimit, rightLimit, targetStringLength, arList));
        System.out.println("LinkedList = " + test_search_by_index(random,testDataSize, leftLimit, rightLimit, targetStringLength, lkList));
    }

    private static long test_search_by_value(Random random, int testDataSize, int leftLimit, int rightLimit, int targetStringLength, List list){
        long start = System.currentTimeMillis();
        for(int i = 0; i < testDataSize; i++) {
            String ran = random.ints(leftLimit,rightLimit + 1)
                    .filter(k -> (k <= 57 || k >= 65) && (k <= 90 || k >= 97))
                    .limit(targetStringLength)
                    .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                    .toString();

            list.indexOf(ran);
        }
        long end = System.currentTimeMillis();

        return end - start;
    }
    
    private static long test_search_by_index(Random random, int testDataSize, int leftLimit, int rightLimit, int targetStringLength, List list){
        long start = System.currentTimeMillis();
        for(int i = 0; i < testDataSize; i++) {
            int ran = random.nextInt(testDataSize);

            list.get(ran);
        }
        long end = System.currentTimeMillis();

        return end - start;
    }
}