배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 한다.
자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.
package com.example.querytest.javaTest.collentionTest;
import java.util.Arrays;
public class ArrayMain1 {
public static void main(String[] args){
int[] arr = new int[5];
//index 입력: O(1)
System.out.println("==index 입력: O(1)==");
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
System.out.println(Arrays.toString(arr));
//index 변경: O(1)
System.out.println("==index 변경: O(1)==");
arr[2] = 10;
//index 조회: O(1)
System.out.println("==index 조회: O(1)==");
System.out.println("arr[2] = " + arr[2]);
//검색: O(n)
System.out.println("==배열 검색: O(n)==");
System.out.println(Arrays.toString(arr));
int value = 10;
for(int i = 0; i < arr.length; i++){
System.out.println("arr[" + i + "]:" + arr[i]);
if(arr[i] == value){
System.out.println(value + " 찾음");
System.out.println(i + "index");
break;
}
}
}
}
배열의 특징
- 배열에서 자료를 찾을 때 인덱스(index)를 사용하면 매우 빠르게 자료를 찾을 수 있다.
- 인덱스를 통한 입력, 변경,조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.
배열의 메모리 구조와 인덱스를 통한 접근
- 배열은 메모리 상에서 연속된 공간에 순서대로 저장됩니다.
- int형 데이터는 각각 4바이트를 차지합니다.
- 배열의 시작 위치 주소와 데이터의 크기, 인덱스를 이용하면 특정 위치의 데이터를 쉽게 찾을 수 있습니다.
접근 공식
공식: 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)
예시 설명
- 배열이 시작하는 메모리 주소가 x100이라고 가정합니다.
- 배열의 자료형이 int이며, int는 4바이트를 차지합니다.
배열의 각 인덱스 위치:
- arr[0]:
- 계산: x100 + (4byte * 0) = x100
- 위치: x100
- 배열에서 인덱스를 사용하면 데이터가 아무리 많아도 한 번의 연산으로 필요한 위치를 찾을 수 있습니다. 이는 배열의 데이터 접근이 매우 효율적이라는 것을 의미합니다.
- 배열에서 인덱스를 사용하여 데이터에 접근하는 것이 효율적인 이유는 직접 접근(direct access) 방식이기 때문입니다. 배열의 요소에 접근할 때는 특정 위치를 계산하여 한 번에 접근할 수 있으므로, 시간 복잡도가 일정합니다.
배열의 특정 위치에 접근할 때는 인덱스를 사용하여 한 번의 연산으로 접근할 수 있지만, 배열에서 특정 값을 검색할 때는 배열의 요소를 하나하나 비교해야 하므로 시간이 더 많이 걸립니다. 이는 배열의 데이터 접근이 매우 효율적임을 의미하는 반면, 값 검색은 상대적으로 비효율적일 수 있음을 나타냅니다.
배열에 데이터가 100,000건이 있다면 인덱스를 사용하면 1번의 연산으로 결과를 찾을 수 있지만, 순차 검색을 사용한 다면 최악의 경우 100,000번의 연산이 필요하다. 배열에 들어있는 데이터의 크기가 증가할 수록 그 차이는 매우 커진 다.
따라서 인덱스를 사용할 수 있다면 최대한 활용하는 것이 좋다.
배열의 특정 위치에 데이터를 추가할 때는 기존 데이터를 오른쪽으로 한 칸씩 이동시켜 공간을 확보해야 합니다.
배열의 특징2 - 데이터 추가
배열의 특정 위치에 데이터를 추가하는 과정은 다음과 같습니다:
- 공간 확보: 데이터를 추가할 위치를 만들기 위해 기존 데이터를 오른쪽으로 한 칸씩 이동시킵니다.
- 데이터 추가: 지정된 위치에 새로운 데이터를 입력합니다.
배열에서 데이터를 추가하는 과정은 기존 데이터를 오른쪽으로 한 칸씩 이동시키는 연산이 필요하기 때문에, 데이터의 개수에 비례하여 시간이 걸립니다. 이러한 과정은 평균적으로 O(n) 시간 복잡도를 가지며, 배열의 크기가 클수록 더 많은 시간이 필요합니다. 이를 통해 배열에서 데이터 추가는 비효율적일 수 있음을 알 수 있습니다.
- 배열의 첫 번째 위치에 추가: 배열의 첫 번째 위치를 찾는 것은 O(1) 시간 복잡도로 매우 빠르지만, 모든 데이터를 한 칸씩 이동시켜야 하기 때문에 O(n) 시간이 걸립니다. 따라서 총 시간 복잡도는 O(n)입니다.
- 배열의 중간 위치에 추가: 배열의 중간 위치를 찾는 것도 O(1) 시간 복잡도로 빠르지만, 인덱스 이후의 데이터를 모두 한 칸씩 이동시켜야 하기 때문에 평균적으로 O(n/2) 시간이 걸립니다. 이는 O(n)과 동일하게 간주됩니다. 따라서 총 시간 복잡도는 O(n)입니다.
- 배열의 마지막 위치에 추가: 배열의 마지막 위치를 찾는 것은 O(1) 시간 복잡도로 매우 빠르며, 데이터를 이동할 필요가 없으므로 시간 복잡도는 O(1)입니다. 따라서 총 시간 복잡도는 O(1)입니다.
package com.example.querytest.javaTest.collentionTest;
import java.util.Arrays;
public class ArrayMain1 {
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));
System.out.println("배열의 마지막 위치에 5 추가 O(1)"); addLast(arr, 5);
System.out.println(Arrays.toString(arr));
}
private static void addLast(int[] arr, int newValue) {
arr[arr.length - 1] = newValue;
}
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;
}
private static void addAtIndex(int[] arr, int index, int newValue) {
for (int i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = newValue;
}
}
배열은 가장 기본적인 자료 구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다. 하지만 이런 배열에는 큰 단점이 있다. 바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점이다.
배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료 구조 가 있다면 편리할 것이다.