원형연결리스트(circular linked list)의 맨 앞에 새로운… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도 표현은?㉠ 포인터 ptr이 원형연결리스트의 맨 앞 노드를 가리키는 경우㉠ ㉡
㉡ 포인터 ptr이 원형연결리스트의 맨 뒤 노드를 가리키는 경우
1
2
3
4
해설
맨 앞 삽입 시간은 ptr이 맨 앞을 가리키면 , 맨 뒤를 가리키면 이다.
원형연결리스트에서 맨 앞에 노드를 넣으면 맨 뒤 노드의 링크를 새 노드로 바꿔야 원형이 유지된다. ㉠처럼 ptr이 맨 앞 노드를 가리키면 맨 뒤 노드를 찾기 위해 리스트를 한 바퀴 순회해야 하므로 이다. ㉡처럼 ptr이 맨 뒤 노드를 가리키면 맨 앞 노드는 ptr의 다음 노드로 바로 접근되므로 링크 두 개만 바꾸면 되어 이다.
- , : ㉠에서 맨 뒤 노드를 찾는 순회 비용을 빠뜨렸다.
- , : 두 경우의 복잡도를 거꾸로 짝지었다.
- , : ㉡에서는 맨 뒤 노드가 이미 주어져 있어 순회가 필요 없다.
오류나 개정된 내용이 보이면 알려주세요
