ArrayList vs LinkedList (자바 데이터 타입)

00 개요

• Java에서 데이터를 다룰 때 자주 사용되는 2가지 대표적인 리스트 자료구조로 LinkedLst 및 ArrayList가 있음
• 모두 List 인터페이스를 구현하고 있으나 내부적인 동작 방식 및 성능에 차이가 있음
• LinkedList 및 ArrayList의 정의, 차이점, 사용 사례에 관한 정리

01 ArrayList란

1. 정의

• 내부적으로 배열을 사용하여 데이터를 저장하는 동적 리스트
• 배열은 고정된 크기를 가지며, 그 크기를 초과하는 데이터를 추가하려면 새로운 배열을 생성하고, 기존 데이터를 복사해야 함
• 배열을 기반으로 하기에 인덱스를 통한 빠른 데이터 접근이 가능, 읽기 작업에서 뛰어난 성능 발휘

2. 장단점

• 장점: 인덱스를 통한 빠른 데이터 조회
• 단점: 중간에 데이터를 삽입하거나 삭제하는 경우 배열의 데이터를 이동시켜야 하므로 성능이 저하됨

02 LinkedList란

1. 정의

• 각 데이터가 노드(Node)로 구성된 양방향 연결 리스트
• 각 노드는 자신의 데이터와 다음, 이전 노드에 대한 참조를 가지고 있어, 데이터가 서로 연결된 형태로 저장됨
• 즉, 한쪽 끝에서 다른 끝으로 탐색 가능
• 동적 크기 조정이 용이하고, 중간에 데이터를 삽입하거나 삭제할 때 노드의 참조만 변경하면 되기에 성능이 우수

2. 장단점

• 장점: 리스트의 중간에 데이터를 삽입하거나 삭제할 때 빠름
• 단점: 인덱스를 통한 접근이 비효율적이며, 순차적으로 노드를 탐색해야 함 

03 ArrayList와 LinkedList의 주요 차이점

특성	ArrayList	LinkedList
저장 구조	내부적으로 배열 사용	노드 기반 연결 리스트 사용
데이터 접근 속도	인덱스를 통해 빠른 접근 (O(1))	순차적으로 탐색 (O(n))
삽입/삭제 속도	중간 삽입/삭제 시 느림 (O(n))	중간 삽입/삭제 시 빠름 (O(1))
메모리 사용	고정 크기 배열을 계속 확장해야 하므로 메모리 낭비 발생 가능	노드마다 메모리를 사용하므로 데이터가 적을 때는 비효율적
순차적인 처리	읽기 작업에서 성능 우수	삽입/삭제가 빈번한 경우 유리

1) 언제 LinkedList가 유용한가?

• 데이터 삽입/삭제가 빈번한 경우: 리스트 중간에서 데이터를 추가하거나 삭제하는 작업이 많은 경우 
• 순차적인 접근만 필요한 경우: 인덱스를 통한 랜덤 접근이 거의 필요 없고, 순차적으로 데이터를 처리하거나, 삽입/삭제가 리스트의 양 끝에서 자주 일어나는 경우
• 데이터의 크기가 자주 변하는 경우: LinkedList는 동적으로 크기를 조절하며, 크기를 조정하는 데 비용이 들지 않음 

2) 언제 ArrayList가 유용한가?

• 읽기 작업이 많은 경우: 데이터를 자주 검색하거나 인덱스를 통해 접근 (i.e., 랜덤 접근)해야 한다면 ArrayList의 빠른 접근 속도가 더 효율적
• 데이터의 크기가 비교적 안정적인 경우: 크기가 빈번하게 변하지 않는 경우, ArrayList는 더 적은 메모리를 사용하며 효율적

3) 실험

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

public class checkRandomSequentialAccess {
    public static void main(String[] args) {
        // ArrayList 및 LinkedList 선언
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 1만 개의 데이터 삽입
        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // 실행
        RandomAccess(arrayList, linkedList);
        System.out.println("-".repeat(30));
        SequentialAccess(arrayList, linkedList);
        System.out.println("끝!");
    }
    public static void RandomAccess (List<Integer> arrayList, List<Integer> linkedList) {
        // 랜덤 접근 예시: 인덱스를 통해 특정 위치의 데이터를 가져오는 경우
        long startTime_array = System.nanoTime();
        for (int i = 0; i < arrayList.size(); i ++) {
            arrayList.get(i); // ArrayList는 빠름
        }
        long endTime_array = System.nanoTime();
        long timeSpan_array = (endTime_array - startTime_array);
        String sentence = "ArrayList 랜덤 접근 시간:";
        System.out.printf("%-20s %12d ns%n", sentence, timeSpan_array);  // sentence를 20크기 안에서 왼쪽(-) 정렬

        long startTime_linked = System.nanoTime();
        for (int i = 0; i < linkedList.size(); i ++) {
            linkedList.get(i); // LinkedList는 느림
        }
        long endTime_linked = System.nanoTime();
        long timeSpan_linked = (endTime_linked - startTime_linked);
        sentence = "LinkedList 랜덤 접근 시간:";
        System.out.printf("%-20s %12d ns%n", sentence, timeSpan_linked);
        System.out.printf("ArrayList는 LinkedList보다 %d배 더 빠릅니다.%n", (timeSpan_linked / timeSpan_array));
    }
    public static void SequentialAccess (List<Integer> arrayList, List<Integer> linkedList) {
        // 순차 접근 예시: 리스트의 처음부터 끝까지의 데이터를 하나씩 가져오는 경우
        long startTime_array = System.nanoTime();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList.get(i); // ArrayList 순차 접근
        }
        long endTime_array = System.nanoTime();
        long timeSpan_array = (endTime_array - startTime_array);
        String sentence = "ArrayList 순차 접근 시간:";
        System.out.printf("%-20s %12d ns%n", sentence, timeSpan_array);

        long startTime_linked = System.nanoTime();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i); // LinkedList 순차 접근
        }
        long endTime_linked = System.nanoTime();
        long timeSpan_linked = (endTime_linked - startTime_linked);
        sentence = "LinkedList 순차 접근 시간:";
        System.out.printf("%-20s %12d ns%n", sentence, timeSpan_linked);
        System.out.printf("ArrayList는 LinkedList보다 %d배 더 빠릅니다.%n", (timeSpan_linked / timeSpan_array));
    }
}

• 실행 결과:

ArrayList 랜덤 접근 시간:       1037700 ns
LinkedList 랜덤 접근 시간:     42462400 ns
ArrayList는 LinkedList보다 40배 더 빠릅니다.
------------------------------
ArrayList 순차 접근 시간:        562800 ns
LinkedList 순차 접근 시간:     37607100 ns
ArrayList는 LinkedList보다 66배 더 빠릅니다.
끝!

Process finished with exit code 0

• Note:
  • 랜덤 접근 시간: ArrayList가 LinkedList보다 30~60배 정도 더 빠름
  • 순차 접근 시간: ArrayList가 LinkedList보다 60~70배 정도 더 빠름