단순 연결 리스트(singly linked list)의 노드를 나타내는… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
단순 연결 리스트(singly linked list)의 노드를 나타내는 구조체 node에 다음 노드를 가리키는 포인터 link가 있다고 하자. 2개의 노드로 구성된 단순 연결 리스트에서 첫 번째 노드와 두 번째 노드의 사이에 새로운 노드를 삽입하면서 리스트의 순서를 역순으로 변환하고자 한다. p에는 리스트의 시작 주소가 저장되어 있으며, new에는 새로운 노드의 주소가 저장되어 있다고 가정할 때, 명령문의 실행 순서로 옳은 것은? (단, 역순 변환 후 p에는 리스트의 새로운 시작 주소가 저장되어 있어야 한다)
1
p→link = new; p = p→link; new→link = p; new→link→link = NULL;
2
p = p→link; p→link = new; new→link = p; new→link→link = NULL;
3
new→link = p; p→link = new; p = p→link; new→link→link = NULL;
4
new→link = p; p = p→link; p→link = new; new→link→link = NULL;
해설
옳은 실행 순서는 new→link = p; p = p→link; p→link = new; new→link→link = NULL;이다.
처음 리스트를 A→B라 하면 목표는 B→new→A이고 p는 B를 가리켜야 한다. 이 순서는 new가 A를 가리키게 한 뒤 p를 B로 옮기고, B가 new를 가리키게 한 다음 A의 link를 NULL로 만들어 완성한다.
- p→link = new 로 시작하는 순서: A의 link를 먼저 덮어써 B의 주소를 잃는다.
- p = p→link; p→link = new; new→link = p 순서: new가 A가 아닌 B를 가리키게 되어 A가 리스트에서 빠진다.
- new→link = p; p→link = new 로 시작하는 순서: A의 link를 new로 바꿔 B의 주소를 잃는다.
오류나 개정된 내용이 보이면 알려주세요