이중 연결 리스트에서 노드 p의 다음(next) 노드가 q이고 노드 q… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
이중 연결 리스트에서 노드 p의 다음(next) 노드가 q이고 노드 q의 이전(prev) 노드가 p인 경우, 인접한 p, q 노드의 위치를 서로 바꾸는 연산의 순서로 옳은 것은? (단, p, q 노드는 모두 연결 리스트의 처음 노드나 마지막 노드가 아니라고 가정한다)
ㄱ. p → prev → next = q;
ㄴ. q → next → prev = p;
ㄷ. p → prev = q;
ㄹ. q → next = p;
ㅁ. q → prev = p → prev;
ㅂ. p → next = q → next;
1
ㄱ→ㄴ→ㄷ→ㄹ→ㅁ→ㅂ
2
ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ
3
ㄱ→ㄴ→ㅂ→ㄹ→ㄷ→ㅁ
4
ㄷ→ㄹ→ㅁ→ㅂ→ㄱ→ㄴ
해설

올바른 순서는 ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ이다.

p의 앞 노드를 A, q의 뒤 노드를 B라 하면 먼저 A.next=q(ㄱ), B.prev=p(ㄴ)로 바깥 연결을 바꾸고, 아직 남아 있는 p.prev와 q.next를 이용해 q.prev=A(ㅁ), p.next=B(ㅂ)를 설정한다.
마지막으로 p.prev=q(ㄷ), q.next=p(ㄹ)로 둘을 맞붙이면 A↔q↔p↔B가 된다.

  • ㄷ·ㄹ을 ㅁ보다 먼저 하면 p.prev가 이미 q로 바뀌어 q.prev가 자기 자신을 가리키게 된다.
  • ㅂ→ㄹ→ㄷ→ㅁ 순서도 ㅁ 시점에 p.prev가 q이므로 같은 오류가 생긴다.
  • ㄷ·ㄹ부터 하면 A와 B의 주소를 잃어 바깥 노드의 링크를 고칠 수 없다.

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

이어서 풀어보기

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