연속된 자료구조 vs 연결된 자료구조

연속된 자료구조	연결된 자료구조
모든 데이터가 메모리에 연속적으로 저장된다.	데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있다.
임의 원소에 즉각적으로 접근할 수 있다. (시작주소 + 2 * sizeof(type) 식으로 수식을 통해 접근한다)	임의 원소에 접근하는 것은 산형 시간 복잡도를 가지며 느린 편입니다.
데이터가 연속적으로 저장되어 있고, 캐시 지역성 효과로 인해 모든 데이터를 순회하는 것이 매우 빠릅니다.	캐시 지역성 효과가 없으므로 모든 데이터를 순회하는 것이 느린 편입니다.
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리를 사용합니다.	각 노드에서 포인터 저장을 위해 여분의 메모리를 사용한다.
배열의 유형 1. 정적 배열 (stack) : 선언된 블록이 끝나면 소멸 int arr[size] 2. 동적 배열 (heap) : 생성, 해제 시점 프로그래머가 결정 int* arr = new int[size];

다양한 연산에 대한 시간복잡도 비교

파라미터	배열	연결리스트
임의 접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
중간에 원소 삽입	O(n)	O(1)
캐시 지역성	있음	없음