[자료구조] 동적 배열(ArrayList)

1. 개요

---

배열의 장단점은 다음과 같습니다.

장점

1. 항목 접근 속도가 빠르고 일정하다.
   배열의 원소들은 모두 연속된 메모리 위치에 저장되기 때문에 인덱스를 통해 가장 빠르게 원소를 참조하거나 변경할 수 있다.

단점

1. 사용하기 전에 배열 크기를 지정해야하고, 지정한 크기로 고정된다. 
   정해진 크기를 넘겨서 데이터를 저장하려 한다면, 더 큰 크기의 배열을 새로 할당받아 사용해야 한다.
2. 삽입/삭제가 힘들다.
   배열의 중간에 원소를 삽입/삭제할 경우, 나머지 원소들의 연속적인 순서를 맞추기 위해 삽입/삭제가 이루어진 위치 뒤의 모든 데이터들을 모두 한 칸씩 앞으로 당기거나, 뒤로 밀어야한다. 원소들을 모두 옮기는데 드는 시간복잡도는 O(n)이다.
3. 메모리를 한 덩어리로 차지하므로, 배열 크기가 클 경우 배열 전체를 위한 메모리를 할당받지 못하는 경우가 있다.

 

위와 같은 기본 배열의 단점을 해결하기 위한 자료구조가 동적 배열(Dynamic array)과 연결리스트(Linked list)입니다.

2. 동적 배열(Dynamic array)

---

동적 배열은 기본 배열의 단점을 보완한 자료구조로, 기본적으로 배열로 구현되기에 배열이 가지는 특징을 그대로 가집니다.
초기에 고정된 크기를 할당받으며 생성되고, 초기에 지정한 크기를 넘어서면 동적으로 크기를 늘린다는 특징을 가지고 있습니다.

[그림 1] 동적 배열의 용량 변화

동적 배열은 다음과 같은 과정으로 동작합니다.

1. 처음 동적 배열이 생성될 때, 일정한 Capacity를 갖고 할당된다.
2. 할당된 Capacity를 넘어서 원소가 추가되면, 기존 Capacity의 2배 크기로 배열을 새로 할당한 후, 기존 배열의 원소를 복사한다.

3. 동적 배열(Dynamic array) 구현

---

동적 배열을 구현하는 클래스는 할당된 배열을 가리키는 참조변수, Capacity 변수, Size 변수 세 가지 필드가 필요합니다.

 

구현해야할 메서드 목록은 다음과 같습니다.

1. Add
2. Insert
3. Clear
4. Contains
5. CopyTo
6. RemoveAt
7. RemoveRange
8. IndexOf
9. LastIndexOf
10. ToArray