[자료구조] 배열과 동적 배열 : 차이점과 선택 기준

배열 (Array)

메모리에 연속적으로 데이터를 저장하는 자료구조이다.

 

1. 배열의 구조

배열의 구조

 

 

2. 배열의 특징

• 모든 원소의 크기가 같아야 한다. (ex. int형 배열이면 모든 원소가 int여야 한다.)
• 인덱스(index)로 각 원소에 바로 접근할 수 있어 매우 빠르다. (O(1) 시간)
• 크기가 한 번 정해지면, 다시 바꾸기 어렵다. (배열의 한계)
• 배열의 처음이나 끝에서 삽입/삭제를 하는 경우, 관련된 값들을  다 한칸 씩 옆으로 밀어주거나 당겨줘야 한다.
  • 직접 구현해야 한다.

삽입/삭제 시

 

 

3. 배열의 인덱스

배열의 인덱스는 다음과 같이 계산이 된다.

arr[0] : X001 + (4Byte * 0) : X001

arr[1] : X001 + (4Byte * 1) : X005

arr[2] : X001 + (4Byte * 2) : X009

..

 

위에서 처럼 인덱스 번호만 알면, 한 번의 연산으로 한 번에 찾을 수 있다. (O(1) 시간)

 

 

---

 

동적 배열 (Dynamic Array)

데이터를 순차적으로 저장하고, 크기를 동적으로 조절 할 수 있는 배열 자료 구조이다. 

 

1. 동적 배열의 구조

동적 배열의 구조

• 기본적인 시각적 구조는 일반 배열과 동일하다. 하지만 동작 방식의 차이가 있다.
• 일반 배열을 감싼 객체 형태(클래스)로 구현되어 있다.

 

 

2. 동적 배열 특징

• 클래스 내부에 배열을 동적으로 사용할 수 있게 해주는 내부 로직들이 존재한다.
• 배열 크기가 고정되어있지 않고 필요에 따라 자동으로 증가(또는 감소) 합니다.
  • 보통 요소 수가 용량(Capacity)을 초과하면 2배로 확장됩니다.
• 일반 배열처럼 인덱스를 이용한 O(1) 시간의 빠른 접근이 가능합니다.
• 용량이 차면, 새로운 더 큰 배열을 할당하고, 기존 데이터를 복사합니다. (메모리 낭비를 줄일 수 있다. 다만 일부 남는 공간이 존재한다.)
• 동적 배열도 마찬가지로 삽입/삭제를 하는 경우, 관련된 값들을  다 한칸 씩 옆으로 밀어주거나 당겨줘야 한다. 
  • 일반 배열과 다르게 내부에서 제공하는 메서드를 이용하여, 간단하게 할 수 있다.

 

3. 동적 배열의 용량 증가

다음 로직을 통해 내부적으로 배열의 크기가 자동으로 늘어난다.

private int[] data;
private int size;
private int capacity;

• data : 실제 데이터가 저장될 일반 배열
• size : 현재 배열에 저장된 요소의 개수
• capacity : 배열의 용량 (배열의 크기)

 

public void add(int value) {
    // 배열이 가득 찼으면 용량을 늘린다
    if (size == capacity) {
        resize();  // 용량 늘리기
    }
    data[size++] = value; // 배열에 값 추가 후 size 증가
}

• resize() : 배열의 용량(크기)보다 저장할려는 요소의 개수가 더 많으면 늘려주는 메서드
• data[size++] = value : 일반 배열에 값을 할당

 

private void resize() {
    capacity *= 2; // 용량을 두 배로 증가
    int[] newData = new int[capacity];  // 새로운 배열 생성
    newData = Arrays.copyOf(data, size); // 기존 배열 데이터를 새 배열로 복사
    data = newData;  // data를 새 배열로 갱신
}

• resize() 메서드가 호출되면, 현재 배열의 총 크기를 2배로 늘린다.
• 새로 늘어난 용량을 이용하여, 새로운 배열을 생성한다.
• 기존 배열 데이터를 새 배열로 복사한 후, data를 갱신한다.

 

---

 

 

배열 (Array) vs 동적 배열 (Dynamic Array)

구분	배열	동적 배열
크기	고정 (생성 시 지정)	유동적 (자동 확장 가능)
메모리 구조	연속적, 고정 크기	내부는 일반 배열이지만 자동 재할당
삽입 시 확장	불가 (초기 크기 제한)	자동으로 용량 증가 (보통 2배)
접근 속도	O(1) (빠름)	O(1)
삽입/삭제 (중간)	O(n)	O(n)
삽입/삭제 (끝)	O(1) (공간 있을 경우)	O(1) 평균, O(n) 최악 (재할당 시)
메모리 효율성	낭비 없음 (필요한 만큼만 할당)	일부 남는 공간 존재 가능
언어 예	int[], String[] (Java)	ArrayList (Java)

 

 

 

---

 

 

각 선택 기준

 

언제 배열을 선택할까?

• 원소 개수가 정해져 있거나 변하지 않을 때
• 빠른 접근 속도가 필요할 때
• 메모리 사용량을 최소화하고 싶을 때

 

언제 동적 배열을 선택할까?

• 데이터 개수를 예측할 수 없을 때
• 배열을 자주 추가/삭제할 때
• 편의성과 코드 단순화가 중요한 경우 (메서드로 쉽게 관리 가능하다)