데이터 구조에서 ADT 배열 표현 완벽 정리

기본 개념

ADT는 추상 데이터 타입(Abstract Data Type)을 의미합니다.

배열이 ADT로 정의되는 이유는 동일한 순서대로 연속된 요소들을 저장할 수 있기 때문입니다. 또한 인덱스나 위치를 통해 특정 요소에 직접 접근할 수 있다는 특징도 있습니다.

배열이 '추상적'이라고 불리는 이유는 String, int, Person 등 저장하려는 데이터 타입에 구애받지 않고 다양하게 활용될 수 있기 때문입니다.

int[] arrA = new int[1];
String[] arrB = new String[1];
Person[] arrC = new Person[3]; // Person은 미리 정의된 클래스로 취급됩니다

장점

• 인덱스를 통해 요소에 빠르게 무작위(random) 접근할 수 있습니다.
• 메모리 효율성이 매우 뛰어납니다. 실제 데이터를 저장하는 데 필요한 메모리 외에 추가로 소모되는 메모리가 거의 없습니다.

단점

• 요소의 삽입과 삭제 작업이 상대적으로 느립니다.
• 배열의 크기를 생성 시점에 미리 지정해야 하며, 이후에는 변경할 수 없어 고정적(정적)입니다.

ADT 리스트의 배열 기반 구현

아래는 자바로 작성한 배열 기반 리스트 구현 예제입니다. 최대 크기를 상수로 선언하고, 리스트 항목을 담는 배열과 현재 항목 수를 함께 관리하는 구조입니다.

public class ListArrayBased implements ListInterface {
    private static final int MAX_LIST1 = 50;
    private Object items1[];
    // 리스트 항목을 저장하는 배열
    private int numItems1;
    // 리스트에 포함된 항목의 개수

    public ListArrayBased() {
        items1 = new Object[MAX_LIST1];
        numItems1 = 0;
    } // 기본 생성자 끝
}

이처럼 배열 기반 구현은 구조가 단순하고 접근 속도가 빠른 반면, 크기가 고정되어 있어 유연성이 떨어진다는 점을 기억해 두면 좋습니다.