배열(Array) : 각각의 개별 항목을 위치 번호로 참조할 수 있도록 항목을 번호순으로 배열하는 데이터 구조입니다.
- 많은 수의 데이터를 다룰 때 사용하는 자료구조입니다.
- 각 데이터를 인덱스와 1:1 대응하도록 구성됩니다.
- 데이터가 메모리 상에 연속적으로 저장됩니다.
데이터구조(Data Structure) : 하나의 단위로 취급될 수 있도록 여러 개의 데이터 항목을 뭉쳐서(chunked) 구성됩니다.
길이(Length) : 배열에서 항목들의 수 입니다.
기본 자료형(Base Type) : 배열의 개별 항목 자료형입니다.
인덱스(Index) : 배열에서 항목의 위치 번호 입니다.
배열(Array)의 장점
- 인덱스를 이용하여 데이터에 빠르게 접근 가능합니다.
* 더 나아가기(OS)
배열은 Spatial locality(공간적 지역성)을 갖습니다.
Spatial Locality(공간적 지역성) : 프로그램이 특정 메모리에 접근한 후, 근접한 메모리 위치에 다시 접근할 확률이 높다는 개념입니다.
따라서, 배열(Array)은 연속적인 메모리 공간에 데이터를 저장하므로, 한 번에 여러 개의 배열 요소에 접근할 수 있고, 이 근접한 메모리 위치에 접근하는 경우가 많습니다. 이는 CPU 캐시와 같은 하드웨어 수준에서의 메모리 접근 속도 향상을 도와줄 수 있습니다.
ex) 배열이 데이터를 연속적으로 저장하고 인덱스를 사용하여 접근하는 특성에 기인한 것입니다.
배열(Array)의 단점
- 데이터의 추가/삭제가 번거로운 편입니다.
* 미리 최대 길이를 정해서 생성해야 합니다.
* 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성해야합니다.
* 데이터 삭제 시 인덱스를 유지하기 위해 빈 공간을 유지해야합니다.
* 배열의 크기는 동적이지 않고 고정되어있습니다.
(So, 동적인 배열 ArrayList가 있습니다.)
2차원 배열 : 배열을 요소를 직사각형 격자(grid)에 배치하는 것입니다.
구성 요소
행(row), 열(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)
'Computer Science > Data Structure' 카테고리의 다른 글
힙(Heap) (0) | 2023.04.18 |
---|---|
연결 리스트(Linked List) (0) | 2023.04.18 |
해시 테이블(Hash Table) (0) | 2023.04.14 |
큐(Queue) (0) | 2023.04.13 |
스택(Stack) (0) | 2023.04.13 |