n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결리스트(singly linked list)로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?
1
포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제
2
리스트의 길이를 출력
3
포인터값이 주어진 임의의 노드 앞에 새로운 노드 추가
4
마지막 노드의 데이터를 출력
해설

시간 복잡도가 가장 낮은 연산은 포인터가 가리키는 노드의 다음 노드 삭제로 O(1)이다.

가리키는 노드의 링크를 다음 노드의 링크로 바꾸기만 하면 되므로 탐색이 필요 없다. 나머지 연산은 단순 연결리스트에서 리스트를 처음부터 따라가야 해 O(n)이다.

  • 리스트 길이 출력: 길이를 따로 저장하지 않으면 모든 노드를 세어야 한다.
  • 주어진 노드 앞에 새 노드 추가: 단순 연결리스트에는 앞 노드로 가는 링크가 없어 선행 노드를 처음부터 찾아야 한다.
  • 마지막 노드의 데이터 출력: 꼬리 포인터가 없으면 끝까지 따라가야 한다.

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

이어서 풀어보기

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