배열
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이에요. (아래 그림 참고)
*배열과 리스트는 다른 자료구조에요. 내부 구현 방식과 사용법이 달라요.
특징
- 동일한 데이터 유형을 요소로 가져요. (대부분 프로그래밍 언어에서)
- 배열의 각 요소에 접근하는 시간은 O(1)로 모두 동일해요.
- 연속된 메모리에 단일 블록화해서 데이터를 저장해요.
- 실제 메모리 상에 물리적으로 데이터가 순차적으로 저장돼요.
- 그러므로 데이터에 순서가 있어요. index가 존재하기 때문에 인덱싱 및 슬라이싱이 가능해요.
장점
1. 인덱스를 통해 빠르게 데이터에 접근 가능
2. 구현이 간단하고 직관적
3. 기록 밀도가 1로, 공간 낭비가 적어요.
4. 다차원 배열 표현 가능
단점
1. 배열 선언시 사이즈를 미리 지정해야 함(정적 메모리, 배열 크기 변경 불가)
-> 배열의 크기를 미리 알 수 없을 때 불리함
2. 중간 특정 요소를 삽입 및 삭제하는 경우 시간이 오래 걸림
3. 대량의 데이터 다룰 때 불리
시간 복잡도
사용하는 경우
- 순차적 데이터(담기는 값보다는 순서가 중요할 때)
- 다차원 데이터를 다룰 때
- 특정 요소에 대한 접근이 빨라야 할 때
- 데이터 사이즈가 자주 바뀌지 않으며, 예상되는 요소의 추가 및 삭제가 적을 때
리스트와의 차이
위 그림에서, 배열 = 순차 리스트 / 리스트 = 연결 리스트(링크드 리스트)
좀 더 자세히..
구성
배열의 각각 요소의 값을 요소(element)라고 하고, 요소의 배열상 위치를 가리키는 숫자를 인덱스(index)라고 해요.
배열 예시
동작 원리
접근(access)
O(1)의 시간 복잡도. 찾고자 하는 값의 인덱스만 안다면, 인덱스로 바로 접근이 가능하기 때문이에요.
참고로, C언어에서는 배열의 이름은 곧 배열의 시작 주소(0번째 요소의 주소)에요. 그렇기 때문에, 인덱스가 3인 요소의 주소에 첫 주소 + (4(번째) * 4(int형이니까))byte를 더해주면 4번째 요소의 주소가 되겠죠?
검색(search)
O(n)의 시간 복잡도. 순차검색 방식으로, 인덱스를 모른다면, 원하는 값을 찾기 위해 배열을 앞에서부터 차례대로 다 찾아봐야 해요. 예를 들어, n개의 배열에서 A[n]번째 값을 찾는다면, n번째에 찾게 되겠죠. (찾는 값이 없는 경우도 다 찾게 되겠죠)
추가(add) & 제거(remove)
O(n)의 시간 복잡도. 배열의 공간이 가득 차 있는 상태가 아니라면, 끝자리에 데이터를 추가(append)하는 경우는 간단하고 시간도 O(1)이겠죠.
그러나 중간에 요소가 추가된다면, 그 뒤의 요소들의 인덱스는 모두 1씩 증가해야 해요. 그러므로 최악의 경우(맨 앞, 0번째 요소 자리에 추가하는 경우) 0번 째 ~ n번 째 인덱스 모두의 주소가 1씩 추가해야 하므로 O(n)의 시간이 걸려요.
삭제의 경우도 마찬가지에요.
동작 원리에 대해 더 자세하게 알아보고 싶으시다면, 자료구조 기초 - 배열 이 분의 글을 읽어보세요.
출처
