데크(deque: double-ended queue)는 삽입과 삭제가 … | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
데크(deque: double-ended queue)는 삽입과 삭제가 양끝에서 임의로 수행되는 자료구조이다. 다음 그림과 같이 단순 연결 리스트(singly linked list)로 데크를 구현한다고 할 때 O(1) 시간 내에 수행할 수 없는 연산은? (단, first와 last는 각각 데크의 첫 번째 원소와 마지막 원소를 가리키며, 연산이 수행된 후에도 데크의 원형이 유지되어야 한다)
문제 이미지
1
insertFirst 연산: 데크의 첫 번째 원소로 삽입
2
insertLast 연산: 데크의 마지막 원소로 삽입
3
deleteFirst 연산: 데크의 첫 번째 원소를 삭제
4
deleteLast 연산: 데크의 마지막 원소를 삭제
해설

단순 연결 리스트로 구현한 데크에서 O(1)에 할 수 없는 연산은 마지막 원소 삭제(deleteLast)이다.

마지막 노드를 지우면 last 를 그 직전 노드로 옮기고 링크를 NULL 로 바꿔야 하는데, 단방향 링크로는 직전 노드를 알 수 없어 first 부터 끝까지 따라가야 하므로 O(n)이 걸린다.

  • 첫 번째 원소로 삽입: 새 노드가 기존 first 를 가리키게 하고 first 만 갱신하면 되므로 O(1)이다.
  • 마지막 원소로 삽입: last 노드의 링크를 새 노드로 연결하고 last 를 갱신하면 되므로 O(1)이다.
  • 첫 번째 원소 삭제: first 를 다음 노드로 옮기기만 하면 되므로 O(1)이다.

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

이어서 풀어보기

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