원형연결리스트(circular linked list)의 맨 앞에 새로운… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
원형연결리스트(circular linked list)의 맨 앞에 새로운 노드를 삽입할 때, ㉠, ㉡에 대한 시간 복잡도 표현은?
㉠ 포인터 ptr이 원형연결리스트의 맨 앞 노드를 가리키는 경우

㉡ 포인터 ptr이 원형연결리스트의 맨 뒤 노드를 가리키는 경우
㉠ ㉡
문제 이미지
1
O(1)O(1) O(1)O(1)
2
O(1)O(1) O(n)O(n)
3
O(n)O(n) O(1)O(1)
4
O(n)O(n) O(n)O(n)
해설

맨 앞 삽입 시간은 ptr이 맨 앞을 가리키면 O(n)O(n), 맨 뒤를 가리키면 O(1)O(1)이다.

원형연결리스트에서 맨 앞에 노드를 넣으면 맨 뒤 노드의 링크를 새 노드로 바꿔야 원형이 유지된다. ㉠처럼 ptr이 맨 앞 노드를 가리키면 맨 뒤 노드를 찾기 위해 리스트를 한 바퀴 순회해야 하므로 O(n)O(n)이다. ㉡처럼 ptr이 맨 뒤 노드를 가리키면 맨 앞 노드는 ptr의 다음 노드로 바로 접근되므로 링크 두 개만 바꾸면 되어 O(1)O(1)이다.

  • O(1)O(1), O(1)O(1): ㉠에서 맨 뒤 노드를 찾는 순회 비용을 빠뜨렸다.
  • O(1)O(1), O(n)O(n): 두 경우의 복잡도를 거꾸로 짝지었다.
  • O(n)O(n), O(n)O(n): ㉡에서는 맨 뒤 노드가 이미 주어져 있어 순회가 필요 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 15년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기