Page 20 -

1.4 삽입 data structures and algorithms

배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따
라 효율성이 다르다.

쇼핑 목록의 맨 끝에 "figs"를 추가해 보자. 이 삽입에는 딱 한 단계만 필요하

다. 앞서 설명했듯이 컴퓨터는 배열이 시작되는 메모리 주소를 안다. 이제 컴퓨
터는 배열이 현재 얼마나 많은 원소를 포함하는지도 알고 있으므로 새 원소를
추가해야 하는 메모리 주소가 어딘지 계산할 수 있고, 이는 한 단계면 된다. 다
음 그림을 살펴보자.

그림 1-10

ˮapplesˮ ˮbananasˮ ˮcucumbersˮ ˮdatesˮ ˮelderberriesˮ ˮfigsˮ

1010 1011 1012 1013 1014 1015

하지만 배열의 맨 처음이나 중간에 데이터를 삽입하면 문제가 달라진다. 이때는
삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 하므로 단계가 늘
어난다.

예를 들어 배열의 인덱스 2에 "figs"를 추가해 보자. 다음 그림으로 살펴보자.

1장 자료 구조가 중요한 까닭 031

algorith06.indd 31 2018-06-25 오전 10:32:03