연속된 자료구조
- 모든 원소를 단일 메모리 청크(chunck)에 저장
- 큰 사각형이 단일 메모리 청크를 나타내고, 안쪽 작은 사각형은 원소가 저장된 메모리 공간을 의미
- 각각의 원소는 같은 타입(type)이고, 데이터 접근 시 주소를 이용해서 접근하고 O(1)이 걸린다.
- ex) 배열
정적 배열 vs 동적 배열
- 정적 배열은 스택(stack) 영역에 할당되어 함수가 종료되면 자동으로 해제된다.
- 동적 배열은 힙(heap) 영역에 할당되어 사용자가 직접 해제하기 전까지 유지된다.
int arr[size];
int* arr = (int*)malloc(size*sizeof(int));
int* arr = new int[size];* 배열과 같은 연속된 자료 구조는 원소끼리 인접되어 있어 접근 시 원소 몇 개도 같이 캐시(cache)로 가져온다.
어떤 연산에 점근적 시간 복잡도 계산을 영향을 주지 않고, 실제 동작에서 연속된 원소에 빠르게 접근할 수 있다.
배열에서 모든 원소에 순차적으로 접근하는 경우, 캐시 지역성(cache locality)가 좋다.
연결된 자료구조
- 노드(node)라는 여러 개의 메모리 청크에 데이터를 저장 : 서로 다른 메모리 위치에 데이터가 저장
- 각각의 노드는 저장할 데이터(Data)와 다음 노드를 가리키는 포인터(next)를 가짐
- 그래서 i번째 원소에 접근하려면 연결리스트 내부를 i번 이동해야 하고(노드에 비례), O(n) 소요
- ex) 연결리스트
연결리스트에 새로운 원소 추가 방법
- next 포인터를 수정 후 해당 노드의 메모리 할당을 해제
- 연결리스트에는 원소가 메모리에 연속적으로 저장되지 않아 캐시 지역성 낮음
| 비교 항목 | 배열 | 연결 리스트 |
|---|---|---|
| 임의 접근 | O(1): 인덱스로 접근 가능 | O(n): 원하는 노드까지 순차 접근 필요 |
| 맨 뒤에 원소 삽입 | O(1): 단순 삽입 가능 (공간이 충분할 경우) | O(1): 연결 리스트 끝에서 바로 추가 가능 |
| 중간에 원소 삽입 | O(n): 앞의 원소들을 거쳐 이동해야 함 | O(1): 원하는 위치에 접근 후 삽입 |
| 캐시 지역성 | 우수: 메모리에 연속적으로 저장됨 | 낮음: 노드가 메모리에 흩어져 있음 |
배열은 임의접근에 유용하지만, 중간 원소 삽입 및 삭제에는 비효율적이다.
리스트는 임의접근이 비효율적이지만, 중간 원소 삽입 시 노드 생성 후 연결만 하면 된다.