[자료구조] 배열

배열(Array)

많은 수의 데이터를 다룰 때 사용되는 자료구조이며, 같은 타입의 데이터를 나열한 선형 자료구조이다. 

데이터를 연속된 메모리 공간에 순차적으로 저장한다.  선언 시 배열의 크기를 정하기 때문에 배열의 크기는 고정되어 있으며 변경할 수 없다.

각 데이터와 인덱스는 1:1 대응하도록 구성되어 있다.

데이터	`a`	`b`	`c`	`d`	`e`
인덱스	0	1	2	3	4

 

배열의 장점

인덱스를 이용하여 데이터에 빠르게 접근 가능하기 때문에 검색 성능이 좋다.

연속적인 공간 할당이 되므로 관리하기가 편하다.

데이터 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리 속도 면에서 좋다. 

 

arr 배열 

`a`

`b`

`c`

arr[0] = a

arr[1] = b

arr[2] = c

위 예시와 같이 인덱스를 이용하여 데이터에 바로 접근이 가능하다. 

 

배열의 단점 

데이터의 추가/삭제가 번거로운 편이다. 

• 원소를 삽입하거나 삭제할 경우, 다음 인덱스의 모든 요소를 이동시키는 작업이 필요하다. 
  (연속된 메모리 공간, 아래 구현 코드 참조) 
• 이를 위한 연산작업이 수행되어 비효율적이다. 
• 자료의 수에 비례하여 성능이 떨어지게 된다.

배열의 크기를 바꿀 수 없다.

• 미리 최대 길이를 정해서 생성하기 때문에 크기를 바꿀 수 없다.
• 그렇기 떄문에 가변 길이 배열에 경우 크기를 변경하기 위해선 새로운 배열을 생성해줘야 한다.

메모리 재사용이 불가능하다. 

• 마찬가지로 초기 사이즈만큼 할당받아 사용된다.
• 데이터의 존재 유무와 관계없이 할당된 메모리만 사용가능하다. 
• 삭제된 데이터여도 배열을 크기를 재할당(다시 선언)해주지 않는 이상 삭제된 공간의 메모리 재사용이 불가하다.
  (요소를 삭제 시 빈 공간으로 그대로 할당되어 있음을 의미)

 

언제 사용하는 것이 좋을까?

• 데이터가 정해져 있을 경우
• 데이터 삽입, 삭제가 거의 없는 경우
• 검색 

 

시간복잡도

삽입/삭제

• 배열의 맨 앞에 삽입/삭제 하는 경우 -> O(n)
• 배열의 맨 뒤에 삽입/삭제 하는 경우 -> O(1)
• 배열의 중간에 삽입/삭제하는 경우 -> O(n)
• O(n)인 경우는 데이터 요소만큼 재복사 및 이동시켜줘야 하는 작업이 필요하기 때문이다. (구현 코드 참조) 

탐색

• O(1)
• 순차적 구조 및 인덱스 검색을 이용하기 때문에 O(1)이다.

 

배열 삽입/삭제 구현 

class MyArray {

    int[] arr;

    // 배열의 초기 사이즈 설정
    public MyArray(int size) {
        this.arr = new int[size];
    }

    // 배열에 데이터 삽입
    public void insertData(int index, int data) {
        if (index < 0 || index > this.arr.length) {
            System.out.println("index Error");
            return;
        }

        // 기존 배열을 clone을 통해 복사한다.
        int[] arrDup = this.arr.clone();
        this.arr = new int[this.arr.length + 1];

        // 인덱스 전까지 기존 값을 그대로 배열에 넣어준다.
        for (int i = 0; i < index; i++) {
            this.arr[i] = arrDup[i];
        }

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

        this.arr[index] = data;
    }

    public void removeIndex(int index) {
        if (index < 0 || index > this.arr.length) {
            System.out.println("index Error");
            return;
        }

        // 기존 배열을 clone을 통해 복사한다.
        int[] arrDup = this.arr.clone();
        this.arr = new int[this.arr.length - 1];

        // 인덱스 전까지 기존 값을 그대로 배열에 넣어준다.
        for (int i = 0; i < index; i++) {
            this.arr[i] = arrDup[i];
        }

        for (int i = index; i < this.arr.length; i++) {
            this.arr[i] = arrDup[i + 1];
        }
    }
}

public class Practice {
    public static void main(String[] args) {
        int size = 5;
        MyArray myArray = new MyArray(size);

        for (int i = 0; i < size; i++) {
            myArray.arr[i] = i + 1;
        }
        // [1, 2, 3, 4, 5]
        System.out.println(Arrays.toString(myArray.arr));

        myArray.arr[0] = 10;
        // [10, 2, 3 ,4, 5]
        System.out.println(Arrays.toString(myArray.arr));

        myArray.insertData(2, 20);
        // [10, 2, 20, 3, 4, 5]
        System.out.println(Arrays.toString(myArray.arr));

        myArray.insertData(6, 60);
        // [10, 2, 20, 3, 4, 5, 60]
        System.out.println(Arrays.toString(myArray.arr));

        myArray.removeIndex(6);
        // [10, 2, 20, 3, 4, 5]
        System.out.println(Arrays.toString(myArray.arr));
    }
}

 

배열의 선언 방법 

배열 선언

타입[] 변수;
타입 변수[];​

배열 생성

타입[] 변수 = { 값0, 값1, 값2, 값3, … };
변수 = new 타입[] { 값0, 값1, 값2, 값3, … };


타입[] 변수 = new 타입[길이];

public class ArrayExample {
	public static void main(String[] args) {
            int[] a;        // 구성 요소의 자료형이 int형인 배열
            a = new int[];  // new를 사용하여 배열 본체를 생성한 뒤 배열 변수 a와 연결
            int[] a = new int[5];

            a[1] = 37;	     // a[1]에 37을 대입
            a[2] = 51;       // a[2]에 51을 대입
            a[4] = a[1] * 2;  // a[4]에 a[1] * 2 곧 74를 대입

            for (int i = 0; i < a.length; i++)  // 각 요소의 값을 표시
               System.out.println("a[" + i + "] = " + a[i]);
	}
}

 

참조

제로베이스 백엔드 강의 

https://devjun.tistory.com/88

Array (배열)