List - 자바 리스트의 성능 비교

package collection.list;

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

public class JavaListPerformanceTest {
    public static void main(String[] args) {
        int size = 50_000;
        System.out.println("ArrayList 추가==");
        addFirst(new ArrayList<>(),size);
        addMid(new ArrayList<>(),size); // 찾는데O(1), 데이터 추가O(밀기)(n)
        ArrayList<Integer> arrayList = new ArrayList<>(); //조회용 데이터로 사용
        addLast(arrayList,size); // 찾는데O(1), 데이터 추가O(밀기)(1)


        int loop = 10000;
        System.out.println("==ArrayList 조회==");
        getIndex(arrayList,loop,0);
        getIndex(arrayList,loop,size/2);
        getIndex(arrayList,loop,size-1);

        System.out.println("==ArrayList 검색==");
        search(arrayList,loop,0);
        search(arrayList,loop,size/2);
        search(arrayList,loop,size-1);


        System.out.println("LinkedList 추가==");
        addFirst(new LinkedList<>(),size);
        addMid(new LinkedList<>(),size); // 찾는데O(n), 데이터 추가O(1)
        LinkedList<Integer> linkedList = new LinkedList<>(); //조회용 데이터로 사용
        addLast(linkedList,size); // 찾는데O(n), 데이터 추가O(1)
        

        System.out.println("==MyLinkedList 조회==");
        getIndex(linkedList,loop,0);
        getIndex(linkedList,loop,size/2);
        getIndex(linkedList,loop,size-1);

        System.out.println("==MyLinkedList 검색==");
        search(linkedList,loop,0);
        search(linkedList,loop,size/2);
        search(linkedList,loop,size-1);

    }

    private static void addFirst(List<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0,i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }
    private static void addMid(List<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i/2,i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("평균 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }
    private static void addLast(List<Integer> list, int size){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기 : " + size + " 계산시간 :" + (endTime-startTime)+"ms");
    }

    private static void getIndex(List<Integer> list, int loop, int index){
        long startTime = System.currentTimeMillis();

        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("index : " + index + " 반복 : " + loop + " 계산 시간 : " + (endTime-startTime)+"ms");
    }
    private static void search(List<Integer> list, int loop, int findValue){
        long startTime = System.currentTimeMillis();

        for (int i = 0; i < loop; i++) {
            list.get(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue : " + findValue + " 반복 : " + loop + " 계산 시간 : " + (endTime-startTime)+"ms");
    }
}

 

추가, 삭제

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 실제 데이터의 추가는 간단한 참조 변경으로 O(1)로 빠르게 수행된다.

앞에 추가(삭제)

• 배열 리스트 : 추가나 삭제할 위치를 찾는데 O(1), 데이터를 한칸씩 이동 O(n) -> O(n)
• 연결 리스트 : 추가나 삭제할 위치를 찾는데 O(1), 노드를 변경하는데 O(1) -> O(1)

평균 추가(삭제)

• 배열 리스트 : 추가나 삭제할 위치를 찾는데 O(1), 인덱스 이후의 데이터를 한칸씩 이동 O(n/2) -> O(n)
• 연결 리스트 : 추가나 삭제할 위치는 찾는데 O(n/2), 노드를 변경하는데 O(1) -> O(n)

뒤에 추가(삭제)

• 배열 리스트 : 추가나 삭제할 위치는 찾는데 O(1), 이동할 데이터 없음 ->O(1)
• 연결 리스트 : 추가나 삭제할 위치는 찾는데 O(1), 노드를 변경하는데 O(1) -> O(1)
  • 참고로 자바가 제공하는 연결리스트(LinkedList)는 마지막 위치를 가지고 있다.

인덱스 조회

• 배열 리스트 : 배열에 인덱스를 사용해서 값을 O(1)로 찾을 수 있음
• 연결 리스트 : 노드를 인덱스 수 만큼 이동해야함 O(n)

검색

• 배열 리스트 : 데이터를 찾을 때 까지 배열을 순회 O(n)
• 연결 리스트 : 데이터를 찾을 때 까지 노드를 순회 O(n)

데이터를 추가할 때 자바 ArrayList가 직접 구현한MyArrayList보다 빠른 이유

• 자바의 배열 리스트는 이때 메모리 고속 복사를 사용하기 때문에 성능이 최적화 된다.
• 메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략 O(n/10) 정도로 추정하자.        상수를 제거하면 O(n)이 된다. 하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.

시간 복잡도와 실제 성능

• 이론적으로 LinkedList의 중간 삽입 연산은 ArrayList보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도,   메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
  • 추가로 ArrayList는 데이터를 한 칸씩 직접 이동하지 않고, 대신에 메모리 고속 복사를 사용한다.
• ArrayList는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
• 반면, LinkedList 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다.
• ArrayList의 경우 CAPACITY를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다, 하지만 한번에 50%씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 크게 영향을 주지는 않는다.

정리하면 이론적으로 LinkedList가 중간 삽입에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

 

배열 리스트 vs 연결 리스트

대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주료 배열 리스트를 기본으로 사용한다.

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.