배열(Array)이란?
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.
대부분의 프로그램 언어에서 동일 타입의 데이터를 저장한다. 예를 들어 배열이 "int"타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없다.
배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.
배열(Array) 특징
- 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조
- 연속적인 메모리 공간에 순차적으로 데이터를 저장
- 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다.
- 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다.
- 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다.
배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있다. - 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다.
배열(Array) 주요 메서드
- length() : 배열의 길이를 반환
- clone() : 배열을 복제
- equals() : 배열이 다른 배열과 동일한지 여부를 반환
- fill() : 배열의 모든 요소를 지정된 값으로 설정
- sort() : 배열의 요소를 정렬
- binarySearch() : 정렬된 배열에서 지정된 요소를 검색
- toString() : 배열의 내용을 문자열로 반환
- copyOf() : 배열의 일부 또는 전체를 복사하여 새로운 배열을 생성
- asList() : 배열을 List로 변환
배열(Array) 장단점
장점
- 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있다.
- 데이터의 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리속도 면에서 좋다.
- 간단하고 사용하기 쉽다.
- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.
단점
- 삽입과 삭제가 어렵고 오래 걸린다.
- 원소를 삽입하거나 삭제할 경우, 다음 항목의 모든 요소를 이동시켜야 한다. (연속된 메모리 공간)
- 이를 위한 연산작업이 수행되어 비효율적이다.
- 자료의 수에 비례하여 성능이 떨어지게 된다.
- 배열의 크기를 바꿀 수 없다.
- 크게 잡을 경우 메모리가 낭비된다.
- 작게 잡을 경우 그 이상의 자료를 저장하지 못한다.
- 메모리의 재사용이 불가능하다.
- 배열은 초기 사이즈만큼의 메모리를 할당받아 사용하기
- 데이터의 존재 유무와 관계없이 그 만큼의 메모리를 사용한다.
- 배열 자체를 제거하지 않는 이상 삭제된 공간의 메모리 재사용은 불가능하다.
- 삽입과 삭제가 어렵고 오래 걸린다.
배열(Array) 사용 경우
- 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
- 다차원 데이터를 다룰 때
- 삽입, 삭제 작업이 적을 때 사용하면 좋음
- 배열에 저장된 데이터를 검색하는 작업이 많을 때( 인덱스로 빠르게 검색 가능)
배열(Array) 시간복잡도
- 검색(Search): 배열에서 특정 요소를 검색하는 시간 복잡도는 O(n)이다. 배열의 모든 요소를 순차적으로 비교해야 하기 때문이다. 만약 배열이 정렬되어 있다면 이진 검색을 사용하여 시간 복잡도를 O(log n) 로 개선할 수 있다.
- 삽입(Insertion): 배열에서 특정 위치에 요소를 삽입하는 시간 복잡도는 O(n)이다. 삽입 위치 이후의 모든 요소를 이동시켜야 하기 때문.
- 삭제(Deletion): 배열에서 특정 위치의 요소를 삭제하는 시간 복잡도는 O(n)이다. 삭제 위치 이후의 모든 요소를 이동시켜야 하기 때문.
복습해보기
