Page 364 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

09-3 커서로 연결 리스트 만들기

이번에는 각 노드를 배열 안의 요소에 저장하고 그 요소를 잘 이용해 연결 리스트를 구현하는
방법을 알아보겠습니다.

커서로 연결 리스트 만들기
09-2절에서 살펴본 연결 리스트는 ‘노드의 삽입, 삭제를 데이터 이동 없이 수행한다’라는 특

징이 있었지만 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 만들고 해제하
는 과정이 필요했습니다. 메모리 영역을 만들고 해제하는 데 필요한 비용은 결코 무시할 수
없습니다. 이때 프로그램 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값
을 미리 알 수 있다고 가정하면 그림 9-13처럼 배열을 사용해 효율적으로 연결 리스트를 운

용할 수 있습니다.
커서를 사용하는 연결 리스트는 데이터 개수의 최댓값을 미리 계산하여 모든 노드를 저장하기에 충분한 크기의 배열을 만
들어야 합니다.

a 배열로 구현한 연결 리스트의 논리적인 이미지
head 인덱스
１ ４ ３ ０ ２ ５
Ａ Ｂ Ｃ Ｄ Ｅ Ｆ

b 연결 리스트를 배열로 구현한 경우
head 1 ０ D 2
１ A 4
２ E 5 다음 노드 인덱스 3
머리 노드의 ３ C 0
인덱스 값 ４ B 3
５ F -1
６ － －
７ － －
데이터 다음 노드의 인덱스를 저장하고 있는 커서
[그림 9-13] 커서를 사용한 연결 리스트

배열의 커서에 해당하는 값은 다음 노드에 대한 포인터가 아니라 다음 노드가 들어 있는 요소
의 인덱스에 대한 값입니다. 여기서 포인터 역할을 하는 인덱스를 커서(cursor)라고 합니다.

364 C 알고리즘