자료구조 - 배열

자료구조 - 배열

---

순서(index)를 가진 데이터의 집합

• 가장 기본적인 자료구조

Scanner sc = new Scanner(System.in)
int N = sc.nextInt();
int[] arr = new int[N]
for (int i = 0; i < Nl i++)
	arr[i] = sc.nextInt();	// 배열의 저장

long sum = 0;
for (int i=0; i < N; i++)
	sum += arr[i]	// 배열의 탐색, 원소의 접근

• 생성과 동시에 크기가 고정됨
• 전체 원소가 메모리상에 일렬로 저장됨

배열에 대한 아래 기능들의 시간복잡도는?

• get(int idx): idx번째 원소 반환
  - 메모리가 연속적이기 때문에 arr의 시작 주소로부터 idx만큼 떨어진 원소의 주소를 바로 계산하고, 접근할 수 있다.
  ex)

public static int getElement(int[] arr , int idx) {
	return arr[idx];
}

• change(int idx, int val): idx번째 원소를 val로 변경
  - [] 연산자를 통해 idx번 원소에 바로 접근하고, 값을 변경할 수 있다.
  ex)

public static void changeElement(int idx, int val) {
	arr[idx] = val;
}

• append(int val): 가장 뒤에 원소 삽입
  - 한 번 생성된 배열은 고정 길이이다. 원소들이 연속되어있는 배열의 마지막에 원소를 추가할 때 이미 배열이 꽉 찼다면 그보다 큰 새 배열을 생성해 옮겨 닮아야 한다.
  ex)

public static boolean appendElement(int[] arr, int arrCount, int val) {
	if (arrCount == arr.length)
    	return false;
    arr[arrCount] = val;
    return true;
}

• insert(int idx, int val): 현재 idx번째 원소의 앞에 원소 삽입
  - 원소들이 연속되어있는 배열의 중간에 원소를 추가하기 위해서는 추가되는 원소의 뒷 원소들이 모두 한 칸씩 뒤로 이동해 새 원소를 삽입할 수 있는 자리를 만들어야 한다.
  ex)

public static boolean insertElement(int[] arr, int arrCount, int idx, int val) {
	if (idx > arrCount || arrCount >= arr.length)
    	return false;
    for (int i = arrCount; i > idx; i--)
    	arr[i] = arr[i - 1];
    arr[idx] = val;    
    return true;
}

• erase(int idx): idx번째 원소 삭제
  - 원소들이 연속되어있는 배열의 중간 원소를  삭제할때에는 해당 원소의 뒷 원소들을 모두 한 칸씩 앞으로 이동해야한다.
  ex)

public static boolean eraseElement(int[] arr, int arrCount, int idx) {
	if (idx >= arrCount)
    	return false;
    for (int i = idx; i < arrCount; i++)
    	arr[i] = arr[i + 1];
    return true;
}

 

원소에 접근하고 변경하는 것은 빠르나, 중간 원소를 추가/삭제하는 것은 최대 배열 원소의 개수까지 시간이 걸린다.