.png)
☑️배열 : 메모리 상에 원소를 연속하게 배치한 자료구조.
자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다.
☑️배열의 성질
- O(1)에 k번째 원소를 확인 / 변경 가능
- 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
- Cache hit rate가 높음
- 메모리상에 연속한 구간을 잡아야해서 할당에 제약이 걸림
Cache hit rate : CPU에서 요청한 데이터가 캐시에 존재하는 경우
캐시 적중 : 캐시 메모리가 있는 컴퓨터 시스템은 CPU가 메모리에 접근하기 전 먼저
캐시 메모리에서 원하는 데이터 존재여부 확인
참조의 지역성
1. 시간적 지역성 : CPU가 한번 참조한 데이터는 다시 참조할 가능성이 높다.
2. 공간적 지역성 : CPU가 참조한 데이터와 인접한 데이터 역시 참조될 가능성이 높다.
3. 순차적 지역성 : 분기가 발생하지 않는 한 명령어는 메모리에 저장된 순서대로 인출 / 실행 된다.
→ 배열은 연속된 메모리 공간을 가지기 때문에 공간적 지역성을 바탕으로 수집한다면 리스트보다 적중률을 높일 수 있다.
☑️배열 연산
삽입
삭제
☑️연결 리스트 : 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조.
원소들은 이곳 저곳에 흩어져 있다.
☑️연결 리스트의 성질
- k번째 원소를 확인 / 변경하기 위해 O(k)가 필요함
- 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거 O(1)
- 원소들이 메모리상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움
☑️연결 리스트의 종류
- 단일 연결 리스트
각 원소가 자신의 다음 원소의 주소를 들고있는 연결 리스트
주어진 원소의 이전 원소를 알 수 없음 - 이중 연결 리스트
각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고있음
주어진 원소의 이전 원소를 알 수 있음. 다만, 원소가 가지고 있어야 하는 정보가 하나 더 추가되니 메모리를 더 쓴다는 단점. - 원형 연결 리스트
끝과 처음이 연결되어 있음. 이중연결리스트 형태여도 상관 없음
☑️연결 리스트 연산
삽입
삭제
☑️ 배열과 연결리스트 비교
- 배열과 연결 리스트는 메모리상에 원소를 놓는 방법은 다르다고 해도 원소들 사이의 선후 관계가 일대일로 정의된다.
즉, 원소들 사이에서 첫 원소, 두번째 원소, .. 등의 개념이 있으므로 선형 자료구조이다.
| 배열 | 연결리스트 | |
|---|---|---|
| k번째 원소 접근 | O(1) | O(k) |
| 임의 위치에 원소 추가 / 제거 | O(N) | O(1) |
| 메모리 상의 배치 | 연속 | 불연속 |
| 추가적으로 필요한 공간 (overhead) | - | O(N) |
- 각 원소가 주소값을 갖고 있어야함 32bit → 4Nbyte, 64bit → 8Nbyte가 필요하다.
즉, N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.
그럼 어떤 경우에 연결 리스트를 쓰는게 더 적절할까요?
- 배열은 삽입과 삭제연산이 O(N) 인 반면에 연결리스트는 O(1) 의 시간복잡도를 가집니다. 따라서 삽입과 삭제가 빈번한 상황이라면 연결리스트를 사용하는게 더 유리합니다.
반가워요!