[기초 자료구조] Array

1. Array

 

• 같은 타입의 요소들을 보관하는 자료구조 입니다.
• 요소들의 중복을 허용합니다.

 

연속적 (선형적)

• 요소들은 메모리 연속적인 공간에 저장됩니다. (물리적)

 

인덱스 기반

• 각 요소들은 특정 인덱스에 대응되어 구성되어 있습니다.
• Random Access 가능합니다.

 

배열 주소

• 첫번째 요소의 메모리 주소 입니다.

 

요소 주소

• 기본 주소로부터 현재 요소의 인덱스와 데이터 타입 크기를 곱하여 알 수 있습니다.

 

정적 할당

• 크기가 생성되는 시기에 정해집니다.

 

요소 갯수가 배열 크기보다 커질 경우 

• 리사이즈 연산 발생
• 2배 큰 새로운 배열을 생성 + 새 배열에 요소들을 이주

 

중간 요소의 추가 연산

• 삽입: 삽입할 곳의 공간을 만들기 위해 뒤 요소들을 뒤로 한 칸씩 이동 (right shift)
• 삭제: 삭제한 공간을 메우기 위해 뒤 요소들을 앞으로 한 칸씩 이동 (left shift)

 

2. 주요 연산

search	Random Access 로 접근합니다. (요소의 인덱스를 알고 있을 경우) 순차적으로 탐색합니다.	O(1) O(n)
insert	중간 위치에 삽입 (탐색 필요)	O(n)
remove	중간 위치에 삽입 (탐색 필요)	O(n)

 

3. 구현

코드

    class MyArray {
        private static final int EMPTY_VALUE = 0;    

        final int size;
        int cnt;
        int[] arr;
        
        public MyArray(int size) {
            this.size = size;
            this.cnt = 0;
            this.arr = new int[size];
        }

        public void addFirst(int num) {
            fullcheck();
            
            if (cnt > 0) System.copyArray(arr, 0, arr, 1, cnt);
            
            arr[0] = num;
            
            cnt++;
        }

        public void addLast(int num) {
            fullcheck();
            
            arr[cnt++] = num;
        }

        public void add(int idx, int num) {
            rangeCheck(idx);
            
            if (idx == 0) {
                addFirst(num);
                return;
            } else if (idx == size-1) {
                addLast(num);
                return;
            }
            
            System.copyArray(arr, idx, arr, idx+1, cnt-idx);
            
            arr[idx] = num;
            cnt++;
        }

        public void removeFirst() {
            if (cnt == 0) return;
            
            System.arrayCopy(arr, 1, arr, 0, cnt);
            
            cnt--;
        }

        public void removeLast() {
            if (cnt == 0) return;
            
            arr[cnt--] = EMPTY_VALUE;
        }
        
        public boolean remove(int num) {
            int idxToDel = -1;
            for (int i = 0; i < cnt; i++) {
                if (arr[i] != num) continue;

                idxToDel = i;
                break;
            }
            
            if (idxToDel == -1) return false;
            
            System.arrayCopy(arr, idxToDel+1, arr idxToDel, cnt-idxToDel-1);
                
            arr[cnt--] = EMPTY_VALUE;
            
            return true;
        }

        private int get(int idx) {
            rangeCheck(idx);
            
            return arr[idx];
        }

        private void fullCheck() {
            if (cnt == size) throws IllegalStateException("");
        }
        
        private void rangeCheck(int idx) {
            if (idx < 0 || idx >= size) throws ArrayIndexOutOfBoundsException("");
        }
    }

 

 

 

출처

• Wiki - Array