배열
arr[i]는 O(1), 맨 뒤 추가는 동적 배열에서 amortized O(1), 중간 삽입·삭제는 이동 때문에 O(n)입니다.
Array vs Linked List
배열과 연결 리스트 접근·삽입 비용
배열은 인덱스 접근 O(1)과 캐시 지역성이 강하고, 연결 리스트는 노드를 이미 알고 있을 때 포인터 연결만 바꾸는 삽입·삭제가 강합니다.
인덱스 접근과 노드 삽입 비교
O(1) / O(n) + cache locality연결 리스트
노드 포인터를 이미 알고 있으면 삽입·삭제는 O(1)이지만, 값을 찾아가려면 처음부터 O(n) 탐색합니다.
실패 사례
삭제가 많다는 이유만으로 리스트를 고르면, 삭제할 위치를 찾는 O(n)과 pointer chasing이 병목이 됩니다.
vector가 이기는 경우
n이 작거나 순회가 많으면 Big-O가 같아 보여도 연속 메모리의 캐시 이점 때문에 배열이 더 빠를 수 있습니다.
operation mixindex/scanknown node?cache/memory
자료구조 선택은 Big-O 표만 보지 말고, 실제 입력 크기에서 탐색 횟수, 삽입 위치, 캐시 미스, 추가 포인터 메모리를 함께 측정해야 합니다.