그림과 같은 이중 연결 리스트(doubly linked list)에서 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
그림과 같은 이중 연결 리스트(doubly linked list)에서 노드 X의 왼쪽에 노드 Y를 삽입할 때, 연산의 순서를 바르게 나열한 것은? (단, Llink는 왼쪽 노드를 가리키는 포인터 변수이고, Rlink는 오른쪽 노드를 가리키는 포인터 변수이다)
a. X -> Llink -> Rlink = Y
b. Y -> Llink = X -> Llink
c. X -> Llink = Y
d. Y -> Rlink = X
1
a → c → b → d
2
a → c → d → b
3
b → c → a → d
4
b → d → a → c
해설
올바른 순서는 b → d → a → c이다.
X의 기존 왼쪽 노드 정보(X -> Llink)는 Y를 연결하는 데 계속 필요하므로, X -> Llink를 Y로 바꾸는 연산은 맨 마지막에 해야 한다.
먼저 Y의 두 링크를 채우고(Y의 왼쪽 = X의 기존 왼쪽 노드, Y의 오른쪽 = X), 기존 왼쪽 노드의 Rlink를 Y로 바꾼 뒤, 마지막으로 X의 Llink를 Y로 바꾼다.
- a → c → b → d: c 직후 X -> Llink가 이미 Y이므로 b에서 Y의 왼쪽 링크가 자기 자신을 가리키게 된다.
- a → c → d → b: 같은 이유로 b가 Y -> Llink = Y가 되어 기존 왼쪽 노드와의 연결이 끊긴다.
- b → c → a → d: c 후에 a를 하면 X -> Llink가 Y이므로 Y -> Rlink만 Y로 바뀌고, 기존 왼쪽 노드의 Rlink는 여전히 X를 가리킨다.
오류나 개정된 내용이 보이면 알려주세요