동적배열은 배열의 크기가 가변으로 변할 수 있는 배열입니다.
따라서 실행시간에 그 크기가 결정됩니다.
그러나, 동적배열도 배열이기 때문에 배열의 가장 중요한 특징은 일치합니다
그 특징은 "메모리 시작주소를 기준으로 연속적으로 할당되어 있다" 라고 볼 수 있습니다.
어떻게 메모리에 연속적으로 할당될 수 있죠?
다음과 같은 경우를 볼까요?
0x000000 USER[0]
0x000001 USER[1]
0x000002 USER[2]
0x000003 NAME[0]
0x000004 NAME[1]
0x000005
0x000006
0x000007
0x000008
이같은 경우에 USER[3] 이 필요하다면 어쩌죠?
NAME[0], NAME[1] 의 주소를 뒤로 옮기고 USER[3] 을 저장해야하나요?
아닙니다.
예시가 저럴뿐 저 사이에 얼마나 많은 메모리가 사용되고 있는지 모르는데, 그처럼 어마무시한 짓은 할 수 없습니다.
따라서 아래와 같은 순서로 진행합니다
1. 기존 USER 를 복사
0x000000 USER[0]
0x000001 USER[1]
0x000002 USER[2]
0x000003 NAME[0]
0x000004 NAME[1]
0x000005 USER[0]
0x000006 USER[1]
0x000007 USER[2]
0x000008
2. 새로운 USER[3] 을 추가
0x000000 USER[0]
0x000001 USER[1]
0x000002 USER[2]
0x000003 NAME[0]
0x000004 NAME[1]
0x000005 USER[0]
0x000006 USER[1]
0x000007 USER[2]
0x000008 USER[3]
3. 기존 USER 제거
0x000000
0x000001
0x000002
0x000003 NAME[0]
0x000004 NAME[1]
0x000005 USER[0]
0x000006 USER[1]
0x000007 USER[2]
0x000008 USER[3]
그럼 배열이 하나 추가될때마다 계속 복사하나요?
생각만해도 비효율적인 속도가 느껴지나요?
몇개가 추가될지 모르는데, 추가될때마다 복사하고 기존껏을 제거한다면, 시간복잡도가 상당해질 것이 예측이 됩니다.
그래서 동적배열의 경우 SIZE * 2 씩 미리 메모리 영역을 할당해둡니다.
0x000000 USER[0]
0x000001 USER[1] 을 위해 미리 차지해둠
0x000002 NAME[0]
0x000003 NAME[1]
이같은 경우가 있다면 USER[1] 을 추가하는 순간에는 복사 및 기존제거 행위는 일어나지 않습니다.
저 상황에서 USER[2] 를 추가한다면,
0x000000
0x000001
0x000002 NAME[0]
0x000003 NAME[1]
0x000004 USER[0]
0x000005 USER[1]
0x000006 USER[2]
0x000007 USER[3] 을 위해 미리 차지해둠
0x000008
0x000009
마찬가지로 이런 상황에서 USER[3] 을 추가한다면
0x000000
0x000001
0x000002
0x000003 NAME[0]
0x000004 NAME[1]
0x000005
0x000006
0x000007
0x000008 USER[0]
0x00009 USER[1]
0x000010 USER[2]
0x000011 USER[3]
0x000012 USER[4] 를 위해 미리 차지
0x000013 USER[5] 를 위해 미리 차지
0x000014 USER[6] 를 위해 미리 차지
0x000015 USER[7] 를 위해 미리 차지
이렇게 동작한다고 보시면 됩니다.
'BackUp (관리중지) > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] 배열 (0) | 2021.04.28 |
|---|