방송대 자료구조 6강 : 원형·이중 연결 리스트의 포인터 갱신

방송대 자료구조 6강: 원형·이중 연결 리스트의 포인터 갱신

연결 리스트를 변형하는 이유는 노드를 더 복잡하게 만들기 위해서가 아니라, 단순 연결 리스트에서 비싼 이동을 줄이기 위해서입니다. 이 글은 ‘끝에서 다시 처음으로 갈 것인가’와 ‘앞뒤로 모두 움직일 것인가’를 기준으로 원형·이중 연결 리스트를 구분하고, 삽입·삭제 때 어떤 링크를 어떤 순서로 바꿔야 하는지 주소 추적과 불변식으로 검산합니다.

한 방향 링크만으로는 직전 노드를 바로 찾을 수 없다

단순 연결 리스트의 각 노드는 데이터와 다음 노드를 가리키는 링크 하나를 갖습니다. 현재 노드가 X라면 X->link로 다음 노드에는 곧바로 갈 수 있지만, X의 직전 노드를 가리키는 정보는 X 안에 없습니다. 직전 노드가 필요하면 머리 노드부터 다시 출발해 링크가 X인 노드를 찾아야 합니다.

이 불편은 두 가지 서로 다른 질문으로 구분할 수 있습니다. 첫째, 마지막 노드에 도달했을 때 탐색을 끝낼지 처음부터 이어 갈지입니다. 둘째, 현재 노드에서 다음 방향뿐 아니라 이전 방향으로도 곧바로 움직일지입니다. 원형 연결 리스트는 첫 번째 질문을, 이중 연결 리스트는 두 번째 질문을 해결합니다.

구조 선택의 출발점: ‘링크가 몇 개인가’만 외우지 말고 필요한 이동을 먼저 묻습니다. 끝에서 첫 노드로 계속 순환해야 하면 원형 구조를, 현재 노드에서 직전·직후 노드를 모두 직접 찾아야 하면 이중 구조를 고려합니다.

탐색 방향과 끝 처리를 나누면 네 구조가 한눈에 보인다

원형과 이중은 서로 반대되는 분류가 아닙니다. 원형 여부는 마지막 링크의 목적지를, 단일·이중 여부는 노드가 기억하는 방향의 수를 말합니다. 따라서 두 기준을 조합하면 단순, 원형, 이중, 이중 원형 연결 리스트를 같은 틀에서 비교할 수 있습니다.

구조	노드의 이동 방향	끝의 연결	적합한 판단 상황
단순 연결 리스트	다음 방향	마지막 링크가 NULL	처음부터 끝까지 한 방향으로 처리
원형 연결 리스트	다음 방향	마지막 링크가 첫 노드	끝없이 차례를 순환하거나 임의의 시작점에서 한 바퀴 처리
이중 연결 리스트	이전·다음 방향	양 끝 바깥쪽 링크가 NULL	현재 위치에서 앞뒤 항목을 자주 오감
이중 원형 연결 리스트	이전·다음 방향	첫 노드와 마지막 노드가 양방향으로 연결	양방향 이동과 순환을 함께 요구

원형 구조에서는 어느 노드에서 출발해도 다음 링크를 계속 따라 한 바퀴를 돌면 모든 노드에 도달할 수 있습니다. 그러나 이것이 배열처럼 원하는 노드에 즉시 접근한다는 뜻은 아닙니다. 목표를 찾을 때까지 링크를 차례로 따라야 하므로 ‘도달 가능’과 ‘즉시 접근’을 구분해야 합니다.

오개념 교정: 원형 연결 리스트에 뒤쪽 링크가 생기는 것은 아닙니다. 단일 원형 구조의 노드는 여전히 다음 노드 하나만 기억합니다. 이전 방향의 직접 이동은 이중 링크가 제공하는 별도의 성질입니다.

원형 리스트의 불변식은 마지막 링크가 머리를 가리키는 것이다

강의자료의 원형 연결 리스트는 데이터와 link를 갖는 노드, 그리고 첫 노드를 가리키는 head로 구성됩니다. 빈 리스트에서는 head=NULL입니다. 첫 노드 N을 넣으면 N은 동시에 첫 노드이자 마지막 노드이므로 head=N과 N->link=N을 함께 설정해야 합니다.

빈 원형 리스트: head = NULL
노드 N 하나 삽입:
  head = N
  N->link = N

노드가 여러 개라면 마지막 노드의 링크는 항상 head와 같아야 합니다. 이것이 원형 리스트의 핵심 불변식입니다. 단순 리스트에서 끝을 판별하던 link==NULL은 더 이상 사용할 수 없습니다. 마지막 노드는 자신의 링크가 head인지로 알아냅니다.

원형 구조 검산: 빈 리스트가 아니라면 ① head에서 출발해 링크를 따라 다시 head로 돌아오고, ② 그 전에 NULL을 만나지 않으며, ③ 한 바퀴 안에서 각 노드를 한 번씩 방문해야 합니다.

첫 삽입은 새 경로를 만든 뒤 머리를 옮긴다

비어 있지 않은 원형 리스트의 맨 앞에 새 노드를 삽입하려면 마지막 노드도 찾아야 합니다. 마지막 노드는 링크가 현재 head인 노드입니다. 이후 새 노드가 기존 첫 노드를 가리키게 하고, 마지막 노드가 새 노드를 가리키게 한 다음, 마지막으로 head를 새 노드로 옮깁니다.

last = head
while last->link != head:
  last = last->link

newNode->link = head
last->link = newNode
head = newNode

강의와 다른 주소로 포인터를 추적해 보자

학습용 예로 A의 주소를 1200, B의 주소를 1600이라 가정합니다. 처음에는 head=1200, A.link=1600, B.link=1200입니다. 주소 900인 X를 맨 앞에 넣으면 먼저 X.link=1200, 다음으로 B.link=900, 마지막으로 head=900으로 바꿉니다. 결과는 X(900)→A(1200)→B(1600)→X(900)입니다.

갱신 단계	바뀌는 값	보존되는 경로
삽입 전	head=1200, B.link=1200	A→B→A
① 새 노드 연결	X.link=1200	X에서 기존 머리 A로 이동 가능
② 마지막 링크 연결	B.link=900	기존 마지막 B에서 X로 이동 가능
③ 머리 이동	head=900	X→A→B→X의 원 완성

head부터 먼저 900으로 바꾸면 기존 첫 노드 주소 1200을 따로 보관하지 않은 경우 연결할 대상을 잃을 수 있습니다. 링크 갱신에서는 기존 경로를 덮어쓰기 전에 그 경로가 가리키던 주소를 새 링크에 보존하는 것이 안전합니다.

중간 삽입은 이전 노드의 다음 링크 하나를 두 갈래로 나눈다

원형 리스트에서 prevNode 뒤에 새 노드를 넣는 과정은 두 문장으로 정리됩니다. 새 노드의 링크에 prevNode의 기존 다음 주소를 복사하고, prevNode의 링크를 새 노드로 바꿉니다.

newNode->link = prevNode->link
prevNode->link = newNode

앞의 A(1200)→B(1600)→A 구조에서 주소 1400인 Y를 A 뒤에 넣는다고 합시다. 먼저 Y.link=A.link=1600으로 만들어 Y에서 B로 가는 길을 확보합니다. 그 뒤 A.link=1400으로 바꾸면 A→Y→B→A가 됩니다. 두 대입문의 순서를 반대로 실행하고 기존 A.link를 보관하지 않으면 B의 주소를 잃을 수 있습니다.

맨 앞 삽입과 중간 삽입의 차이는 head가 바뀌는지입니다. 중간 삽입에서는 첫 노드가 그대로이므로 머리를 옮기지 않습니다. 그러나 마지막 노드 뒤에 삽입한다면 새 노드의 링크가 기존 머리를 가리켜야 원형 불변식이 유지됩니다.

잘못된 접근의 원인: ‘새 노드를 이전 노드에 연결한다’는 한 문장만 기억하면 새 노드의 다음 링크를 빠뜨리기 쉽습니다. 삽입 뒤에는 새 노드로 들어오는 링크 하나와 새 노드에서 나가는 링크 하나가 모두 있어야 합니다.

원형 탐색은 한 번 방문한 머리로 돌아왔을 때 끝낸다

원형 리스트에는 NULL 끝 표시가 없으므로 실패한 탐색을 멈추는 기준이 필요합니다. 강의자료는 현재 노드를 head에서 시작해 먼저 검사하고, 다음 노드로 이동한 뒤 다시 head가 되었는지를 확인하는 do...while 흐름을 사용합니다.

current = head
do:
  if current->data == target:
    찾음
  previous = current
  current = current->link
while current != head

찾지 못함

처음부터 while current != head를 검사하면 current와 head가 같으므로 반복 본문을 한 번도 실행하지 않습니다. 따라서 첫 노드조차 검사하지 못합니다. ‘먼저 방문하고, 돌아왔는지 나중에 검사한다’가 원형 탐색의 핵심입니다.

또한 삭제할 노드를 찾는 탐색에서는 현재 노드뿐 아니라 직전 노드도 함께 추적해야 합니다. 단일 링크만으로는 현재 노드에서 이전 노드로 돌아갈 수 없기 때문입니다. 목표를 발견했을 때 previous->link를 목표의 다음 노드로 바꿀 수 있도록 두 포인터를 같이 이동합니다.

한 바퀴 탐색 절차: 빈 리스트인지 확인 → 머리를 첫 검사 대상으로 지정 → 현재 데이터를 검사 → 이전·현재 포인터를 한 칸 이동 → 현재가 다시 머리인지 판정합니다. 목표가 없으면 정확히 한 바퀴 뒤 실패로 종료합니다.

원형 삭제는 빠져나갈 노드를 우회한 뒤 메모리를 해제한다

중간 노드 D를 삭제할 때는 D의 직전 노드 P가 D의 다음 노드 S를 직접 가리키게 해야 합니다. 즉 P.link=D.link로 경로를 우회시킨 뒤 D를 해제합니다. 해제를 먼저 하면 D가 가진 다음 주소를 읽을 수 없으므로 순서가 뒤집혀서는 안 됩니다.

학습용으로 A(1200)→Y(1400)→B(1600)→A에서 Y를 삭제해 봅시다. previous=A, deleteNode=Y이므로 A.link=Y.link=1600으로 바꾸고 Y를 해제합니다. 남은 구조는 A→B→A이며 마지막 B의 링크는 여전히 머리 A를 가리킵니다.

삭제 위치	반드시 다시 연결할 것	추가로 확인할 것
중간 노드	직전 노드 → 삭제 노드의 다음 노드	머리는 그대로인지
머리 노드	마지막 노드 → 새 머리	head를 새 머리로 갱신했는지
유일한 노드	연결할 남은 노드 없음	삭제 뒤 head=NULL인지

강의의 삭제 그림은 중간 노드를 중심으로 링크 우회를 보여 줍니다. 이를 경계 위치에 적용할 때는 머리와 마지막 링크도 함께 관리해야 합니다. 특히 머리를 삭제하면서 마지막 링크가 옛 머리를 계속 가리키면 해제된 노드로 순환하는 잘못된 구조가 됩니다.

이중 연결 리스트는 노드 하나에 양쪽 이웃의 주소를 둔다

이중 연결 리스트의 노드는 이전 노드를 가리키는 Llink, 데이터, 다음 노드를 가리키는 Rlink를 갖습니다. 머리 구조는 첫 노드를 가리키는 Fhead와 마지막 노드를 가리키는 Lhead를 함께 관리합니다. 빈 리스트에서는 둘 다 NULL입니다.

첫 노드가 들어오면 그 노드는 첫 노드이자 마지막 노드입니다. 따라서 Fhead와 Lhead가 같은 노드를 가리키고, 노드의 Llink와 Rlink는 모두 NULL입니다. 내부 노드 X에서는 다음 두 관계가 서로 맞아야 합니다.

• X의 다음 노드가 R이라면 X.Rlink=R이고 R.Llink=X여야 합니다.
• X의 이전 노드가 L이라면 X.Llink=L이고 L.Rlink=X여야 합니다.

비용과 이점: 이중 링크는 현재 노드에서 이전 노드를 직접 찾게 해 주지만, 노드마다 링크를 하나 더 저장하고 수정 때 양쪽 관계를 함께 갱신해야 합니다. 탐색 편의와 저장·갱신 부담을 맞바꾸는 구조입니다.

이중 삽입은 네 개의 이웃 관계를 모두 맞춰야 한다

강의자료는 내부 노드 prevNode 뒤에 newNode를 넣는 네 번의 갱신을 보여 줍니다. 기존 다음 노드를 R이라고 하면 결과는 P↔N↔R이어야 합니다.

newNode->Rlink = prevNode->Rlink
prevNode->Rlink = newNode
newNode->Llink = prevNode
newNode->Rlink->Llink = newNode

학습용으로 P의 주소가 2200, R의 주소가 3000이고 새 노드 N의 주소가 2600이라고 합시다. 삽입 전에는 P.Rlink=3000, R.Llink=2200입니다. 삽입 후에는 P.Rlink=2600, N.Llink=2200, N.Rlink=3000, R.Llink=2600이 되어야 합니다.

검사 방향	삽입 뒤 경로	확인할 링크
왼쪽에서 오른쪽	P→N→R	P.Rlink=N, N.Rlink=R
오른쪽에서 왼쪽	R→N→P	R.Llink=N, N.Llink=P

한쪽 방향만 따라가며 검사하면 절반의 오류를 놓칠 수 있습니다. 예를 들어 R.Llink를 P에서 N으로 바꾸지 않아도 P에서 오른쪽으로는 P→N→R이 정상처럼 보입니다. 그러나 R에서 왼쪽으로 이동하면 N을 건너뛰고 P로 가므로 이중 연결 관계가 깨져 있습니다.

위 코드는 새 노드 오른쪽에 R이 있는 내부 삽입을 전제로 합니다. 마지막 뒤에 삽입할 때는 newNode->Rlink가 NULL이므로 이를 역참조하지 않고 Lhead를 새 노드로 옮겨야 합니다. 코드 식을 외우기보다 이웃의 존재 여부를 먼저 확인해야 하는 이유입니다.

이중 삭제는 삭제 노드의 양쪽 이웃을 직접 맞붙인다

내부 노드 D의 왼쪽을 L, 오른쪽을 R이라고 하면 삭제 뒤에는 L과 R이 서로 이웃이 되어야 합니다. D가 기억하는 두 주소를 이용해 L.Rlink=R, R.Llink=L로 바꾼 다음 D를 해제합니다.

deleteNode->Llink->Rlink = deleteNode->Rlink
deleteNode->Rlink->Llink = deleteNode->Llink
free(deleteNode)

강의의 100↔300↔500 구조에서 300을 삭제하면 100의 오른쪽 링크가 500을, 500의 왼쪽 링크가 100을 가리켜야 합니다. 첫 번째 대입만 수행하면 왼쪽에서 오른쪽으로는 300을 우회하지만, 500에서 왼쪽으로 갈 때 여전히 삭제된 300을 가리킵니다. 그래서 두 방향 갱신은 한 쌍입니다.

머리나 마지막 노드를 삭제할 때는 한쪽 이웃이 없습니다. 이때 존재하지 않는 이웃을 역참조하지 말고 각각 Fhead 또는 Lhead를 갱신해야 합니다. 유일한 노드를 삭제하면 두 머리 포인터 모두 NULL이 되어야 합니다.

포인터 변경 감사법: ① 삭제·삽입 위치의 왼쪽과 오른쪽 이웃을 이름 붙이고, ② 덮어쓸 주소를 먼저 보존하며, ③ 정방향과 역방향을 각각 따라가고, ④ 머리·마지막·유일 노드인지 확인한 뒤, ⑤ 연결이 완성된 후 메모리를 해제합니다.

새 문제는 이동 요구와 불변식으로 결정한다

연결 리스트 변형 문제를 만나면 코드 조각부터 고르지 말고 다음 순서로 판단합니다.

1. 이동 요구를 정한다. 다음 방향만 필요한지, 현재 위치에서 이전 방향도 자주 필요한지 묻습니다.
2. 끝 처리를 정한다. 마지막에서 멈출지, 첫 노드로 돌아가 계속 순환할지 정합니다.
3. 경계 위치를 분류한다. 빈 리스트, 유일한 노드, 머리, 중간, 마지막 중 어디인지 확인합니다.
4. 기존 주소를 보존한다. 링크를 덮어쓰기 전에 그 링크가 가리키던 다음·이전 노드를 임시 포인터나 새 링크에 기록합니다.
5. 불변식을 양방향으로 검사한다. 원형이면 다시 머리로 돌아오는지, 이중이면 서로 이웃인 두 링크가 역관계를 이루는지 확인합니다.

이 절차를 따르면 대입문의 암기 부담이 줄어듭니다. 삽입은 새 노드로 들어오고 나가는 경로를 만드는 작업이고, 삭제는 삭제 노드를 거치던 경로를 양쪽 이웃 사이의 직접 경로로 바꾸는 작업입니다. 구조마다 달라지는 것은 유지해야 할 머리·마지막 포인터와 이동 방향의 수입니다.

핵심 개념 정리

• 단순 연결의 한계: 다음 노드는 직접 찾지만 직전 노드는 머리부터 다시 탐색해야 합니다.
• 원형 구조: 마지막 노드가 첫 노드를 가리키며, 탐색은 NULL이 아니라 머리로 되돌아왔는지로 종료합니다.
• 원형 삽입·삭제: 기존 다음 주소를 보존한 뒤 새 경로를 만들고, 머리 삭제에서는 마지막 링크도 새 머리로 바꿉니다.
• 이중 구조: Llink와 Rlink로 이전·다음 노드를 직접 가리키며 양방향 링크가 서로 일치해야 합니다.
• 이중 삽입·삭제: 왼쪽→오른쪽과 오른쪽→왼쪽 경로를 모두 갱신하고 경계에서는 Fhead와 Lhead를 따로 처리합니다.

구조 이름보다 먼저 필요한 이동을 고르세요. 순환이 필요하면 마지막 링크의 목적지를 머리로 만들고, 양방향 이동이 필요하면 각 이웃이 서로를 가리키게 합니다. 포인터를 바꿀 때는 기존 주소 보존 → 새 경로 연결 → 머리·마지막 갱신 → 정방향·역방향 검산 순서를 지키면, 원형과 이중 연결 리스트의 삽입·삭제를 새 주소 예제에서도 재현할 수 있습니다.

예상문제 10선

1. 원형 연결 리스트와 이중 연결 리스트의 차이를 가장 정확히 설명한 것은?

① 원형은 링크가 두 개이고 이중은 링크가 한 개다. ② 원형은 끝 링크의 연결 방식을, 이중은 노드가 기억하는 이동 방향을 나타낸다. ③ 원형은 이전 방향으로만, 이중은 다음 방향으로만 이동한다. ④ 원형과 이중은 동시에 적용할 수 없는 배타적 구조다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 원형 여부는 링크 수가 아니라 마지막 링크가 머리로 이어지는지를 뜻한다.
• ② 정답: 두 분류는 각각 끝 처리와 이동 방향이라는 서로 다른 기준을 설명한다.
• ③ 오답: 단일 원형은 다음 방향으로 움직이며, 이중 구조는 이전과 다음 방향을 모두 제공한다.
• ④ 오답: 두 기준을 결합한 이중 원형 연결 리스트도 만들 수 있다.

2. 노드가 하나뿐인 원형 연결 리스트에서 반드시 성립하는 상태는?

① 노드의 링크가 NULL이다. ② 머리 포인터가 NULL이다. ③ 노드의 링크가 별도의 마지막 포인터를 가리킨다. ④ 머리가 그 노드를 가리키고 노드의 링크도 자기 자신을 가리킨다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 링크가 NULL이면 원형이 끊어져 단순 리스트의 끝처럼 된다.
• ② 오답: 머리가 NULL이면 빈 리스트를 나타내므로 노드 하나가 있다는 조건과 모순된다.
• ③ 오답: 노드 하나인 경우 그 노드가 첫 노드와 마지막 노드의 역할을 모두 한다.
• ④ 정답: 유일한 노드에서 다음 링크를 따라도 같은 머리로 돌아와 원형 불변식이 유지된다.

3. 비어 있지 않은 원형 리스트의 맨 앞에 새 노드를 넣을 때 안전한 갱신 순서는?

① 새 노드→옛 머리, 마지막→새 노드, 머리→새 노드 ② 머리→새 노드, 새 노드→NULL, 마지막→옛 머리 ③ 마지막→NULL, 머리→새 노드, 새 노드→마지막 ④ 옛 머리→새 노드, 새 노드→마지막, 머리는 그대로

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 옛 머리 주소를 새 노드에 먼저 보존하고 원을 닫은 뒤 머리를 옮긴다.
• ② 오답: 새 노드가 NULL을 가리키면 순환이 끊어지고 옛 머리 경로도 보존되지 않는다.
• ③ 오답: 마지막 링크를 NULL로 만들면 원형 불변식을 먼저 깨뜨린다.
• ④ 오답: 맨 앞 삽입인데 머리를 그대로 두며 링크 방향도 필요한 경로와 다르다.

4. A(1200)→B(1600)→A인 원형 리스트에서 Y(1400)를 A 뒤에 삽입한 결과는?

① A.link=1600, Y.link=1200 ② A.link=1400, Y.link=1200 ③ A.link=1400, Y.link=1600 ④ A.link=1200, Y.link=1600

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: A가 여전히 B를 가리켜 Y로 들어오는 경로가 없고, Y는 머리 A로 돌아가 B를 건너뛴다.
• ② 오답: A에서 Y로는 가지만 Y가 B가 아닌 A를 가리켜 B가 순환 경로에서 빠진다.
• ③ 정답: A→Y→B의 새 경로가 생기고 기존 B.link=1200으로 다시 A에 돌아온다.
• ④ 오답: A가 자기 자신을 가리켜 Y와 B에 도달하지 못한다.

5. 원형 리스트 탐색을 current=head로 시작하면서 반복 조건을 처음부터 while current != head로 검사하면 생기는 문제는?

① 마지막 노드만 두 번 검사한다. ② 조건이 처음부터 거짓이어서 첫 노드도 검사하지 않는다. ③ NULL을 만날 때까지 무조건 반복한다. ④ 이전 노드를 자동으로 찾게 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 반복문 본문 자체가 실행되지 않으므로 마지막 노드를 검사할 기회도 없다.
• ② 정답: 초기값에서 current==head이므로 먼저 방문하는 do...while 방식이 필요하다.
• ③ 오답: 정상 원형 리스트에는 끝을 나타내는 NULL이 없지만, 이 코드에서는 그 전에 반복이 시작되지 않는다.
• ④ 오답: 이전 노드는 별도 포인터로 현재 노드와 함께 이동시켜야 한다.

6. A→Y→B→A인 단일 원형 리스트에서 Y를 삭제할 때 가장 먼저 보존해 연결에 사용할 정보는?

① Y의 다음 노드 B를 가리키는 주소 ② Y의 데이터 값만 복사한 주소 ③ 머리 A를 NULL로 바꾼 값 ④ 마지막 B의 링크를 NULL로 바꾼 값

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 직전 A가 Y를 우회해 B를 가리키려면 해제 전에 Y.link가 가진 B 주소가 필요하다.
• ② 오답: 데이터 값은 노드 사이의 경로를 복원하는 포인터 정보가 아니다.
• ③ 오답: 중간 노드 삭제에서 머리를 비우면 남은 A와 B를 잃는다.
• ④ 오답: B의 링크를 NULL로 만들면 원형 연결이 끊어진다.

7. 이중 연결 리스트의 내부 노드 X와 그 다음 노드 R 사이에서 성립해야 하는 관계는?

① X.Llink=R이고 R.Llink=X ② X.Rlink=R이고 R.Rlink=X ③ X.Llink=R이고 R.Rlink=X ④ X.Rlink=R이고 R.Llink=X

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: X의 왼쪽 링크는 이전 노드를 가리켜야 하므로 다음 노드 R을 가리키지 않는다.
• ② 오답: R의 오른쪽 링크는 R의 다음 노드를 가리키며 직전 노드 X의 주소는 왼쪽 링크에 둔다.
• ③ 오답: 두 링크 모두 이웃 관계의 반대 방향을 사용해 X와 R을 서로 연결하지 못한다.
• ④ 정답: X의 오른쪽 이동과 R의 왼쪽 이동이 서로를 가리켜 양방향 이웃 관계가 맞는다.

8. 이중 리스트 P↔R 사이에 N을 넣은 뒤 필요한 네 링크 값으로 옳은 것은?

① P.Rlink=R, N.Llink=P, N.Rlink=R, R.Llink=P ② P.Rlink=N, N.Llink=R, N.Rlink=P, R.Llink=N ③ P.Rlink=N, N.Llink=P, N.Rlink=R, R.Llink=N ④ P.Llink=N, N.Llink=P, N.Rlink=R, R.Rlink=N

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: P와 R의 기존 링크가 그대로라서 N으로 들어오는 경로가 없다.
• ② 오답: N의 왼쪽과 오른쪽 이웃을 뒤바꾸어 P→N→R 방향과 일치하지 않는다.
• ③ 정답: 오른쪽으로 P→N→R, 왼쪽으로 R→N→P를 모두 따라갈 수 있다.
• ④ 오답: P와 R의 바깥쪽 링크를 바꾸어 내부 이웃 관계를 연결하지 못한다.

9. 이중 리스트 L↔D↔R에서 D를 삭제하며 L.Rlink=R만 수행한 상태의 오류는?

① R에서 왼쪽으로 이동하면 여전히 삭제 노드 D를 가리킨다. ② L에서 오른쪽으로 이동하면 반드시 NULL을 만난다. ③ D의 데이터가 자동으로 R에 복사된다. ④ 첫 노드와 마지막 노드가 자동으로 서로 연결되어 원형이 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 역방향 경로를 고치려면 R.Llink=L도 수행해야 삭제 노드를 완전히 우회한다.
• ② 오답: L.Rlink=R이므로 L에서 오른쪽으로는 R에 도달한다.
• ③ 오답: 링크 대입은 주소 관계만 바꾸며 노드의 데이터 값을 복사하지 않는다.
• ④ 오답: 내부 링크 하나를 바꾼다고 양 끝 링크가 연결되지는 않는다.

10. 연결 리스트 변형과 갱신을 결정하는 가장 안전한 순서는?

① 대입문 암기 → 노드 해제 → 이동 방향 결정 → 경계 확인 ② 메모리 해제 → 머리 변경 → 기존 주소 읽기 → 구조 선택 ③ 링크 수 결정 → 데이터 복사 → 모든 링크를 NULL로 초기화 → 탐색 ④ 이동 요구·끝 처리 결정 → 경계 분류 → 기존 주소 보존 → 연결 갱신 → 불변식 검산

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 연결을 완성하기 전에 노드를 해제하면 다음 주소를 잃을 수 있고 구조 선택도 근거가 없다.
• ② 오답: 해제된 노드에서 기존 주소를 읽으려는 역순이므로 안전하지 않다.
• ③ 오답: 모든 링크를 NULL로 만들면 원형·이중 관계가 끊어지며 데이터 복사도 구조 선택 기준이 아니다.
• ④ 정답: 요구에 맞는 구조를 고르고 경계와 주소를 확인한 뒤 연결과 불변식을 검증하는 재현 가능한 절차다.

참고 자료와 작성 기준

• 자료 성격: 이 글은 강의자료를 바탕으로 개념 관계와 포인터 갱신 절차를 재구성한 비공식 학습자료입니다.
• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 자료구조 6강 「연결 리스트의 응용」 강의록(2023)
• 보충 설명: 주소 추적 예제와 경계 조건 점검은 학습을 위해 직접 구성했으며 외부 자료는 사용하지 않았습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토일: 2026년 8월 18일