잘못된 주장
연결 중간 삽입은 무조건 O(1) · 탐색 누락
중간 삽입 비용은 위치 탐색과 링크 변경을 분리한다
이미 Node 참조가 있는 알고리즘의 O(1) 재배선과 index 기반 API의 O(n) 탐색을 같은 표에 섞지 않습니다.
공정한 모델
index 탐색 O(n) + 링크 쓰기 O(1)
Node 핸들 전제
위치를 이미 알 때만 재배선 O(1)
핵심: 실제 시간 단정 대신 탐색 횟수·쓰기 횟수·캐시 효과를 별도 항목으로 관찰합니다.
이미 Node 참조가 있는 알고리즘의 O(1) 재배선과 index 기반 API의 O(n) 탐색을 같은 표에 섞지 않습니다.
연결 중간 삽입은 무조건 O(1) · 탐색 누락
index 탐색 O(n) + 링크 쓰기 O(1)
위치를 이미 알 때만 재배선 O(1)
핵심: 실제 시간 단정 대신 탐색 횟수·쓰기 횟수·캐시 효과를 별도 항목으로 관찰합니다.