자바 중급 2편 - ArrayList(1)

배열의 특징 1 - 배열과 인덱스

✅ 자료 구조란?

• 여러 데이터를 구조화해서 다루는 방식
• 자바는 배열 외에도 컬렉션 프레임워크를 통해 다양한 자료 구조 제공

✅ 배열에서의 입력, 변경, 조회

 

작업시간	복잡도	설명
입력 (arr[0] = 1)	O(1)	인덱스로 위치 바로 접근
변경 (arr[2] = 10)	O(1)	인덱스 위치 값만 수정
조회 (System.out.println(arr[2]))	O(1)	인덱스로 빠르게 조회 가능

 

int[] arr = new int[5];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[2] = 10;
System.out.println(arr[2]); // 10

---

✅ 배열의 검색

• 특정 값을 찾기 위해 배열을 순회하며 비교 필요 → O(n)
• 검색 예시:

int value = 10;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == value) {
        System.out.println(value + " 찾음");
        break;
    }
}

---

✅ 배열의 메모리 구조

배열은 메모리상 연속적으로 배치되어 있음

• int → 4바이트
• 공식: 시작주소 + (자료 크기 * 인덱스)

 

인덱스	메모리 주소
arr[0]	x100
arr[1]	x104
arr[2]	x108

 

---

📊 빅오(Big O) 표기법

✅ 개요

• 알고리즘의 성능 변화 추세를 수학적으로 표현
• 입력 데이터가 커질수록 연산량의 변화를 기준으로 측정

✅ 주요 표기

표기	설명	예시
O(1)	상수 시간	인덱스를 이용한 조회
O(n)	선형 시간	배열 검색, 전체 순회
O(n²)	이중 루프	이중 반복문
O(log n)	로그 시간	이진 탐색
O(n log n)	정렬 알고리즘 등	병합정렬 등

 

---

✅ 배열과 빅오

연산	시간 복잡도
인덱스 접근	O(1)
검색	O(n)

 

---

➕ 배열의 특징 2 - 데이터 추가

✅ 데이터 추가 위치별 동작

위치	설명	시간 복잡도
첫 번째	모든 데이터를 오른쪽으로 한 칸 이동	O(n)
중간	해당 인덱스 오른쪽 데이터만 이동	O(n)
마지막	바로 추가	O(1)

 

package com.example.collection.array;

import java.util.Arrays;

public class ArrayMain2 {

    public static void main(String[] args) {

        int[] arr = new int[5];

        arr[0] = 1;
        arr[1] = 2;

        System.out.println(Arrays.toString(arr));

        // 배열의 첫번째 위치에 추가
        // 기본 배열의 데이터를 한 칸씩 밀고 배열의 첫번째 위치에 추가
        System.out.println("배열의 첫번째 위치에 3 추가 O(n)");
        int newValue = 3;
        addFirst(arr, newValue);

        System.out.println(Arrays.toString(arr));

        // index 위치에 추가
        // 기본 배열의 데이터를 한 칸씩 밀고 배열의 index위치에 추가
        System.out.println("배열의 index(2) 위치에 4 추가 O(n)");
        int index = 2;

        int value = 4;

        addAtIndex(arr, index, value);
        System.out.println(Arrays.toString(arr));
        

    }

    private static void addAtIndex(int[] arr, int index, int value) {

        for (int i = arr.length - 1; i > index ; i--) {
            arr[i] = arr[i - 1];
        }

        arr[index] = value;

    }

    private static void addFirst(int[] arr, int newValue) {

        for (int i = arr.length - 1; i > 0; i--) {

            arr[i] = arr[i - 1];

        }

        arr[0] = newValue;

    }

}

 

---

✅ 배열의 한계

• 크기를 생성 시 미리 고정해야 함
• 동적으로 크기를 조절할 수 없음
• 이벤트 참여자 수처럼 예측 불가능한 경우에 한계

---

📌 정리

기능	시간 복잡도	특징
인덱스 접근	O(1)	빠름
검색	O(n)	느림
데이터 추가 (마지막)	O(1)	효율적
데이터 추가 (앞/중간)	O(n)	비효율적
크기 변경	❌ 불가능	정적 구조

 

출처 : 김영한 자바 - 중급 2편