리스트

리스트란?

• 순서가 있는 데이터 집합
• 중복 허용
• 인덱스로 접근 가능
• 수정 및 삭제 가능 (mutable)

정적 배열 (Static Array)

고정된 크기를 갖는 배열. 선언 시 메모리를 미리 할당받으며, 크기 변경이 불가능

특징

• 고정 크기
  예: int arr[5] = {1, 2, 3, 4, 5};
• 연속된 메모리에 저장됨 → 빠른 접근(O(1)) 가능
• 데이터 삽입/삭제에 비효율적

예시 (C/C++)

int arr[5] = {3, 7, 4, 2, 6};  // 5개의 int형 배열

• arr[3] 접근 → arr + (3 * 4byte)로 산술 연산만으로 접근 가능

동적 배열 (Dynamic Array)

실행 중 크기를 유연하게 변경할 수 있는 배열. 배열이 가득 차면 더 큰 배열로 복사 후 교체

특징

• 데이터 추가 시 용량 초과되면 2배로 확장 (Doubling)
• 대부분의 삽입 연산은 O(1), 리사이징 발생 시 O(n)
• Amortized O(1) 삽입 시간복잡도

Java에서의 배열 및 리스트

정적 배열 사용

int[] arr = new int[5];            // 선언
arr[0] = 1;                        // 수정
System.out.println(arr[0]);       // 접근
int[] copy = Arrays.copyOf(arr, arr.length); // 복사

2차원 배열 복사 (Deep Copy)

int[][] copy = new int[original.length][];
for (int i = 0; i < original.length; i++) {
    copy[i] = Arrays.copyOf(original[i], original[i].length);
}

 

Java의 동적 배열: ArrayList

선언과 초기화

List<Integer> list = new ArrayList<>();
List<Integer> list2 = new ArrayList<>(List.of(1, 2, 3));

주요 연산

연산	예시	시간복잡도
추가 (끝에)	list.add(10);	O(1)
추가 (중간에)	list.add(2, 10);	O(n)
삭제 (끝에)	list.remove(list.size() - 1);	O(1)
삭제 (중간에)	list.remove(2);	O(n)
접근 / 수정	list.get(i);, list.set(i, v);	O(1)

값 삭제 vs 인덱스 삭제 주의

list.remove(2);                  // 2번째 인덱스 삭제
list.remove(Integer.valueOf(2)); // 값이 2인 요소 삭제

 

2차원 ArrayList

List<List<Integer>> matrix = new ArrayList<>();
for (int i = 0; i < 3; i++) {
    List<Integer> row = new ArrayList<>();
    for (int j = 0; j < 3; j++) {
        row.add(i * 3 + j);
    }
    matrix.add(row);
}

2차원 ArrayList Deep Copy

List<List<Integer>> deepCopy = new ArrayList<>();
for (List<Integer> row : matrix) {
    deepCopy.add(new ArrayList<>(row));
}

 

리스트 순회 중 삭제 시 주의

잘못된 예시 (ConcurrentModificationException 발생)

for (String s : list) {
    if (s.length() == 3) list.remove(s);
}

올바른 방법

List<String> result = new ArrayList<>();
for (String s : list) {
    if (s.length() != 3) result.add(s);
}

또는 Stream API 사용

List<String> result = list.stream()
    .filter(s -> s.length() != 3)
    .collect(Collectors.toList());