배열·연결 작업 부하 처리 흐름

조회·앞 삽입·끝 삽입의 이동 또는 링크 추적 횟수를 세어 Big-O와 CPU 캐시 효과를 함께 해석합니다.

  1. 이동 칸 수

    배열 get은 주소 계산으로 접근하지만 연결 get은 head부터 next를 따라갑니다.

    1단계

  2. next 추적 수

    배열 앞 삽입은 기존 원소를 오른쪽으로 이동하고 연결 앞 삽입은 head만 교체합니다.

    2단계

  3. 연속 메모리

    tail이 있는 연결 목록과 여유 capacity가 있는 배열 목록은 끝 추가가 모두 상수 수준입니다.

    3단계

  4. 캐시 지역성

    연속 배열 순회는 객체마다 흩어진 Node 순회보다 CPU 캐시 지역성이 좋은 경우가 많습니다.

    4단계

핵심: 비교하는 두 구현은 같은 입력 크기·같은 위치·같은 최종 결과를 사용한다