📌 배열
배열(Array)은 일반적으로 동일한 자료형의 모음으로 구성된 선형 자료 구조이다.
각 요소는 하나 이상의 인덱스 또는 키로 식별되며, 이러한 인덱스 또는 키의 모음은 튜플일 수 있다.
다른 자료형의 데이터를 모아 저장하는 프로그래밍 언어도 드물게 존재한다.
이 때, 다른 자료형의 데이터를 저장하는 배열을 레코드라고 부른다.
💡 인덱스는 왜 0번 부터?
1번부터 순서를 매기는 일반적인 방식과 다르게 컴퓨터에서 사용하는 인덱스는 0번부터 순서를 매긴다.
0번부터 순서를 매기는 이유는 시작 위치를 기준으로 몇 칸 떨어진 곳에 있다는 식으로 접근하기 때문이다.
💡 필요성
배열을 활용하면 같은 타입의 데이터를 효율적으로 관리할 수 있다.
또한 코드의 가독성이 높아지며, 반복 작업을 간단하게 처리할 수 있게 된다.
💡 특징
- 동일한 데이터 유형을 저장한다.
- 이름으로 참조되어질 수 있다.
- 저장하는 데이터들의 메모리가 연속적으로 할당된다.
이 때, 각 데이터는 메모리의 낮은 주소에서 높은 주소로 할당된다. - 삽입 / 삭제는 배열의 맨 끝에서만 이루어진다.
배열 중간에 삽입 / 삭제를 지원하지 않는 이유
배열 중간에 다른 요소를 삽입하거나 삭제하기 위해서는 삽입 / 삭제를 원하는 위치부터 끝까지 모든 요소를 왼쪽 혹은 오른쪽으로 한 칸씩 밀어내는 작업이 필요하다.
해당 작업은 배열의 요소 개수에 비례해서 동작 횟수가 늘어나기 때문에 시간 복잡도는 O(n)이다.
해당 작업이 빈번하게 일어나야 하는 경우, 애초에 배열을 사용하기에 적합한 상황이 아니라는 뜻이므로 지원하지 않는다.
💡 정적 배열과 동적 배열
정적 배열
정적 배열은 선언할 때 배열의 크기가 고정되는 배열이다.
배열의 크기는 컴파일 시간에 결정되며 한 번 선언된 크기는 변경할 수 없다.
동적 배열
동적 배열은 런타임 도중에 동적으로 크기를 변경할 수 있는 배열이다.
정적 배열과 다르게 배열의 크기를 조절할 수 있으므로 유연한 객체의 추가 / 삭제가 가능하다.
💡 다차원 배열
2차원 이상의 배열 또한 모든 요소들이 연속된 메모리에 할당된다.
2차원 배열의 경우, 현재 행의 마지막 요소 뒤의 요소는 다음 행의 첫번째 요소가 된다.
다차원 배열의 요소를 1차원 배열처럼 접근할 수도 있다.
💡 연산 시간 복잡도
| 평균적인 경우 (average case) | 최악의 경우 (worst cast) | |
|---|---|---|
| 읽기 (read) | O(1) | O(1) |
| 삽입 (insert) | O(n) | O(n) |
| 삭제 (delete) | O(n) | O(n) |
| 탐색 (search) | O(n) | O(n) |
💡 장 / 단점
장점
- 인덱스를 통해 원하는 위치의 데이터에 빠르게 접근 가능하다.
- 연속된 메모리 공간을 할당하기 때문에 CPU Cache를 통해 같은 배열에 있는 다른 데이터에 빠르게 접근 가능하다.
단점
- 배열을 선언한 이후 크기를 동적으로 변경할 수 없다. (정적 배열 한정)
- 메모리의 재사용이 불가능하다. (정적 배열 한정)
- 배열 중간에 요소를 삽입 / 삭제할 수 없다.
- 연속된 메모리를 할당해야 하기 때문에 할당에 제약이 걸린다.
Reference
배열 - 위키 백과
배열 - 정보통신기술용어해설
배열 - C# Learn
[자료구조] 배열(Array), 정적 배열(Static Array) vs 동적 배열(Dynamic Array)
배열(Arrays) - 위키독스
C언어 기초 가이드 STEP 1: 배열
☕ JAVA 배열(Array) 완벽 다루기 가이드
[C언어]C언어 기초 문법 정리[배열, 포인터]
