Java ArrayList

일련의 숫자로 이루어진 배열 데이터(자료) 구조화 된 것이 자료구조라 한다.

자바는 컬렉션 프레임워크의 이름으로 자료구조를 제공하고 있다.

컬렉션 프레임워크 전 자바 기본 배열을 사용법을 살펴보자.

Array.class - 입력 - O(1)

import java.util.Arrays;

public class Array {
    public static void main(String[] args) {
        int[] arr = new int[4];
        // index 입력하기: 빅오의 O(1) 의 속도로 입력함
        System.out.println("index 데이터 입력하기 O(1) 속도");
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        System.out.println(Arrays.toString(arr));
    }
}

index 데이터 입력하기 O(1) 속도
[1, 1, 1, 1]

Array.class - 변경 - O(1)

int[] arr = new int[4];
// index 변경하기: 빅오의 O(1) 의 속도로 변경함
System.out.println("index 데이터 변경하기 O(1) 속도");
arr[0] = 100;
arr[1] = 100;
arr[2] = 100;
arr[3] = 100;
System.out.println(Arrays.toString(arr));

index 데이터 변경하기 O(1) 속도
[100, 100, 100, 100]

배열의 위치를 바로 지정해 속도가 빠르다.

Array.class - 조회 - O(1)

int[] arr = new int[4];
// index 조회하기: 빅오의 O(1) 의 속도로 조회함
System.out.println("index 데이터 조회하기 O(1) 속도");
arr[2] = 100;
System.out.println("arr[2] = " + arr[2]);

index 데이터 조회하기 O(1) 속도
arr[2] = 100

Array.class - 검색 - O(N)

int[] arr = new int[4];
        arr[2] = 100;

        // index 검색하기: 빅오의 O(n) 의 속도로 검색함
        System.out.println("index 데이터 검색하기 O(n) 속도");
        int value = 100;
        int search = 0;
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr[" + i + "] = " + arr[i]);
            if (value == arr[i]) {
                search = value;
            }
        }
        System.out.println("Find Value = " + value);

index 데이터 검색하기 O(n) 속도
arr[0] = 0
arr[1] = 0
arr[2] = 100
arr[3] = 0
Find Value = 100

배열의 특징

메모리에서 배열을 그림으로 표현해보았다.

int[] arr = new int[4];
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;

예제 코드

int[] arr
+------+
| x000 |
+------+

[0]      [1]     [2]     [3]
+-------+-------+-------+-------+
| 4byte | 4byte | 4byte | 4byte |
| 10    | 20    | 30    | 40    | 
+-------+-------+-------+-------+
 x000    x004    0x008   0x012

메모리로 시각화한 것이다.
메모리는 순서대로 붙어서 존재한다.
int 형은 4바이트씩 차지하므로 메모리 주소도 4바이트마다 값이 존재한다.
arr[2] 값 30를 찾는 다고 가정
- 배여르이 시작 위치 x000 부터 시작해 자료의 크기(4byte)를 가지고 인덱스를 곱해 메모리 위치를 찾게 된다.
  - 시작 주소"arr(000) + (size(4) * index(2)) = x008" 결과가 나오며 x008 에는 30이라는 숫자가 있다.

배열은 인덱스를 사용해 한번 계산으로 효율적으로 자료 위치를 찾는다. 인덱스를 통한 입력, 변경, 조회 계산이 필요한 위치를 찾아 처리한다. 배열에서 인덱스를 알고 있는 경우 바로 위치를 찾아가 원하는 값을 출력하게 된다.

배열 검색 O(n) 속도가 나온 이유는?

배열에 들어 있는 특정 데이터를 찾아내는 것이 검색이다.
이전에 인덱스를 알고 있다면 한번에 찾아서 꺼내서 찾아낼 수 있으나. 인덱스를 모르는 경우 배열에 들어간 모든 데이터를 방문을 열어 값을 비교해야 한다. 배열의 크기가 클 수록 방문 횟수가 많아지므로 오래 걸린다.