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

예를 들어, 노드 B의 커서 3은 B의 다음 노드 C가 인덱스 3인 위치에 저장되어 있음을 의미합

니다. 꼬리 노드의 커서는 배열의 인덱스로는 있을 수 없는 값인 –1로 하면 됩니다. 머리 노드
를 나타내는 head도 커서이기 때문에 머리 노드 A가 들어 있는 곳인 인덱스 1이 head의 값
이 됩니다. 이와 같은 방법을 사용하면 노드의 삽입, 삭제 시 요소를 옮길 필요가 없습니다. 예
를 들어, 그림 9-13처럼 연결 리스트의 머리에 노드 G를 삽입하면 그림 9-14와 같은 상태가

됩니다. head를 1에서 6으로 업데이트하고 노드 G의 커서에 1을 대입하면 됩니다.

head
６ １ ４ ３ ０ ２ ５
G Ａ Ｂ Ｃ Ｄ Ｅ Ｆ

head 6 ０ D 2
１ A 4 업데이트하지 않습니다.
２ E 5 업데이트합니다.
6으로 바뀝니다. ３ C 0
４ B 3 머리에 노드 G를 삽입합니다.
５ F -1
６ G 1
７ － －
[그림 9-14] 머리에 노드를 삽입하는 과정

실습 9-4, 9-5는 이런 방식으로 구현한 프로그램입니다.

실습 9-4는 헤더, 실습 9-5는 소스입니다.

커서의 자료형 Index
Index는 커서의 자료형입니다. 단순한 정수 값을 가지기 때문에 int형과 동일하게 정의
합니다.

노드의 자료형 Node
연결 리스트의 노드를 의미하는 구조체 Node입니다. 커서 next의 자료형은 커서의 자료형
인 Index입니다.

연결 리스트를 관리하는 구조체 List
구조체 List는 연결 리스트를 관리하는 구조체입니다.

구조체 Node와 List는 09-2절의 프로그램에 비해 멤버가 많습니다. 멤버가 많아진 이유에 대해서도 곧이어 자세히 살
펴보겠습니다.

09•리스트 365