[자료구조/Java] 배열(Array)

Array (배열)

각 데이터를 인덱스와 1:1 대응하도록 구성되어있으며 메모리 상에 연속적으로 저장되는 자료구조

 

배열은 정적배열(Static Array)와 동적 배열(Dynamic Array)로 나누어 지는데

주로 배열이라고 하면 정적배열을 의미한다

• 정적배열: 컴파일 시점에 크기가 결정된 배열
• 동적배열: 실행시간에 크기를 변경 가능한 배열

즉,  Array는 인덱스와 1:1 대응하여 메모리 상에 연속적으로 저장되는 크기가 결정된 자료구조이다.

 

장점

• 인덱스를 이용하여 데이터에 빠른 접근

단점

• 미리 최대 길이를 정해서 생성
  • 빈자리가 없어 새 항목을 삽입 할 수 없는 상황(Overflow)에 직면 가능하다.
  • 가변 길이 배열로 설계시 크기를 변경할 때마다 새로운 배열을 생성
• 데이터의 추가/삭제가 번거로움
• 데이터 삭제시, 인덱스 유지하기 위한 빈공간을 유지

 

시간복잡도

• 인덱스를 통한 조회 O(1)
• 검색 O(n)
• 추가 및 삭제 O(n)
  • 인덱스로 찾는 것은 O(1)이나 삭제,추가를 하면 뒤따르는 항목을 한칸씩 앞 뒤로 이동해야하기에 O(1)에 항상 수행할 수 없다. 

 

마지막으로 배열로 가변배열 만드는 예시

public class arrayPractive {
    public static void main(String[] args) {
        int[] array = { 1,5,3,8,2,1,3,2,7,97,45,23};
        DynamicArray dynamicArray = new DynamicArray(array);
        System.out.println("=================== 기본값=======================");
        dynamicArray.show();


        System.out.println("=================== 인덱스 2삭제=======================");
        dynamicArray.delete(2);
        dynamicArray.show();

        System.out.println("=================== 97삭제=======================");
        dynamicArray.removeDate(97);
        dynamicArray.show();


        System.out.println("=================== 87추가=======================");
        dynamicArray.add(87);
        dynamicArray.show();

        System.out.println("=================== 인덱스 5에 1000=======================");
        dynamicArray.insert(5,1000);
        dynamicArray.show();
    }

   static class DynamicArray{
        int[] arrInt;
        public DynamicArray() {}
        public DynamicArray(int[] arrInt) {
            this.arrInt = arrInt;
        }


        public void show(){
            for (int i = 0; i < this.arrInt.length; i++) {
                System.out.print(this.arrInt[i]+" ");
            }
            System.out.println();
        }
       public void add(int data) {

           int[] arrDup = this.arrInt.clone();
           this.arrInt = new int[arrInt.length +1];

           for(int i =0; i < arrDup.length ; i++){
               this.arrInt[i] = arrDup[i];
           }
           this.arrInt[arrDup.length] = data;
       }


        public void insert(int index, int data) {
            if(index<0 || index>this.arrInt.length){
                System.out.println("Index Error");
                return;
            }

            int[] arrDup = this.arrInt.clone();
            this.arrInt = new int[arrInt.length +1];

            for(int i =0; i < index ; i++){
                this.arrInt[i] = arrDup[i];
            }
            for(int i = index ; i < arrInt.length ; i++){
                this.arrInt[i] = arrDup[i-1];
            }
            this.arrInt[index] = data;
        }

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

        public void removeDate(int data){
            int targetIndex = -1;

            for (int i = 0; i < this.arrInt.length; i++) {
                if (this.arrInt[i] == data) {
                    targetIndex = i;
                }
            }

            if (targetIndex == -1) {
                System.out.println(data+"가 배열에 없습니다.");
                return;
            }

            this.delete(targetIndex);
        }

    }

}