11.2 List: ArrayList와 LinkedList

가장 많이 쓰이는 컬렉션인 List 계열을 자세히 살펴봅니다. List는 배열처럼 데이터를 순서대로 저장하되, 크기가 동적으로 변하는 스마트 배열 이라고 생각하면 됩니다.

1. List 인터페이스 특징

List<E> 인터페이스의 두 가지 핵심 특징:

• 순서(Order) 있음: 요소가 추가된 순서대로 인덱스(0, 1, 2...)가 부여됩니다.
• 중복(Duplicate) 허용: 같은 값을 여러 번 저장할 수 있습니다.

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

List<String> list = new ArrayList<>();
list.add("사과");
list.add("바나나");
list.add("사과"); // 중복 허용
System.out.println(list);        // [사과, 바나나, 사과]
System.out.println(list.get(0)); // 사과 (인덱스 0)
System.out.println(list.get(2)); // 사과 (인덱스 2)

2. ArrayList

ArrayList는 내부적으로 배열(Array)을 기반 으로 만들어졌습니다. 요소를 추가하면 내부 배열이 꽉 찼을 때 더 큰 배열로 자동으로 확장됩니다. 순서(인덱스)로 데이터를 빠르게 조회 하는 상황에 최적화되어 있습니다.

내부 동작 원리 (capacity)

import java.util.ArrayList;

public class ArrayListCapacity {
    public static void main(String[] args) {
        // 기본 생성: 내부 배열 초기 용량(capacity) = 10
        ArrayList<String> list1 = new ArrayList<>();

        // 용량 힌트 제공: 처음부터 100개를 담을 공간 확보
        // 많은 데이터를 미리 알고 있다면 초기 용량 지정으로 성능 향상
        ArrayList<String> list2 = new ArrayList<>(100);

        // 용량이 초과되면 자동으로 1.5배로 확장
        // 10 → 15 → 22 → 33 → ... (내부적으로 Arrays.copyOf 사용)
        for (int i = 0; i < 20; i++) {
            list1.add("item" + i);
        }
        System.out.println("크기: " + list1.size()); // 20
    }
}

초기 용량 설정

삽입할 데이터의 양을 미리 알고 있다면 new ArrayList<>(예상개수)로 초기 용량을 지정하세요. 불필요한 배열 복사를 줄여 성능이 향상됩니다.

주요 메서드 완전 정리

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArrayListMethods {
    public static void main(String[] args) {
        ArrayList<String> fruits = new ArrayList<>();

        // ========== 추가 ==========
        fruits.add("사과");           // 맨 끝에 추가
        fruits.add("바나나");
        fruits.add("딸기");
        fruits.add(1, "포도");        // 인덱스 1에 삽입 (기존 요소 뒤로 밀림)
        System.out.println("추가 후: " + fruits); // [사과, 포도, 바나나, 딸기]

        // addAll: 다른 컬렉션의 모든 요소 추가
        List<String> more = List.of("키위", "망고");
        fruits.addAll(more);
        System.out.println("addAll 후: " + fruits); // [사과, 포도, 바나나, 딸기, 키위, 망고]

        // ========== 조회 ==========
        System.out.println("get(0): " + fruits.get(0));          // 사과
        System.out.println("size(): " + fruits.size());           // 6
        System.out.println("isEmpty(): " + fruits.isEmpty());     // false
        System.out.println("contains(딸기): " + fruits.contains("딸기")); // true
        System.out.println("indexOf(바나나): " + fruits.indexOf("바나나")); // 2
        System.out.println("lastIndexOf(사과): " + fruits.lastIndexOf("사과")); // 0

        // ========== 수정 ==========
        fruits.set(0, "자두");        // 인덱스 0의 요소를 "자두"로 교체
        System.out.println("set 후: " + fruits); // [자두, 포도, 바나나, 딸기, 키위, 망고]

        // ========== 삭제 ==========
        fruits.remove(0);             // 인덱스 0 요소 삭제
        System.out.println("인덱스 삭제 후: " + fruits); // [포도, 바나나, 딸기, 키위, 망고]

        fruits.remove("키위");        // 값으로 삭제 (첫 번째로 일치하는 것 삭제)
        System.out.println("값 삭제 후: " + fruits); // [포도, 바나나, 딸기, 망고]

        fruits.removeIf(f -> f.length() > 2); // 조건에 맞는 요소 삭제 (람다)
        System.out.println("조건 삭제 후: " + fruits); // [포도, 망고] (글자수 2 이하만 남음)

        // ========== 부분 리스트 ==========
        ArrayList<Integer> numbers = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
        List<Integer> sub = numbers.subList(2, 5); // 인덱스 2~4 (5 미포함)
        System.out.println("subList(2,5): " + sub); // [2, 3, 4]

        // ========== 정렬 ==========
        ArrayList<String> names = new ArrayList<>(List.of("Charlie", "Alice", "Bob"));
        Collections.sort(names);    // 오름차순 정렬
        System.out.println("정렬: " + names); // [Alice, Bob, Charlie]

        names.sort((a, b) -> b.compareTo(a)); // 내림차순 정렬
        System.out.println("역순: " + names); // [Charlie, Bob, Alice]

        // ========== 변환 ==========
        String[] arr = names.toArray(new String[0]); // 배열로 변환
        System.out.println("배열 변환: " + java.util.Arrays.toString(arr));

        // ========== 초기화 ==========
        fruits.clear();
        System.out.println("clear 후 isEmpty: " + fruits.isEmpty()); // true
    }
}

3. LinkedList

LinkedList는 내부적으로 각 데이터가 자신의 앞뒤 데이터의 주소를 기억하는 이중 연결 리스트(Doubly Linked List) 구조로 되어있습니다. 또한 Deque 인터페이스도 구현하므로 Queue와 Stack 역할도 동시에 수행합니다.

이중 연결 리스트 구조

[head]                                    [tail]
  ↓                                          ↓
[prev=null | "사과" | next=●] ←→ [prev=● | "바나나" | next=●] ←→ [prev=● | "딸기" | next=null]

각 노드(Node)가 이전 노드와 다음 노드의 참조를 모두 가지고 있습니다.

LinkedList 주요 메서드

import java.util.LinkedList;

public class LinkedListMethods {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 기본 List 메서드
        list.add("중간1");
        list.add("중간2");
        System.out.println("기본: " + list); // [중간1, 중간2]

        // 앞에 추가 (Deque 기능)
        list.addFirst("맨 앞");
        list.offerFirst("더 앞"); // 동일 기능

        // 뒤에 추가 (Deque 기능)
        list.addLast("맨 뒤");
        list.offerLast("더 뒤"); // 동일 기능

        System.out.println("전체: " + list); // [더 앞, 맨 앞, 중간1, 중간2, 맨 뒤, 더 뒤]

        // 앞에서 조회 (삭제 없이)
        System.out.println("peekFirst: " + list.peekFirst()); // 더 앞

        // 앞에서 꺼내기 (삭제)
        System.out.println("pollFirst: " + list.pollFirst()); // 더 앞
        System.out.println("removeFirst: " + list.removeFirst()); // 맨 앞

        // 뒤에서 꺼내기 (삭제)
        System.out.println("pollLast: " + list.pollLast()); // 더 뒤

        System.out.println("남은 목록: " + list); // [중간1, 중간2, 맨 뒤]
    }
}

LinkedList를 Queue로 사용

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // LinkedList를 Queue 인터페이스로 참조
        Queue<String> queue = new LinkedList<>();

        // enqueue: 뒤에 추가
        queue.offer("첫 번째 손님");
        queue.offer("두 번째 손님");
        queue.offer("세 번째 손님");
        System.out.println("대기열: " + queue);

        // peek: 앞의 요소 확인 (삭제 안 함)
        System.out.println("다음 손님: " + queue.peek()); // 첫 번째 손님

        // dequeue: 앞에서 꺼내기 (FIFO)
        System.out.println("서비스: " + queue.poll()); // 첫 번째 손님
        System.out.println("서비스: " + queue.poll()); // 두 번째 손님
        System.out.println("남은 대기열: " + queue);   // [세 번째 손님]
    }
}

LinkedList를 Stack으로 사용

import java.util.LinkedList;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        // Deque를 Stack(후입선출, LIFO)으로 사용
        Deque<String> stack = new LinkedList<>();

        // push: 스택에 쌓기
        stack.push("1층");
        stack.push("2층");
        stack.push("3층");
        System.out.println("스택: " + stack); // [3층, 2층, 1층]

        // pop: 가장 마지막에 쌓은 것부터 꺼냄
        System.out.println("꺼냄: " + stack.pop()); // 3층
        System.out.println("꺼냄: " + stack.pop()); // 2층
        System.out.println("남은 스택: " + stack);  // [1층]
    }
}

4. ArrayList vs LinkedList 비교표

작업	ArrayList	LinkedList	설명
인덱스 조회 get(i)	O(1)	O(n)	ArrayList는 배열이라 바로 접근
맨 끝 추가 add(e)	O(1)(평균)	O(1)	둘 다 빠름
중간 삽입 add(i,e)	O(n)	O(1)	LinkedList는 참조만 변경
중간 삭제 remove(i)	O(n)	O(1)	LinkedList는 참조만 변경
메모리 사용	적음	많음	LinkedList는 노드마다 참조 2개
Queue/Stack 사용	부적합	적합	LinkedList는 Deque 구현

언제 무엇을 쓸까?

• ArrayList(기본 선택): 대부분의 상황, 인덱스 조회가 많을 때, 끝에 추가/삭제할 때
• LinkedList: 앞/중간에 잦은 삽입·삭제가 있을 때, Queue나 Stack 구조가 필요할 때

실무에서는 ArrayList가 기본 선택 입니다. LinkedList는 노드마다 객체를 생성해야 해서 메모리 오버헤드가 크고, 캐시 지역성도 나쁩니다.

5. List.of()와 List.copyOf() (Java 9+)

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

public class ImmutableList {
    public static void main(String[] args) {
        // List.of(): 불변 리스트 생성 (null 불허)
        List<String> immutable = List.of("Alice", "Bob", "Charlie");
        System.out.println(immutable); // [Alice, Bob, Charlie]
        // immutable.add("Dave"); // UnsupportedOperationException!
        // immutable.set(0, "X"); // UnsupportedOperationException!

        // List.copyOf(): 기존 컬렉션을 불변 리스트로 복사
        ArrayList<String> original = new ArrayList<>();
        original.add("가");
        original.add("나");
        original.add("다");
        List<String> copy = List.copyOf(original);
        System.out.println(copy); // [가, 나, 다]

        // original을 변경해도 copy에는 영향 없음
        original.add("라");
        System.out.println("original: " + original); // [가, 나, 다, 라]
        System.out.println("copy: " + copy);          // [가, 나, 다]
    }
}

List.of() 주의사항

• null 요소를 허용하지 않습니다. → NullPointerException
• 중복 요소는 허용합니다.
• 반환된 리스트의 순서는 입력 순서와 동일합니다.

6. Collections 유틸리티 클래스

Collections 클래스는 List를 다룰 때 유용한 정적 메서드를 제공합니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsUtil {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3));

        // sort: 오름차순 정렬
        Collections.sort(numbers);
        System.out.println("정렬: " + numbers); // [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

        // reverse: 역순 정렬
        Collections.reverse(numbers);
        System.out.println("역순: " + numbers); // [9, 6, 5, 5, 4, 3, 3, 2, 1, 1]

        // shuffle: 무작위 섞기
        Collections.shuffle(numbers);
        System.out.println("섞기: " + numbers); // 무작위 순서

        // min, max: 최솟값, 최댓값
        System.out.println("최솟값: " + Collections.min(numbers));
        System.out.println("최댓값: " + Collections.max(numbers));

        // frequency: 특정 값의 등장 횟수
        Collections.sort(numbers);
        System.out.println("5의 등장 횟수: " + Collections.frequency(numbers, 5)); // 2

        // binarySearch: 이진 탐색 (정렬된 리스트에서만 사용)
        int idx = Collections.binarySearch(numbers, 4);
        System.out.println("4의 인덱스: " + idx);

        // fill: 모든 요소를 특정 값으로 채우기
        ArrayList<String> blanks = new ArrayList<>(List.of("a", "b", "c"));
        Collections.fill(blanks, "X");
        System.out.println("fill: " + blanks); // [X, X, X]

        // unmodifiableList: 불변 래퍼 반환 (Java 9+ List.of() 권장)
        List<Integer> readOnly = Collections.unmodifiableList(numbers);
        // readOnly.add(100); // UnsupportedOperationException!
    }
}

7. 실전 예제: 학생 성적 관리 시스템

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class StudentGradeManager {

    // 학생 데이터 클래스
    static class Student {
        String name;
        int score;
        String grade;

        public Student(String name, int score) {
            this.name = name;
            this.score = score;
            this.grade = calculateGrade(score);
        }

        private String calculateGrade(int score) {
            if (score >= 90) return "A";
            if (score >= 80) return "B";
            if (score >= 70) return "C";
            if (score >= 60) return "D";
            return "F";
        }

        @Override
        public String toString() {
            return String.format("[%s: %d점(%s)]", name, score, grade);
        }
    }

    public static void main(String[] args) {
        ArrayList<Student> students = new ArrayList<>();

        // 학생 추가
        students.add(new Student("김철수", 85));
        students.add(new Student("이영희", 92));
        students.add(new Student("박민준", 78));
        students.add(new Student("최지은", 95));
        students.add(new Student("정다운", 65));
        students.add(new Student("한소희", 88));

        System.out.println("=== 전체 학생 목록 ===");
        students.forEach(System.out::println);

        // 점수 내림차순 정렬
        students.sort(Comparator.comparingInt((Student s) -> s.score).reversed());
        System.out.println("\n=== 성적 순위 ===");
        for (int i = 0; i < students.size(); i++) {
            System.out.println((i + 1) + "위: " + students.get(i));
        }

        // 평균 점수 계산
        double avg = students.stream()
                .mapToInt(s -> s.score)
                .average()
                .orElse(0);
        System.out.printf("\n평균 점수: %.1f점%n", avg);

        // 특정 등급 학생 필터링
        System.out.println("\n=== A등급 학생 ===");
        List<Student> aGrade = students.stream()
                .filter(s -> s.grade.equals("A"))
                .toList(); // Java 16+
        aGrade.forEach(System.out::println);

        // 학생 검색 (이름으로)
        String searchName = "박민준";
        System.out.println("\n=== " + searchName + " 검색 ===");
        students.stream()
                .filter(s -> s.name.equals(searchName))
                .findFirst()
                .ifPresentOrElse(
                    s -> System.out.println("찾음: " + s),
                    () -> System.out.println("찾지 못함")
                );

        // 학생 제거 (조건: 60점 미만)
        students.removeIf(s -> s.score < 60);
        System.out.println("\n=== 60점 이상 학생 ===");
        students.forEach(System.out::println);

        // 최고점/최저점
        Student top = Collections.max(students, Comparator.comparingInt(s -> s.score));
        Student bottom = Collections.min(students, Comparator.comparingInt(s -> s.score));
        System.out.println("\n최고 득점자: " + top);
        System.out.println("최저 득점자: " + bottom);
    }
}

출력 결과:

=== 전체 학생 목록 ===
[김철수: 85점(B)]
[이영희: 92점(A)]
[박민준: 78점(C)]
[최지은: 95점(A)]
[정다운: 65점(D)]
[한소희: 88점(B)]

=== 성적 순위 ===
1위: [최지은: 95점(A)]
2위: [이영희: 92점(A)]
3위: [한소희: 88점(B)]
4위: [김철수: 85점(B)]
5위: [박민준: 78점(C)]
6위: [정다운: 65점(D)]

평균 점수: 83.8점

=== A등급 학생 ===
[최지은: 95점(A)]
[이영희: 92점(A)]

=== 박민준 검색 ===
찾음: [박민준: 78점(C)]

=== 60점 이상 학생 ===
[최지은: 95점(A)]
[이영희: 92점(A)]
[한소희: 88점(B)]
[김철수: 85점(B)]
[박민준: 78점(C)]
[정다운: 65점(D)]

최고 득점자: [최지은: 95점(A)]
최저 득점자: [정다운: 65점(D)]

8. 고수 팁: List 성능 최적화

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

public class ListPerformanceTips {
    public static void main(String[] args) {
        // 팁 1: 대량 삽입 시 초기 용량 지정
        ArrayList<Integer> list = new ArrayList<>(10000); // 재할당 최소화
        for (int i = 0; i < 10000; i++) {
            list.add(i);
        }

        // 팁 2: 중간 삭제 루프 시 뒤에서부터 삭제 (앞에서 삭제하면 인덱스 밀림)
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) % 2 == 0) {
                list.remove(i); // 짝수 삭제
            }
        }
        System.out.println("홀수만 남음, 크기: " + list.size()); // 5000

        // 팁 3: 조건부 대량 삭제는 removeIf 사용 (내부 최적화)
        ArrayList<String> names = new ArrayList<>(List.of("Alice", "Bob", "Alex", "Charlie", "Andrew"));
        names.removeIf(name -> name.startsWith("A")); // A로 시작하는 이름 삭제
        System.out.println("A 제외: " + names); // [Bob, Charlie]

        // 팁 4: 읽기 전용 뷰가 필요하다면 List.copyOf 또는 Collections.unmodifiableList
        List<String> readOnly = List.copyOf(names);
        System.out.println("읽기 전용: " + readOnly);
    }
}

순회 중 수정 금지

// 잘못된 코드 - ConcurrentModificationException 발생!
for (String s : list) {
    if (s.equals("삭제")) {
        list.remove(s); // 금지!
    }
}

// 올바른 코드 1: removeIf 사용
list.removeIf(s -> s.equals("삭제"));

// 올바른 코드 2: Iterator.remove 사용
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("삭제")) {
        it.remove(); // 안전
    }
}