[ 알고리즘 ] 1. 배열

📌 배열의 특징 

0(1) 에 k 번째 원소를 확인/변경 가능하다. 

: 배열은 메모리상에 원소를 연속하게 배치한 자료구조이기때문에, k번째 원소의 위치를 바로 계산할 수 있다. 단, 임의의 위치에 원소를 추가 또는 제거할 시에는 한칸씩 밀거나 땡겨야 하므로, O(N)의 시간이 걸리게 된다. 

🍉추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다.

: 연결리스트와 비교하자면, 연결리스트는 다음노드의 주소값 또한 가지고 있어야하지만 배열의 경우 순서대로 주소가 정해지기때문에 메모리의 낭비가 적다. 

🍉메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. 

 

	public static void insert_test(){
		  System.out.println("***** insert_test *****\n");
		  int arr[] = new int[10];
		  arr[0] = 10 ;arr[1]=20;arr[2] = 30; 
		  int len = 3;
		  insert(3, 40, arr, len); // 10 20 30 40
		  printArr(arr, len);
		  insert(1, 50, arr, len); // 10 50 20 30 40
		  printArr(arr, len);
		  insert(0, 15, arr, len); // 15 10 50 20 30 40
		  printArr(arr, len);
		}

	static void insert(int idx,int num,int[] arr,int len) {
		for (int i=arr.length-2;i>=idx;i--) {
			arr[i+1] = arr[i];
		}
		arr[idx] = num;
	}

( erase ) 

	static void erase_test(){
		  System.out.println("***** erase_test *****\n");
		  int arr[] = {10, 50, 40, 30, 70, 20,0,0,0};
		  int len = 6;
		  erase(4, arr, len); // 10 50 40 30 20
		  printArr(arr, len);
		  erase(1, arr, len); // 10 40 30 20
		  printArr(arr, len);
		  erase(3, arr, len); // 10 40 30
		  printArr(arr, len);
		}

	static void erase(int idx, int[] arr, int len){
		for (int i=idx;i<len;i++) {
			arr[i] = arr[i+1];
		}
	}