[기초 자료구조] 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. 구현

Array

코드

public 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.arraycopy(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 == cnt) {
            addLast(num);
            return;
        }

        System.arraycopy(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-1);
        cnt--;
    }

    public void removeLast() {
        if (cnt == 0) return;
        arr[--cnt] = EMPTY_VALUE;
    }

    // From Head
    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, arr, idxToDel+1, cnt-idxToDel);
        arr[--cnt] = EMPTY_VALUE;

        return true;
    }

    private int get(int idx) {
        rangeCheck(idx);

        return arr[idx];
    }

    private void rangeCheck(int idx) {
        if (idx < 0 || idx >= size) throw new ArrayIndexOutOfBoundsException("invalid index to add element");
    }

    private void fullCheck() {
        if (size == cnt) throw new IllegalStateException("Cannot add element: Array is already full");
    }
}

 

 

 

출처

• Wiki - Array