[자료구조] 배열 (Array)

📚 배열 (Array)

배열은 index와 data가 1:1로 매핑되어 있는 형태로 많은 수의 데이터를 다룰 때 사용된다. (가장 기본적인 자료구조)

index로 관리하기 때문에 data가 메모리상에 연속적으로 저장된다.

 

배열의 원소들의 type은 다 같아야 하고 그렇기 때문에 원소들 모두 같은 크기를 갖는다.

 

index의 수에 따라 차원이 다른 배열을 만들 수 있다. (1차원배열, 2차원배열, ...)

 

👍 장점

index로 관리하고 메모리상에 연속적으로 저장되어있기 때문에

인덱스를 이용하여 데이터에 빠르게 접근할 수 있다.

 

👎 단점

배열의 생성할 때 미리 크기를 정해줘야 하기 때문에 더 많은 수의 데이터를 넣기 위해서는 배열을 다시 만들어줘야 한다.

데이터 추가/삭제 시에 원소를 전체적으로 이동시켜야 하는 번거로움이 있다.

---

✍🏻 배열 ADT (추상 데이터 타입)

create(size)	size를 받아 배열 생성
insert(index, item)	index와 추가할 item을 받아 해당 index에 삽입
remove(item)	item을 받아 있으면 삭제
isOver(index)	index가 배열의 크기보다 큰지 확인 true, false
print()	배열 전체 원소 출력

 

---

⚙️ 배열 기능 & 동작원리

생성

1. size값을 입력받음
2. 입력받은 size를 배열의 크기로 설정

// 슈도 코드

Array arr;

public void create(int size) {
	arr = new Array[size];
}

 

삽입

1. index와 item을 입력받음
2. isOver(index)로 입력받은 index가 유효한지 확인
3. isOver(index)가 true를 반환한다면 오류 발생 후 종료
4. 종료되지 않는다면 기존 배열의 해당 index의 값을 보존하기 위해 (size + 1)을 한 새로운 배열 생성
5. 입력받은 index를 제외한 나머지 공간에 기존 배열의 값들 채움
6. 입력받은 index에 입력받은 item 삽입

// 슈도 코드

public void insert(int index, T item) {
	if (isOver(index)) { // 배열의 크기가 해당 인덱스보다 크면
    	print(error); // 에러 발생
    }
    
    T[] temp = arr.clone(); // temp 배열에 원래 배열 복사해놓기
    arr = new T[arr.length + 1]; // item을 넣을 공간이 필요하기 때문에 size + 1
    
    for (i = 0; i < index; i++) {
    	arr[i] = temp[i]; // 0부터 index 전 까지는 데이터 그대로 유지
    }
    
    for (i = index + 1; i < arr.length; i++) {
    	arr[i] = temp[i-1]; // index 다음 부터 끝까지
    }
    
    arr[index] = item; // index위치에는 아무것도 없기 때문에 item을 넣을 수 있다.
}

 

삭제

1. item 을 입력받음
2. 배열을 처음부터 끝까지 돌며 item이 있는지 확인
3. 없다면 에러 발생 후 종료
4. 있으면 해당 index를 받아옴 (targetIndex로 변수 선언)
5. 따로 지우는 작업 필요없이 targetIndex 다음 index부터 하나씩 줄여서 item을 삭제

// 슈도 코드

public void remove(T item) {

	int targetIndex = -1; // 최소 index는 0이기 때문에 -1을 넣어줌
    
	for (i = 0; i < item.length; i++) {
    	if (arr[i] == item) {
        	targetIndex = i; // 찾으면 해당 index를 targetIndex에 넣어줌
            break; // 찾으면 바로 for문을 빠져나감
        }
    }
    
    if (targetIndex == -1) {
    	print(error); // targetIndex가 -1이란 것은 해당 item이 없음을 의미
    } else {
    
    	T[] temp = arr.clone(); // temp 배열에 원래 배열 복사해놓기
        arr = new T[arr.length - 1]; // item을 하나 지우면 길이가 하나 줄어듦
        
        for (i = 0; i < targetIndex; i++) {
            arr[i] = temp[i]; // 0부터 targetIndex 전 까지는 데이터 그대로 유지
        }
        
        for (i = targetIndex; i < arr.length; i++) {
            arr[i] = temp[i+1];
            /*
             * 기존 targetIndex의 값은 지워저야 하기 때문에
             * targetIndex부터 끝까지
             * 기존 위치의 다음 위치 item들로 덮어쓰기 해준다.
             */
        }
        
    }
}

---

⏱️ 배열의 시간복잡도

• 접근(access) O(1)
• 검색(search) O(n)
• 추가(add) O(1) or O(n)
• 제거(remove) O(1) or O(n)

접근 (access)

배열의 접근은 n번째 인덱스의 값을 찾아내는 것이기 때문에 index값을 정확히 알고 있다면 O(1)의 시간복잡도를 갖는다.

 

검색 (search)

배열의 검색은 순차검색이므로

최악으로는 제일 첫 index부터 배열의 끝까지 찾아야 하기 때문에 O(n)의 시간복잡도를 갖는다.

 

추가 (add) , 제거(remove)

해당 index를 정확히 알고 있다면 O(1),

모르는 상태라면 검색을 통해 직접 index를 찾아야 하기 때문에 최악의 경우 O(n)의 시간복잡도를 갖는다.