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

동적 배열

---

동적 배열

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

일반적인 자료구조에서 리스트(list) 라고 하면 대부분 동적 배열을 의미

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

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

---

동적 배열과 복잡도

시간복잡도

접근 / 변경 : O(1)

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

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

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

공간복잡도

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

---

Java 동적 배열

---

ArrayList / Vector

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

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

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

 

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

• 기본적으로 할당되는 배열의 크기는 10
• 배열의 크기가 부족하면 내부의 grow() 메소드를 호출하여 1.5배 크기의 배열을 재할당하고 데이터를 복사
• 크기가 여유로울 때 자동적으로 크기를 줄이지는 않음

Vector은 멀티스레드 환경에서 사용할 수 있게 동기화를 지원하는 대신 연산 속도가 ArrayList에 비해 느리기 때문에 APS에선 일반적으로 ArrayList를 사용

※ 사실 Vector은 컬렉션 프레임워크가 나오기 전에 사용되었던 동적 배열으로, 현재는 호환성을 위해 남겨둔 사장된(deprecated)자료구조이다. 동기화 문제도 지금은 Collections.synchronizedList(List<E> list) 메서드로 동기화 리스트를 따로 만드는 방식으로 해결하므로, 가급적 사용하지 말자.

 

유용한 메서드

삽입

List<Integer> list = new ArrayList<>();

// boolean add(E e) : 요소 맨 끝에 삽입
list.add(1);

// void add(int index E element) : 특정 위치에 요소 삽입
list.add(0, 2);

// 결과 : [2, 1]

특정 위치에 삽입할 경우, 기존 요소들을 모두 한칸씩 뒤로 이동한 후 삽입

 

삭제

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(4);

// E remove(int index) : 특정 인덱스 삭제
list.remove(0);

// boolean remove(Object O) : 특정 요소 삭제
list.remove(Integer.valueOf(4));

// 결과 : []

list.add(1);
list.add(2);

// void clear() : 모든 요소 삭제
list.clear()

// 결과 : []

객체를 담은 동적배열의 경우, 특정 요소를 삭제할 수 있다.

정수를 사용하는 경우에는 Integer와 같은 래퍼클래스를 사용해야 오류가 나지 않는다(index로 인식하기 때문)

 

조회

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(4);

// E get(int index) : 특정 인덱스의 요소 조회
int ans = list.get(0);

// int indexOf(Object o) : 특정 값의 인덱스 반환
int idx = list.indexOf(4);

// boolean contains(Object o) : 특정 값 포함 여부 확인
boolean isContain = list.contains(1);

// int size() : 리스트 크기 반환
int size = list.size();

System.out.println(ans + " " + idx + " " + isContaion + " " + size);
// 결과 : "1 1 true 2"

 

수정

List<Integer> list = new ArrayList<>();
list.add(1);

// E set(int index, E element) : 특정 인덱스의 요소 수정
int ans = list.set(0,3)
// 결과 : [3]

System.out.println(ans);
// 결과 : "1" (이전값 반환)

 

그외

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(4);

// void trimToSize() : size에 맞춰 빈공간 제거
list.trimToSize() // 이제 size는 10이 아닌 2

// Object[] toArray() : 리스트를 배열로 반환
Integer[] arr = list.toArray(new Integer[0]);

System.out.println(ans + " " + idx);
// 결과 : "1 1"

// Arrays.asList(arr) : 배열을 리스트로 변환
// 불변객체가 형성
// 가변 리스트는 new ArrayList<>(Arrays.asList(arr));

제네릭 문제등으로 실전에선 for문을 더 많이 사용하는 느낌

---

- 최종 수정일 : 25-03-20

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