다음은 원형연결리스트(circular linked list)의 맨 앞에… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음은 원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 추가하는 알고리즘의 의사코드이다. ㉠, ㉡에 들어갈 문장으로 옳은 것은? (단, 원형연결리스트에서 ‘last’는 리스트의 맨 마지막 노드를 가리키는 포인터이고 초기치는 NULL이며, 변수 ‘p’는 새로 삽입되는 노드를 나타낸다. 또한 리스트에 3개 이상의 노드를 추가할 수 있어야 한다)struct node {
int key;
struct node *next;
} *last = NULL; //마지막 노드를 가리키는 포인터
Function insertFront(struct node *p)
if (last == NULL) then // 리스트가 빈 경우
last = p;
p→next = p;
else // 리스트에 하나 이상의 노드가 있는 경우
( ㉠ )
( ㉡ )
end if
return;
㉠ ㉡
1
p→next = last→next; last→next = p;
2
last→next = p; p→next = last→next;
3
p→next = last; last→next = p;
4
last→next = p; p→next = last;
해설
㉠ p→next = last→next; 다음 ㉡ last→next = p; 순서가 옳다.
last→next가 맨 앞 노드이므로, 먼저 새 노드가 기존 맨 앞을 가리키게 한 뒤 last가 새 노드를 가리키게 해야 원형이 유지된다. 맨 앞 삽입이므로 last는 바꾸지 않는다.
- last→next = p; 후 p→next = last→next;: 기존 맨 앞 주소를 먼저 덮어써 p가 자기 자신을 가리키게 된다.
- p→next = last; last→next = p;: 새 노드가 마지막 노드를 가리켜 기존 맨 앞~중간 노드가 고리에서 끊긴다.
- last→next = p; p→next = last;: last와 p 두 노드만의 고리가 되어 나머지 노드가 유실된다.
오류나 개정된 내용이 보이면 알려주세요