[Algorithm] 배열과 연결리스트

🖍️ 배열과 벡터

배열이란?

메모리 상에 원소를 연속하게 배치한 자료구조

0	1	2	3	4	5
5	7	6	2	9	1

배열의 성질

1. O(1)에 K번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리양(overhead)가 거의 없음
3. cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림

   cache hit rate

   • 캐시 메모리(주로 CPU와 메인 메모리 사이에 위치하며, 빠른 접근 속도를 제공하여 시스템 성능을 향상)에서 메인 메모리에 접근하지 않고 성공적으로 데이터를 가져오는 메모리 액세스 요청의 백분율

배열의 시간 복잡도

연산	시간복잡도
임의의 위치에 있는 원소 확인 및 변경	O(1)
원소를 끝에 추가	O(1)
마지막 원소를 제거	O(1)
임의의 위치에 원소를 추가 및 제거	O(N)

vector

동적으로 크기가 조정되는 배열(List)을 구현한 자료구조

vector의 성질

1. 동적으로 크기를 조정 가능
   요소를 추가하거나 삭제할 때 자동으로 크기가 조정되며, 필요에 따라 용량(capacity)이 증가
2. 요소를 저장할 때 입력된 순서대로 유지
3. 동기화된 메소드로 구현되어 있어 멀티스레드 환경에서 안전하게 사용 가능
   여러 스레드가 동시에 Vector에 접근하더라도 내부적으로 동기화되어 충돌을 방지

---

🖍️ 연결리스트

연결리스트란?

데이터 요소를 노드(Node)로 구성하여 저장하는 자료구조

연결리스트의 성질

1. K번째 원소를 확인/변경하기 위해 O(K)가 필요함
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 cache hit rate가 낮지만 할당이 쉬움

연결리스트 종류

단일 연결 리스트	이중 연결 리스트	원형 연결 리스트

연결리스트의 시간 복잡도

연산	시간복잡도	이유
임의의 위치에 있는 원소 확인 및 변경	O(N)	포인트가 각각 연결된 노드에 존재하기 때문에 순차적으로 순회
임의의 위치에 원소를 추가 및 제거	O(1)	삽입이나 제거로 인해 다른 원소를 옮길 필요가 없이 연결된 주소값만 변경

배열 vs 연결리스트

공통점 : 선형 자료 구조

차이점	배열	연결리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간 (Overhead)	-	O(N)