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

으로 프리 리스트에 빈 레코드가 등록된 경우에는 ‘새 레코드를 지정하고 max의 값을 증가한

다음 해당 레코드에 데이터를 저장’하지 않습니다. 따라서 max의 값은 8이 아니라 7인 상태
를 유지합니다.

연결 리스트(원래 데이터의 나열을 관리)
head 2 deleted 3
head
a ０ C 7 －
１ - - 5
２ ６ ０ ７ ４ ２ A 6 －
Ａ Ｂ Ｃ D E ３ - 1
４ E -1 －
５ - - -1
deleted ６ B 0 －
3 1 5 ❼ D 4 －
８ － - －
프리 리스트(삭제한 레코드를 관리)

head 2 deleted 1
head
b ０ C 7 －
１ － － 5
２ ６ ０ ７ ４ ３ ２ A 6 －
Ａ Ｂ Ｃ D Ｅ F ３ F -1 －
４ E 3 －
노드 F를 삽입합니다. ５ － － -1
deleted ６ B 0 －
1 5 ❼ D 4 －
８ － － －

head 2 deleted 7
head
c ０ C 4 －
１ － － 5
２ ６ ０ ７ ４ ３ ２ A 6 －
Ａ Ｂ Ｃ Ｄ E F ３ F -1 －
４ E 3 －
노드 D를 삭제합니다. ５ － － -1
deleted ６ B 0 －
7 1 5 ❼ － － 1
８ － － －
커서(다음 노드의 인덱스）next
프리 리스트의 커서(프리 리스트의 다음 노드의 인덱스）dnext

[그림 9-16] 노드의 삽입과 삭제에 따라 프리 리스트가 변화하는 모습

c 노드 D를 삭제한 다음의 상태입니다. 7번째 레코드에 넣어둔 데이터를 삭제했기 때문에 7
을 프리 리스트의 머리 노드로 추가합니다. 프리 리스트는 7 → 1 → 5의 상태가 됩니다.

삭제한 레코드를 프리 리스트에 등록하는 함수의 이름은 DeleteIndex이고 노드를 삽입할 때
레코드 번호를 정하는 함수의 이름은 GetIndex입니다. 그림 b 의 경우를 예로 들면 이미 삭제

09•리스트 375