Java Mid 14 - Collection Array
in Programming Language on Java
배열(Array) 개념 정리
- 배열은 메모리에 연속적으로 저장되며, 인덱스를 사용해 빠르게 데이터를 찾을 수 있다.
- 인덱스를 사용하면 단 한 번의 연산으로 자료의 위치를 계산해 접근할 수 있다.
배열의 인덱스 접근 원리
- 배열에서
arr[2]에 위치한 데이터를 찾는 경우를 가정하자:- 배열은 메모리상에 순차적으로 저장되어 있다.
int타입의 데이터는 4바이트를 차지한다.- 배열의 시작 주소 + 자료 크기(4바이트) × 인덱스(2)를 통해 메모리에서 해당 데이터의 위치를 계산할 수 있다.
즉, 배열에 있는 데이터가 아무리 많아도 단일 연산으로 데이터에 접근할 수 있다. 이런 방식의 데이터를 찾는 작업을 검색이라고 한다.
배열에서 데이터 추가 시 문제점
배열에 데이터를 추가하려면 기존 데이터를 이동해야 한다. 데이터가 추가되는 위치에 따라 성능에 차이가 발생한다.
- 중간에 추가: 기존 데이터를 오른쪽으로 한 칸씩 밀어야 하므로 많은 연산이 필요하다.
- 처음에 추가: 배열의 모든 데이터를 오른쪽으로 이동해야 하므로 성능이 가장 저하된다.
- 끝에 추가: 새로운 공간에 데이터를 바로 넣을 수 있어 성능이 가장 좋다.
package 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 ) );
//배열의 첫번째 위치에 추가
//기존 배열을 한 칸씩 뒤로 밀고 첫번 째 위치에 추가
int newValue = 3;
addFirst(arr, newValue); //배열에다가 new Value를 넣는 메서드
System.out.println( Arrays.toString( arr ) );
//index 위치에 추가
//기본 배열의 데이터를 한 칸씩 밀고 배열의 index 위치에 추가
int index = 2;
int value = 4;
addAtIndex(arr, index, value );
System.out.println( Arrays.toString( arr ) );
addLastIndex( arr, 5 );
System.out.println( Arrays.toString(arr) );
}
private static void addLastIndex(int[] arr, int newValue) {
arr[arr.length - 1] = newValue;
}
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; //인덱스에 위치에 value 삽입
}
private static void addFirst(int[] arr, int newValue) {
for (int i = arr.length - 1; i > 0; i--) { //배열의 크기가 5 거기서 -1을 뺴줘야 index가 되기 때문이다.
arr[i] = arr[i - 1]; //왼쪽에 있는 값 오른쪽에 대입
}
arr[0] = newValue;
}
}
배열의 시간 복잡도
- 조회 (Access)
- 시간 복잡도: O(1)배열은 인덱스를 통해 특정 위치의 데이터를 바로 접근하므로, 데이터의 개수에 상관없이 상수 시간에 조회가 가능하다.
- 탐색 (Search)
- 시간 복잡도: O(n)배열 내에서 특정 값을 찾으려면 데이터를 하나씩 비교해야 한다. 따라서 배열의 크기가 커질수록 탐색에 소요되는 시간이 선형적으로 증가한다.
- 삽입 (Insert)
- 시간 복잡도: O(n)배열에 데이터를 추가하려면, 추가할 위치에 따라 데이터를 이동시켜야 한다. 특히 중간이나 앞부분에 데이터를 추가할 경우, 나머지 데이터를 모두 오른쪽으로 이동시켜야 하므로 최악의 경우 배열 크기만큼 이동이 필요하다.
- 끝에 추가하는 경우에는 이동이 없으므로 시간 복잡도는 O(1)이다.
- 삭제 (Delete)
- 시간 복잡도: O(n)데이터를 삭제한 후에도 남은 데이터를 채우기 위해 배열의 다른 요소들을 이동해야 하므로, 최악의 경우 배열 크기만큼 이동이 필요하다.
배열의 한계
배열의 한계는 배열의 크기가 지정되어 있어서 동적인 움직임에 한계가 있다는 점이다. 예를들어 1000명을 모집하기로 했는데 10000명이 온다면 9000명이 이벤트에 참여하지 못한다. 그럼 100만개의 배열을 만들면 되는게 아닐까? → 사용하지 않는 배열은 메모리의 낭비가 된다. 배열의 길이가 정적으로 정해지는 것이 배열의 단점이 된다. 그래서 동적인 배열이라는 것이 존재한다.
Reference
인프런 김영한님의 자바강좌 + 나의 뇌