놀이공원에서 롤러코스터를 타려고 줄을 서 있다고 가정해 보자. 누군가 중간에 새치기를 하면 새치기한 사람 뒤에 있는 사람은 모두 한 자리씩 뒤로 밀리게 된다.

선형 리스트는 순차 자료구조 방식으로 구현하므로, 삽입 후에 변경된 논리적 순서와 메모리에 연속 저장된 물리적 순서가 일치해야 한다. 따라서 메모리에 순서대로 연속 저장되어 있는 선형 리스트에 새로운 원소를 삽입하려면, 먼저 물리적으로 삽입할 자리를 만든 후에 원소를 삽입해야 한다. 원소를 삽입할 자리를 만들려면 삽입할 위치 다음에 있는 원소를 모두 한 자리씩 뒤로 옮겨야 한다.

[ 그림 3-6 ]과 같이 인덱스 2번 자리에 원소 30을 삽입하려면 2번 자리를 비워줘야 한다. 그러려면 2번 이후에 있는 원소 40, 50, 60, 70을 한 자리씩 뒤로 옮겨야 한다. 원소가 (n+1)개인 선형 리스트에서 k번 자리에 원소를 삽입하려면 빈자리를 만들기 위해 k번 원소부터 마지막 원소인 n번 원소까지 총 n-k+1개 원소를 모두 한 자리씩 뒤로 옮겨야 한다. 빈자리를 만들기 위한 이동 횟수는 n-k+1 (마지막 원소의 인덱스 - 삽입할 자리를 인덱스 + 1 )이 된다. [ 그림 3-6 ] 에서 2번 자리에 빈 자리를 만들기 위한 이동 회수는 5-2+1로 총 4회가 된다.

<aside> ❗ NOTE_ 원소가 n개인 선형 리스트에서 k번 자리에 원소를 삽입하려면 k번 원소부터 마지막 원소인 (n-1)번 원소까지 총 (n-1)-k+1개 원소를 옮겨야 한다. 따라서 이동 횟수는 (n-1)-k+1=(마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1) 이므로 5-2+1=4가 된다.

</aside>