배열(Array)

배열(Array) : 각각의 개별 항목을 위치 번호로 참조할 수 있도록 항목을 번호순으로 배열하는 데이터 구조입니다.

    - 많은 수의 데이터를 다룰 때 사용하는 자료구조입니다.

    - 각 데이터를 인덱스와 1:1 대응하도록 구성됩니다.

    - 데이터가 메모리 상에 연속적으로 저장됩니다.

 

Array의 예시

 

데이터구조(Data Structure) : 하나의 단위로 취급될 수 있도록 여러 개의 데이터 항목을 뭉쳐서(chunked) 구성됩니다.

길이(Length) : 배열에서 항목들의 수 입니다.

기본 자료형(Base Type) : 배열의 개별 항목 자료형입니다.

인덱스(Index) : 배열에서 항목의 위치 번호 입니다.

 

 

배열(Array)의 장점

- 인덱스를 이용하여 데이터에 빠르게 접근 가능합니다.

 

 

 

    * 더 나아가기(OS)

    배열은 Spatial locality(공간적 지역성)을 갖습니다.

    Spatial Locality(공간적 지역성) : 프로그램이 특정 메모리에 접근한 후, 근접한 메모리 위치에 다시 접근할 확률이 높다는 개념입니다.

    따라서, 배열(Array)은 연속적인 메모리 공간에 데이터를 저장하므로, 한 번에 여러 개의 배열 요소에 접근할 수 있고, 이 근접한 메모리     위치에 접근하는 경우가 많습니다. 이는 CPU 캐시와 같은 하드웨어 수준에서의 메모리 접근 속도 향상을 도와줄 수 있습니다.

       ex) 배열이 데이터를 연속적으로 저장하고 인덱스를 사용하여 접근하는 특성에 기인한 것입니다.

 

 

배열(Array)의 단점

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

    * 미리 최대 길이를 정해서 생성해야 합니다.

    * 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성해야합니다.

    * 데이터 삭제 시 인덱스를 유지하기 위해 빈 공간을 유지해야합니다.

    * 배열의 크기는 동적이지 않고 고정되어있습니다.

    (So, 동적인 배열 ArrayList가 있습니다.)

 

 

 

2차원 배열 : 배열을 요소를 직사각형 격자(grid)에 배치하는 것입니다.

구성 요소

행(row), 열(column)

5 of row, 7 of column

2차원 배열 변수 선언

int[][]  A;
A = new int[5][7];

 

 

Array 메소드

asList(T... a) : 가변 인자를 통해 배열 a를 리스트로 변환합니다.

copyOf(T[] original, int newLength) : 배열 original의 일부 요소를 새로운 배열로 복사하여 반환합니다. 복사할 길이(newLength)를 지정할 수 있습니다.

sort(T[] a) : 배열 a를 오름차순으로 정렬합니다.

fill(T[] a, T val) : 배열 a의 모든 요소를 특정 값(val)으로 채웁니다.

equal(T[] a, T[] b) : 두 배열 a와 b가 같은지 여부를 반환합니다.

deepEquals(Object[] a, Object[] b) : 다차원 배열 a와 b를 깊은 비교(deep comparison)하여 같은지 여부를 반환합니다.

binarySearch(T[] a, T key) : 배열 a에서 특정 키(key)를 이진 검색을 통해 찾아 해당 인덱스를 반환합니다.(주의! 배열이 정렬된 상태에서만 사용가능합니다.)

toString(T[] a) : 배열 a를 문자열로 변환하여 반환합니다.

hashCode(T[] a): 배열 a의 해시 코드를 계산하여 반환합니다.

 

 

시간 복잡도(Time Complexity)

삽입(Insertion) : O(n)

삭제(Deletion) : O(n)

접근(Access) : O(1)

할당(Allocation) : O(1)

검색(Search) : O(n)

 

 

 

Reference

- Chater 3. Array, Introduction to Programming Using Java, Eighth Edition (David J. Eck)