배열(Array)

• 많은 수의 데이터를 다룰때 사용하는 자료구조
• 각 데이터를 인덱스와 1:1 대응하도록 구성
• 데이터가 메모리 상에 연속적으로 저장됨

데이터	'a'	'b'	'c'	'd'	'e'
인덱스	0	1	2	3	4

특징

• 고정된 크기로 생성
• 많은 수의 데이터를 다룰떄 사용
• 요소들이 메모리상에 연속으로 저장된다
• 각 요소들이 인덱스와 1:1 대응하므로 인덱스를 사용해 각 요소에 접근할 수 있다.

구조

타입[] 변수 = {}

시간복잡도

• Access: $O(1)$
• Search: $O(N)$
• Insertion: $O(N)$
• Deletion: $O(N)$
  단, 배열의 앞과 뒤에 추가/제거하는 경우는 $O(1)$

장점

인덱스를 사용해 요소에 직접 접근하므로 접근이 빠르다.

단점

데이터의 추가/삭제가 번거로움

• 미리 최대길이를 정해서 생성해야함
• 가변길이 배열은 배열의 크기를 변경할 때 마다 새로운 배열을 생성
  ex) 새로운 데이터를 추가할 때 메모리를 새로 생성하여 복사 진행
• 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지

배열의 생성, 삽입, 삭제 기능 구현

배열 클래스

class MyArray{
	int[] arr;
    MyArray(int size){
    	this.arr = new int[size];
	}
}

배열에 특정 데이터 삽입

public void insertData(int index, int data){
	if(index < 0 || index > this.arr.length){
    	System.out.println("Index Error");
            return;
	}
    int[] arrDup = this.arr.clone();
    
    this.arr = new int[this.arr.length+1];
    
    for(int i = 0; i < index; i++){
        	this.arr[i] = arrDup[i];
	}
    
    for(int i =index+1; i<this.arr.length; i++){
        	this.arr[i] = arrDup[i-1];
	}
    
    this.arr[index] = data;
}

배열에서 특정 데이터 삭제

public void removeData(int data){
	for (int i = 0; i<this.arr.length; i++){
    	if(this.arr[i] == data){
        	targetIndex = i;
            break;
		}
	}
    if(targetIndex == -1){
    	System.out.println("해당 데이터가 없습니다.");
	} else {
    	int[] arrDup = this.arr.clone();
        this.arr = new int[this.arr.length - 1];
        for (int i=0; i<targetIndex; i++){
        	this.arr[i] = arrDup[i];
		}
        for (int i =targetIndex; i<this.arr.length; i++){
        	this.arr[i] = arrDup[i+1];
		}
	}
}