배열 (Array)

 

배열의 특징

 

• 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.
• 프로그래밍 언어에서 동일 데이터 타입을 저장 하며, 다른 타입의 요소를 저장할 수 없다. 배열을 구성하는 각각의 값을 요소(element), 배열에서 위치를 가리키는 숫자를 인덱스(index)라고 한다.

 

 

 

배열의 시간 복잡도

Operation	average case	worst case
읽기(read)	O(1)	O(1)
삽입(insert)	O(n)	O(n)
삭제(delete)	O(n)	O(n)
탐색(search)	O(n)	O(n)

 

시간 복잡도의 특징은 항상 최악의 상황을 고려한다.

 

• 읽기의 시간복잡도는 특정 인덱스로 바로 접근이 가능하기 때문에 O(1)이다.
• 삽입의 시간 복잡도는 원하는 인덱스에 삽입, 그 이후의 인덱스는 오른쪽 한칸씩 이동해야 하기 때문에 O(N)이다.(10개의 elements가 있다면 0번째(최악의 경우)에 삽입한다고 가정, 그 이후의 10개의 elements를 이동하면 O(N)이다.)
• 삭제의 시간 복잡도는 원하는 인덱스를 삭제, 그 이후의 인덱스를 왼쪽으로 한칸씩 이동해야 하기 때문에 O(N)이다.(10개의 elements가 있다면 0번째(최악의 경우)를 삭제한다고 가정, 그 이후의 10개의 elements를 이동하면 O(N)이다.)
• 탐색의 시간 복잡도는 원하는 value의 elements를 찾는 경우이다. 가장 마지막(최악의 경우)이 일치할 경우 O(N)이다.

 

장점

• 구현하기가 쉽다.
• 인덱스를 이용해 검색 성능이 우월하다.
• 데이터 크기가 확정되었으면 메모리나 처리속도 면에서는 용이하다.
• 연속된 메모리 공간에 존재하기 떄문에 관리가 편하다.

 

단점

• 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없다.
• 중간에 특정 요소를 삽입 및 삭제 하는 경우 메모리가 순차적으로 이어져 있어야 하기에 해당하는 요소들을 이동 시켜주어야 하기 때문에 비용이 많이 들게된다.
• 배열의 크기가 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하면 오버플로우의 발생이나 저장공간이 낭비 될 수 있다.

 

배열을 자주 사용하는 경우

• 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
• 다차원 데이터를 다룰 때
• 특정 요소를 빠르게 읽어야 할 때
• 데이터 사이즈가 자주 바뀌지 않으며 요소의 추가 및 삭제되지 않을 때

 

배열의 구현

java로 배열을 구현하였다.

/*
* 배열 구현
* 1. 동일한 데이터 타입을 순서에 따라 관리하는 자료구조
* 2. 정해진 인덱스의 크기가 있다.
* 3. 요소의 추가와 제거시 다른 요소들의 이동이 필요
* 4. 배열의 n번째 요소를 찾는 연산이 빠르다.
* jdk 클래스: ArrayList, Vector
* */



public class MyArray {

    private int[] intArray;// 배열 생성
    private int ArraySize; //배열의 크기, 할당한 만큼 제한 할 것.
    private int count; // 요소의 갯수
    public static final int ERROR_NUM = -999999999;

    // 생성자
    public MyArray(int size){
        intArray = new int[size]; // 크기만큼 할당
        count = 0; //요소의 갯수
        ArraySize = size; // 요소의 길이
    }

    /*
     * 요소 추가
     * 조건
     * 1. 요소의 갯수가 size를 초과하지 않는가
     * */
    public void addElement(int num){
        if(count >= ArraySize){
            System.out.println("size 초과");
            return;
        }
        // n번째에 요소를 추가한 후, 요소의 갯수를 늘린다.
        intArray[count++] = num;
    }

    /*
     * 특정 인덱스에 요소 추가
     * 조건
     * 1. 요소의 갯수가 size를 초과하지 않는가
     * 2. 포지션 위치가 적당한가
     * */
    public void insertElement(int position, int num){
        if(count >= ArraySize){
            System.out.println("size 초과");
            return;
        }

        // 요소의 갯수보다 위치가 작거나, 0보다 작으면 error
        if(position > count || position < 0){
            System.out.println("error");
            return;
        }

        // 포지션 이후의 요소를 오른쪽으로 이동
        for (int i = count-1; i >= position; i--){
            intArray[i+1] = intArray[i];
        }

        intArray[position] = num;
        count++;

    }

    // 요소 삭제
    // 1. 비어있지 않아야 한다.
    // 2. 포지션이 적당한가.
    public int removeElement(int position){

        if(position >= ArraySize){
            System.out.println("size 초과");
            return ERROR_NUM;
        }
        if(position > count || position < 0){
            System.out.println("error");
            return ERROR_NUM;
        }

        // 반환될 포지션의 값
        int ret = intArray[position];

        // 포지션으로 부터 요소의 왼쪽 이동
        for (int i = position; i < count-1; i++){
            intArray[i] = intArray[i+1];
        }

        count--;
        return ret;
    }

    //사이즈 반환
    public int getSize(){
        return count;
    }

    //배열이 비어 있는가
    public boolean isEmpty(){
        if(getSize() == 0)
            return true;
        return false;

    }

    //모든 요소 출력
    public void printAll(){
        if(count == 0){
            System.out.println("요소 없음");
            return;
        }
        for(int i = 0; i<count; i++){
            System.out.print(intArray[i]+" ");
        }
        System.out.print("\n");
    }


    //모든 요소 제거
    public void removeAll(){
        // 갯수 -1 인덱스를 모두 제거
        for(int i = count-1; i>=0; i--){
            intArray[i] = 0;
        }
        count = 0;
    }


}