[Data Structure] 배열

순차적 메모리 할당 방식이며 <인덱스, 원소> 쌍의 집합이다. 원소들이 모두 같은 타입, 같은 크기를 가진다.

 

인덱스: 순서를 나타내는 원소의 유한 집합이며 집합 내 상대적 위치를 식별하는데 사용된다. 인덱스 만으로 원하는 원소를 직접 접근하기에 내부 구현을 알 필요가 없다.(정보은닉)

 

메모리 표현

 

연속적인 메모리 주소를 배열에 할당한다.

1. 순차 사상: 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현한다.
2. 순차 표현: 순차 사상을 이용하여 데이터를 표현한다.

순차 사상의 특징으로 인해 빠르게 검색이 가능하다.

하지만 메모리의 크기를 할당하면 크기를 바꿀수 없다는 점과 삽입, 삭제가 다른 자료구조들에 비해 어렵다는 특징이 있다.

 

배열 추상 데이터 타입(ADT)

public class Array<E> {
    private Object[]
    a;
    public Array(int n) {
        a = new Object[n];
    }
    public E retrieve(int i) {
        return (E) a[i];
    }
    public void store(int i, E e) {
        a[i] = e;
    }
}

1차원 배열

<T> arr [] = new <T> [n]

n은 원소의 최대 수를 말하며 인덱스는 {0, 1, ---, n-1}이다.

2차원 배열

<T> arr [][] = new <T> [n][m];

n개의 행을 가지고 m개의 열을 가진다. 원소수는 n*m이며 원소는 arr[i][j]로 표현할 수 있다.

JAVA 배열

일정 수의 컴포넌트를 순차적으로 정렬시킨 것이며 원시 타입(int, boolean, String 등)과 객체 타입의 배열도 생성할 수 있다.

모든 배열은 생성될 때 배열 내부에 갖게 되는 데이터 필드가 있다.

1. length

배열의 원소 수를 나타낸다.

int arr [] = new int [10];
System.out.println(arr.length); // 10

2. clone

객체를 복제할 수 있다. clone의 특징은 똑같은 배열을 생성해내면서 arr와 arr_clone은 다른 객체를 가리킨다.

int arr[] = new int [10];
int arr_clone [] = arr.clone();

이와 반대로 다음 코드는 같은 객체를 가리키기에 arr의 원소를 수정하면 arr_copy의 원소도 함께 변경된다.

int arr [] = new int [10];
int arr_copy [] = arr;