자바 중급 2편 - List(3)

자바 리스트(컬렉션 프레임워크)

List란?

• 순서 보장, 중복 허용 컬렉션. 자바 컬렉션 프레임워크에서 대표적인 선형 자료구조다. 컬렉션 계층 구조상 Collection 하위에 List가 있고, 구현체로 ArrayList, LinkedList 등이 있다.

List 인터페이스 핵심 메서드

• 삽입/수정/조회/삭제 전형 메서드: add(e), add(index,e), get(index), set(index,e), remove(index), indexOf(o), lastIndexOf(o), contains(o), size(), isEmpty(), iterator(), toArray() 등.

 

ArrayList vs LinkedList — 내부 동작과 특징

ArrayList (배열 기반)

• 내부는 동적 배열. 기본 용량은 10이며, 넘치면 약 50%씩 용량을 늘리며 확장한다. (예: 10→15→22→33→49 … 최적화는 JDK 버전에 따라 다를 수 있음)
• 중간 삽입/삭제 시 뒤 요소들을 한 번에 메모리 고속 복사(System.arraycopy)로 이동하여 최적화한다.
• 요약: 인덱스 접근 O(1), 끝에 추가 O(1)(아모티제이션), 중간 삽입/삭제 O(n).

LinkedList (이중 연결 리스트)

• 이중 연결 리스트로 first, last를 모두 가진다. 양방향 이동(prev, next) 가능. 마지막 노드 참조가 있어 끝에 추가도 O(1) 가능. 인덱스 접근은 노드를 순회해야 한다.
• 인덱스가 앞쪽이면 머리에서, 뒤쪽이면 꼬리에서 역방향으로 탐색해 조회 경로를 최적화한다.

package com.example.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 = 1_000_000;

        System.out.println("== ArrayList 추가 ==");

        addFirst(new ArrayList<>(), size);
        addMid(new ArrayList<>(), size); // 데이터 찾는데 O(1), 데이터 추가(밀기) O(n)
        List<Integer> list = new ArrayList<>(size);


        addLast(list, size); // 찾는데 O(1), 데이터 추가 O(1)


        int loop = 10000;

        System.out.println("== ArrayList 조회 ==");

        getIndex(list, loop, 0); // 앞 조회
        getIndex(list, loop, size / 2); //중간 조회
        getIndex(list, loop, size - 1); // 마지막 조회

        System.out.println("== ArrayList 검색 ==");

        search(list, loop, 0); // 앞 조회
        search(list, loop, size / 2); //중간 조회
        search(list, loop, size - 1); // 마지막 조회


        System.out.println("== LinkedList 추가 ==");

        addFirst(new LinkedList<>(), size);
        addMid(new LinkedList<>(), size); // 찾는데 O(n), 데이터 추가 O(1)

        List<Integer> list1 = new LinkedList<>();
        addLast(list1, size); // 찾는데 O(n), 데이터 추가 O(1)


        System.out.println("== LinkedList 조회 ==");

        getIndex(list1, loop, 0); // 앞 조회
        getIndex(list1, loop, size / 2); //중간 조회
        getIndex(list1, loop, size - 1); // 마지막 조회

        System.out.println("== LinkedList 검색 ==");

        search(list1, loop, 0); // 앞 조회
        search(list1, loop, size / 2); //중간 조회
        search(list1, 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.indexOf(findValue);

        }

        long endTime = System.currentTimeMillis();

        System.out.println("findValue : " + findValue +", 반복 : " + loop + ", 계산시간 : " + (endTime - startTime) + "ms");

    }
}

 

ArrayList vs LinkedList 비교표

구분	ArrayList	LinkedList
내부 구조	동적 배열 기반	이중 연결 리스트 기반 (prev, next 참조)
메모리 구조	연속된 메모리 블록	노드 단위로 분산 저장
인덱스 접근	O(1) – 인덱스로 바로 접근 가능	O(n) – 앞/뒤에서 순차 탐색 필요
끝에 추가(addLast)	O(1) (아모티제이션)	O(1)
앞에 추가(addFirst)	O(n) – 전체 요소 이동 필요	O(1) – head 변경만
중간 삽입	O(n) – 요소 이동	O(n) – 위치 탐색 후 링크 변경
삭제(앞/중간)	O(n) – 요소 이동	O(n) – 위치 탐색 후 링크 변경
삭제(끝)	O(1)	O(1)
장점	랜덤 접근 빠름, CPU 캐시 친화적, 메모리 사용 효율 높음	앞·뒤 삽입/삭제 빠름, 요소 이동 없음
단점	앞·중간 삽입/삭제 성능 저하, 확장 시 배열 복사 비용	인덱스 접근 느림, 포인터 저장으로 메모리 사용량 많음
적합한 상황	조회/검색이 많고, 주로 끝에 추가하는 경우	앞부분 삽입·삭제가 잦은 경우, 큐/데크 구현

 

📌정리

 

• 대부분의 CRUD·조회 중심 서비스에서는 ArrayList가 기본값이 된다. CPU 캐시 친화적이고 랜덤 접근이 빠르다.
• 리스트의 앞부분에 매우 자주 삽입/삭제가 필요할 때만 LinkedList를 고려한다. (끝 추가는 둘 다 O(1) 가능)
• “중간 삽입은 LinkedList가 이론상 유리”하지만, 현대 머신의 메모리/캐시/할당 비용을 감안하면 실제는 ArrayList가 더 빠른 경우가 많다.