[APS] 005 : 자료구조 - 동적 배열

동적 배열

---

동적 배열(Dynamic Array)

 - 동적 할당(dynamic allocate)를 통해, 크기를 변경할 수 있도록 한 배열의 일종

• index를 이용한 데이터 접근이나 탐색과 같은 배열의 형태와 장점을 그대로 유지
• 내부적으로 배열로 구현되는 경우가 많아 캐시 메모리 적중률 이 높음

◆ 동적 할당(dynamic allocate)
컴파일 단계에서 크기를 미리 정해주는 배열과는 달리, 런타임 단계에서 크기에 따라 메모리를 가변적으로 배치하는 것을 의미한다. Java는 모든 객체의 메모리값을 JVM이 동적 할당해준다.

---

동적 배열과 복잡도

1. 시간복잡도

 - 접근 / 변경 : O(1)

• 인덱스를 이용해 해당 데이터에 바로 접근하고 변경할 수 있음

 - 삽입 / 삭제 O(1) ~ O(n)

• 동적배열의 크기를 초과하지 않는다면 배열과 동일함 (맨끝 O(1) / 중간 O(n))
• 만약 사이즈를 초과하면 새로운 배열을 할당한 뒤 값을 복사하는 과정이 일어나므로 O(N) 소요

2. 공간복잡도

 - O(N) : 동적 배열은 별다른 추가 메모리(Overhead)공간을 필요로 하지 않음

---

---

Java 동적 배열

---

ArrayList / Vector

- Java는 List 인터페이스를 상속받는 ArrayList 와 Vector 클래스로 동적 배열을 구현하고 있음

List<Integer> list = new ArrayList<>();
List<Integer> list2 = new Vector<>();
// 1차원 동적 배열의 선언

List<ArrayList<Integer>> ArrayList = new ArrayList<>();
// 다차원 (예시에선 2차원) 동적 배열의 선언

Collections.sort(list); // 정렬

- 내부적으로 Object 배열을 사용하며, 기존 배열 크기를 넘어서면 더 큰 배열을 선언하여 할당

※ ArrayList는 배열의 크기가 커져야 하는 경우 내부의 grow() 메소드를 호출하여 1.5배 크기의 배열을 재할당하고 데이터를 복사한다. 단, 크기가 작아져야 할 경우엔 자동으로 재할당 되지 않으며, trimToSize()등으로 줄여줘야 한다.

---

- 최종 수정일 : 23-04-11

- 이 글은 지속적으로 수정되고 있으며, 오타나 잘못된 정보에 대한 사항은 댓글로 남겨주시면 감사하겠습니다.