다음은 이중연결리스트의 맨 앞에 새로운 키 값을 갖는 노드를 삽입하는 … | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음은 이중연결리스트의 맨 앞에 새로운 키 값을 갖는 노드를 삽입하는 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, head는 이중연결리스트의 맨 앞 노드를 가리키는 포인터이며, 리스트는 초기에 비어있다고 가정한다)struct node { // 이중연결리스트의 노드 구조
int key;
struct node *prev; // 이전 노드를 가리키는 포인터
struct node *next; // 다음 노드를 가리키는 포인터
};
struct node *head = NULL; // 맨 처음 노드를 가리키는 포인터
void insertDoubleList(int ikey)
{
struct node *temp;
temp = (struct node *) malloc(sizeof(struct node));
if (temp == NULL) {
printf("Memory allocation is failed. \n");
exit(1);
}
temp→key = ikey;
( ㉠ ) ;
if (head == NULL) // 리스트에 노드가 없는 경우
( ㉡ ) ;
else { // 리스트에 노드가 있는 경우
( ㉢ ) ;
head→prev = temp;
}
head = temp;
}
㉠ ㉡ ㉢
1
temp→prev = NULL temp→prev = head temp→prev = head
2
temp→prev = NULL temp→next = NULL temp→next = head
3
head→next = temp temp→next = NULL temp→prev = head
4
head→next = temp temp→prev = head temp→next = head
해설
㉠ temp→prev = NULL, ㉡ temp→next = NULL, ㉢ temp→next = head 조합이 옳다.
맨 앞에 삽입되는 노드는 이전 노드가 없으므로 prev를 항상 NULL로 둔다. 리스트가 비어 있으면 다음 노드도 없어 next = NULL이고, 노드가 있으면 새 노드의 next가 기존 head를 가리킨 뒤 head→prev = temp로 양방향 연결을 완성한다.
- temp→prev = NULL, temp→prev = head, temp→prev = head: prev만 덮어써 next가 초기화되지 않고 기존 노드와 연결되지 않는다.
- head→next = temp, temp→next = NULL, temp→prev = head: 빈 리스트에서 NULL인 head의 next에 접근한다.
- head→next = temp, temp→prev = head, temp→next = head: 빈 리스트에서 NULL 접근이 발생하고 연결 방향도 반대이다.
오류나 개정된 내용이 보이면 알려주세요