: 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 자료구조이다.
- 데이터가 컴퓨터 메모리에 저장될 때 저장 시작 위치부터 빈자리 없이 순서대로 저장된다.
→ 데이터의 시작 위치와 원소의 크기를 안다면 특정 원소의 위치를 알 수 있다.
- 자료의 논리적인 순서와 물리적인 순서가 일치하는 구현 방식이라고 할 수 있다.
- 구현이 비교적 간단하다. (배열을 사용하면 된다.)
- 크기가 고정되어있다.
- 인덱스를 활용해 랜덤 엑세스가 가능하다.
- 논리적인 순서와 물리적인 순서가 같다.
삽입과 삭제시, 물리적인 순서와 논리적인 순서를 맞추기 위한 데이터 이동이 발생한다. → 오버해드가 야무지다.
- 배열 이름 - array name
배열 그 자체와는 별개로 배열의 이름 지칭(배열 선언)
- 배열 변수 - array variable
배열 전체 이름을 갖는 변수 처럼 활용
- 배열 요소 - array element
배열의 각 성분 원소들
- 배열 크기 - array size
배열 요소의 갯수
- 배열 인수/키/인덱스/첨자 - array index
특정 요소를 참조하는 수단, 통상적으로 정수이며 0부터 시작한다.
4번 인덱스에 숫자 7를 삽입할 것이다.
삽입이 끝난 후 3번 인덱스의 값을 삭제할 것이다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 삽입 전 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 삽입 중 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 삽입 후(삭제 전) | 1 | 2 | 3 | 7 | 4 | 5 | 6 |
| 삭제 중 | 1 | 2 | 7 | 4 | 5 | 6 | |
| 삭제 후 | 1 | 2 | 7 | 4 | 5 | 6 |
- 삽입 하기 위해 3번 인덱스를 비워야한다.
- 4번 인덱스를 비우려면 3번 인덱스 기준으로 뒤에있는(5, 6, 7 인덱스) 모든 데이터의 인덱스를 기준으로 1씩 뒤로 이동한다.
오버헤드가 발생한다.
- 2번 인덱스의 값을 제거한다.
- 2번 인덱스의 빈공간이 생겼으므로 3번 인덱스 기준으로 뒤에 있는 데이터는 1씩 앞으로 이동한다.
- 배열의 맨 앞에 삽입/삭제하는 경우 :
O(n) - 배열의 맨 뒤에 삽입/삭제하는 경우 :
O(1) - 배열의 중간에 삽입/삭제하는 경우 :
O(n)
- 인덱스로 랜덤 엑세스가 가능하다.
시간 복잡도
O(1) - 하지만 인덱스 속 값을 모르면 순차적으로 탐색해야 하므로
시간 복잡도
O(n)
- 인덱스를 가지고 있어 바로 접근 가능 (시간복잡도
O(1))자료구조의 크기가 클수록 이득이다.
- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.
- 삽입과 삭제가 어렵고 오래 걸린다.
원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다.
- 크기를 변경할 수 없다.
크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야 함.
- 크기를 변경할 수 없어 공간 낭비가 발생할 수 있따.
자료구조의 크기를 100으로 선언하고 10개만 사용하면 나머지 90개의 메모리 낭비가 생긴다.
- 데이터 개수가 확실하게 정해져 있을 때
- 데이터 삽입/삭제 빈도가 적을 때
- 검색이 빈번하게 일어날 때