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

프리 리스트

이 프로그램에서 삭제한 여러 레코드를 관리하면 앞에서 발생한 ‘사용하지 않는 빈 배열’의
문제를 해결할 수 있습니다. 이때 삭제한 레코드를 관리하기 위해 사용하는 자료구조를 프리
리스트(free list)라고 부릅니다. 프리 리스트는 앞에서 다룬 ‘커서로 연결 리스트 만들기’와 삭

제한 레코드를 관리하기 위한 프리 리스트를 결합해 구현할 수 있습니다. 따라서 노드용 구조
체 Node와 연결 리스트를 관리하는 구조체 List에 포인터 버전에 없는 멤버를 추가합니다.

프리 리스트는 삭제된 레코드를 관리하기 위해 만든 연결 리스트를 이 책에서 지칭한 것입니다.

노드 구조체 Node에 추가한 멤버

• Dnext
프리 리스트의 다음 노드를 가리키는 커서입니다.

연결 리스트를 관리하는 구조체 List에 추가한 멤버

• deleted
프리 리스트의 머리 노드를 가리키는 커서입니다.
• max
배열의 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호를 의미합니다. 그림 9-15에서 ● 안에 표시한 값이
max입니다.
그림 9-15에서 max 값은 3, 4, 4로 바뀌었습니다.

그러면 그림 9-16을 통해 노드의 삽입, 삭제에 따라 프리 리스트가 어떻게 변화하는지 알아
보겠습니다.

a 연결 리스트에 5개의 노드 A → B → C → D → E가 순서대로 저장되어 있습니다. max의

값은 7이며, 8번째 레코드는 아직 사용하지 않은 상태입니다. 또한 3개의 레코드 1, 3, 5가 삭
제를 마치면 프리 리스트는 3 → 1 → 5가 됩니다. 그림 9-16에서는 데이터를 저장했던 연결
리스트(배열)에 프리 리스트를 위한 공간을 추가하여 삭제한 레코드까지 관리하는 연결 리스

트를 구현했습니다. 연결 리스트 구조체 List의 멤버 deleted의 값은 프리 리스트의 머리 노
드의 인덱스 값(그림의 a 에서 3번째 레코드)입니다.

b 연결 리스트 꼬리에 노드 F를 삽입한 이후의 상태입니다. 노드를 삽입하는 위치는 새로 정
하는 것이 아니라 프리 리스트 3, 1, 5 가운데 머리 노드의 값을 사용합니다. 따라서 노드 F를

3번째 레코드에 저장하고 프리 리스트에서 3을 삭제해 1 → 5의 상태로 만듭니다. 이런 방법

374 C 알고리즘