동적 배열 (Dynamic Array)
데이터를 순차적으로 저장하고, 크기를 동적으로 조절 할 수 있는 배열 자료 구조이다. 일반적인 배열은 선언 시 크기가 고정되지만, 동적 배열은 데이터의 삽입/삭제에 따라 자동으로 크기를 확장하거나 축소할 수 있습니다.
1. 동적 배열의 구조
- 변수 : 실제 메모리 공간의 주소를 담고 있는 변수입니다.
- 크기(Size) : 현재 배열에 저장된 요소의 개수입니다.
- 용량(Capacity) : 배열이 재할당 없이 저장할 수 있는 최대 요소 수입니다.
2. 동적 배열의 특징
- 일반 배열을 감싼 객체 형태(클래스)로 구현되어 있으며, 동적으로 사용할 수 있게 해주는 내부 로직들이 존재한다.
- 배열 크기가 고정되어있지 않고 필요에 따라 자동(내부로직)으로 증가(또는 감소) 합니다.
- 보통 요소 수가 용량(Capacity)을 초과하면 2배로 확장됩니다.
- 일반 배열처럼 인덱스를 이용한 O(1) 시간의 빠른 접근이 가능합니다.
- 용량이 차면, 새로운 더 큰 배열을 할당하고, 기존 데이터를 복사합니다. (메모리 낭비를 줄일 수 있다. 다만 일부 남는 공간이 존재한다.)
연결 리스트 (Linked List)
데이터를 순서대로 연결한 자료구조이다.
1. 연결 리스트의 구조
2. 연결 리스트 특징
- 각 데이터는 `데이터 + 다음 데이터 주소(포인터)`를 가지고 있다.
- 메모리에 흩어져 저장될 수 있다.
- 웝소의 삽입/삭제가 쉽다. (각 값의 포인터가 가지고 있는 참조값을 변경)
3. 동적 배열 vs 연결 리스트
| 비교 항목 | 동적 배열 (Dynamic Array) | 연결 리스트 (Linked List) |
| 메모리 구조 | 연속된 메모리 블록 | 노드마다 흩어진 메모리, 포인터로 연결 |
| 접근 속도 | O(1) - 인덱스로 바로 접근 가능 | O(n) - 앞에서부터 순차 탐색 |
| 삽입/삭제 (중간) | O(n) - 이동 필요 | O(1) - 포인터만 조정(위치를 알고 있는 경우) |
| 삽입/삭제 (끝) | O(1) - (단, 재할당 발생 시 O(n)) | 단일 연결 리스트는 O(n), 이중 연결 리스트는 O(1) |
| 메모리 사용 | 남는 공간이 생길 수 있음 | 포인터 공간이 추가로 필요 |
| 메모리 재할당 | 배열 크기 초과 시 전체 복사 필요 (비쌈) | 없음 – 필요할 때마다 노드 추가 |
| 캐시 효율성 | 높음 – 메모리가 연속적이어서 캐시 적중률이 높다 | 낮음 – 메모리가 분산되어 있음 |
'자료구조' 카테고리의 다른 글
| [자료 구조] Stack과 Queue (0) | 2025.04.30 |
|---|---|
| [자료구조] 배열과 동적 배열 : 차이점과 선택 기준 (2) | 2025.04.29 |
