[JAVA] List에 인터페이스에 대하여 (2)

지난 글에서는 MyArrayList와 MyLinkedList를 직접 구현해보았다. 단순히 구현해보는 것만으로는 부족하다. 실제로 얼마나 성능 차이가 나는지, 자바는 왜 더 빠른지, 구조가 어떻게 다른지까지 알아야 진짜 실력을 키울 수 있다. 이번 글에서는 직접 구현한 리스트와 자바의 ArrayList, LinkedList를 비교 실험을 통해 차이점과 이유까지 하나하나 풀어본다.

 

1. 자바의 List는 인터페이스이다

먼저 개념부터 잡고 가자.

자바에서 List는 인터페이스(interface) 이다. 즉, 기능의 틀만 정해놓고, 실제 구현은 하지 않은 것이다. List는 순서가 있는 데이터를 저장하고 중복을 허용하는 자료 구조이며, 대표적인 구현체는 아래와 같다:

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

 

2. 실험: 직접 구현한 리스트 vs 자바 내장 리스트 성능 비교

실험 코드:

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;
        int loop = 10_000;

        // ===== ArrayList 성능 테스트 =====
        System.out.println("== ArrayList 추가 ==");
        addFirst(new ArrayList<>(), size);
        addMid(new ArrayList<>(), size);
        List<Integer> arrayList = new ArrayList<>();
        addLast(arrayList, size);

        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);

        // ===== LinkedList 성능 테스트 =====
        System.out.println("== LinkedList 추가 ==");
        addFirst(new LinkedList<>(), size);
        addMid(new LinkedList<>(), size);
        List<Integer> linkedList = new LinkedList<>();
        addLast(linkedList, size);

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

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

    private static void addFirst(List<Integer> list, int size) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
        long end = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기: " + size + ", 시간: " + (end - start) + "ms");
    }

    private static void addMid(List<Integer> list, int size) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i / 2, i);
        }
        long end = System.currentTimeMillis();
        System.out.println("중간 추가 - 크기: " + size + ", 시간: " + (end - start) + "ms");
    }

    private static void addLast(List<Integer> list, int size) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("뒤에 추가 - 크기: " + size + ", 시간: " + (end - start) + "ms");
    }

    private static void getIndex(List<Integer> list, int loop, int index) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long end = System.currentTimeMillis();
        System.out.println("조회 - index: " + index + ", 반복: " + loop + ", 시간: " + (end - start) + "ms");
    }

    private static void search(List<Integer> list, int loop, int value) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(value);
        }
        long end = System.currentTimeMillis();
        System.out.println("검색 - 값: " + value + ", 반복: " + loop + ", 시간: " + (end - start) + "ms");
    }
}

 

비교 결과:

[ArrayList] 빠른 이유 1: 메모리 고속 복사 사용

직접 구현한 MyArrayList는 배열을 직접 하나하나 복사한다. 예를 들어 중간에 값을 추가할 때 for문으로 뒤 요소들을 하나씩 밀어낸다.

for (int i = size - 1; i >= index; i--) {
    array[i + 1] = array[i]; // 한 칸씩 이동
}

 

하지만 자바의 ArrayList는 System.arraycopy() 를 사용한다. 이 메서드는 하드웨어 수준에서 메모리를 복사하는 고속 복사 명령으로, 일반적인 반복문보다 수십 배 이상 빠르다.

System.arraycopy(elementData, index, elementData, index + 1, size - index);

 

즉, ArrayList는 배열을 '하나하나 이동'하는 게 아니라, '한 번에 덩어리로 복사'하는 방식으로 동작하기 때문에 훨씬 빠르다.

 

 

[LinkedList] 빠른 이유 2: 마지막 노드(last)를 참조하고 있기 때문

 

직접 구현한 MyLinkedList는 단순 단일 연결 리스트이기 때문에, 뒤에 값을 추가하려면 맨 끝까지 쭉 따라가야 한다. (O(n))

하지만 자바의 LinkedList는 이중 연결 리스트이고, first와 last 노드를 동시에 저장한다. 따라서 addLast()는 last 노드에 바로 연결만 해주면 되므로 O(1)에 가까운 속도를 낼 수 있다.

또한 자바 LinkedList는 다음과 같은 최적화도 한다:

• 인덱스가 절반보다 작으면 앞에서부터, 크면 뒤에서부터 역방향으로 찾아간다.
• 즉, 단순 O(n)이 아니라 평균적으로 조회 범위를 반으로 줄여 조회 속도를 개선한다.

 

3. 언제 ArrayList를 쓰고 언제 LinkedList를 써야 할까?

리스트는 상황에 따라 다르게 써야 성능이 제대로 나온다. 각각 어떤 상황에서 어떤 리스트를 쓰는 게 좋은지 아래와 같이 정리해보자.

 

1)대부분의 경우에는 ArrayList가 정답이다

ArrayList는 데이터를 배열처럼 연속된 메모리에 저장하기 때문에 인덱스로 바로 접근하는 조회 속도가 매우 빠르다(O(1)). 또한, 데이터를 뒤에 추가할 때도 배열 끝에만 값을 넣으면 되기 때문에 역시 매우 빠르다.

 

게다가 메모리가 연속되어 있어 CPU 캐시에도 잘 맞고, 자바 내부적으로는 System.arraycopy()라는 고속 복사 기능을 써서 데이터 이동도 빠르게 처리한다. 그래서 일반적인 상황에서는 대부분 ArrayList를 쓰는 것이 성능 면에서 유리하다.

 

 

2)앞쪽에 자주 데이터를 넣거나 뺄 일이 많다면 LinkedList

앞에 데이터를 자주 추가하거나 삭제하는 경우에는 LinkedList가 더 적합하다.

 

왜냐하면 LinkedList는 노드(데이터와 다음 노드 주소)를 연결해서 데이터를 저장하기 때문에, 앞에 무언가를 추가할 때는 그 앞쪽 노드만 참조 연결을 바꾸면 된다(O(1)). 반면 ArrayList는 데이터를 앞에 넣으려면 뒤에 있는 모든 요소를 한 칸씩 밀어야 하므로 느리다(O(n)).

 

단, 주의할 점은 앞에 추가할 때만 그렇다는 것이다. 중간이나 뒤에 추가하는 경우는 오히려 LinkedList가 더 느릴 수 있다.

 

 

3)중간에 삽입을 자주 해야 하는 경우는?

이론적으로는 LinkedList가 더 유리하다. 삽입 위치까지 찾아가는 데 시간이 걸리지만, 실제 삽입은 참조만 바꾸면 되기 때문이다.

 

하지만 실제 성능을 측정해보면 ArrayList가 오히려 더 빠를 때가 많다. 그 이유는 자바가 배열 복사를 고속으로 처리할 수 있도록 최적화되어 있기 때문이다. 반면 LinkedList는 메모리에 데이터가 따로따로 흩어져 있어서, CPU 캐시 효율도 떨어지고 접근 속도도 느리다.

 

결국 실제로 중간 삽입을 자주 해야 할 일이 있어도, 성능 측정을 해보고 결정하는 것이 좋다. 대부분은 ArrayList가 더 빠를 수 있다.

 

 

4)순서대로 조회하거나 정렬, 검색 중심의 작업이라면 ArrayList

데이터를 순차적으로 처리하거나, 정렬하거나, 검색하는 작업이 많다면 ArrayList가 훨씬 더 적합하다.

 

그 이유는 배열이 연속된 메모리 공간에 저장되므로 CPU가 데이터를 훨씬 빠르게 읽을 수 있고, 정렬도 더 빠르게 처리할 수 있다.

 

또한 ArrayList는 인덱스 기반 조회가 가능하기 때문에, 반복문을 통해 빠르게 원하는 요소를 가져올 수 있다.

 

 

4 자바 List가 제공하는 주요 기능들

자바의 List 인터페이스는 단순히 데이터를 저장하는 것 외에도 다양한 편의 기능들을 제공한다. 대표적으로 아래와 같은 기능들이 있다:

• add(E e) – 리스트의 끝에 요소를 추가
• add(int index, E element) – 지정된 위치에 요소를 삽입
• addAll(Collection<? extends E> c) – 다른 컬렉션의 모든 요소를 끝에 추가
• addAll(int index, Collection<? extends E> c) – 다른 컬렉션의 요소들을 중간에 삽입
• get(int index) – 특정 인덱스의 요소를 조회
• set(int index, E element) – 특정 위치의 요소를 다른 값으로 교체
• remove(int index) – 해당 인덱스의 요소를 삭제
• remove(Object o) – 값이 일치하는 첫 번째 요소를 삭제
• clear() – 모든 요소를 삭제
• indexOf(Object o) – 특정 값이 처음 등장하는 인덱스를 반환
• lastIndexOf(Object o) – 특정 값이 마지막으로 등장하는 인덱스를 반환
• contains(Object o) – 특정 값이 리스트에 포함되어 있는지 확인
• size() – 리스트에 저장된 요소의 수를 반환
• isEmpty() – 리스트가 비어 있는지 확인
• iterator() – 리스트 요소에 대해 순차적으로 접근할 수 있는 반복자 반환
• toArray() – 리스트의 모든 요소를 배열로 변환
• toArray(T[] a) – 리스트의 요소를 지정된 배열에 복사
• sort(Comparator<? super E> c) – 지정된 기준으로 요소 정렬
• subList(int fromIndex, int toIndex) – 리스트의 일부분(뷰)을 반환

이러한 기능들은 List를 단순한 데이터 저장 공간을 넘어, 다양한 형태로 데이터를 가공하고 관리할 수 있는 구조로 만들어준다.

 

마무리하며

직접 List를 구현해보면 배열과 연결 리스트가 어떻게 작동하는지, 어떤 상황에서 더 적절한지를 몸으로 체감할 수 있다. 하지만 실무에서는 자바가 제공하는 기본 구현체인 ArrayList와 LinkedList를 사용하는 것이 훨씬 효율적이다. 자바는 내부적으로 System.arraycopy() 같은 고속 복사, 이중 연결 리스트 구조, 메모리 최적화와 같은 다양한 기술을 통해 성능을 극대화하고 있기 때문이다.

 

따라서 특별한 이유가 없다면 ArrayList를 기본으로 사용하고, 앞쪽 삽입이나 삭제가 빈번한 경우에만 LinkedList를 고려하는 것이 가장 현실적이고 효율적인 선택이다. 자료구조는 이론도 중요하지만, 실제 성능과 용도에 맞는 현명한 선택이 핵심이다.

 

감사합니다.