프로그래밍의 기초(의사 코드 트레이스)
다음 프로그램은 배열 next로 연결한 연결 리스트 A → C → E → D → B의 "C"(인덱스 3) 바로 뒤에 val[6]의 "F"를 삽입한 다음, 인덱스 1인 요소부터 차례로 따라가며 출력한다. 배열의 인덱스는 1부터 시작한다. next의 값 0은 리스트의 끝을 나타낸다. 출력이 A, C, F, E, D, B가 되도록 【a】에 넣을 처리는?
string array: val ← {"A", "B", "C", "D", "E", "F"}
integer array: next ← {3, 0, 5, 2, 4, 0}
【a】
integer: p ← 1
while (p ≠ 0)
output val[p]
p ← next[p]
endwhile- Anext[3] ← 6 다음에 next[6] ← next[3]
- Bnext[6] ← 3 다음에 next[3] ← next[6]
- Cnext[6] ← next[3] 다음에 next[3] ← 6
정답과 해설 보기
정답: C. next[6] ← next[3] 다음에 next[3] ← 6
삽입에서는 새 요소 F의 다음을 C가 원래 가리키던 E(next[3] = 5)로 한 다음, C의 다음을 F로 합니다. next[6] ← next[3]으로 next[6] = 5, 이어지는 next[3] ← 6으로 C → F → E가 연결됩니다. 순서를 반대로 하면 next[3]을 6으로 바꾼 후에 next[6] ← next[3]을 수행하므로 next[6] = 6이 되어, F가 자기 자신을 가리켜 C, F, F, …로 끝나지 않게 됩니다. 연결 리스트의 연결을 바꿀 때는 뒤쪽 요소로 가는 경로를 잃지 않는 순서로 대입합니다.