방송대 방통대 자료구조 6강 - 원형 연결 리스트와 이중 연결 리스트 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 6강 - 원형 연결 리스트와 이중 연결 리스트

단순 연결 리스트의 한계를 살펴보고 이를 보완하는 원형 연결 리스트와 이중 연결 리스트를 학습합니다. 각 구조의 링크 방향을 이해한 뒤 노드 생성·삽입·검색·삭제에서 포인터를 어떤 순서로 바꾸는지 단계적으로 정리합니다.

연결 리스트의 변형

단순 연결 리스트의 한계

단순 연결 리스트의 각 노드는 데이터와 하나의 링크를 가지며, 링크는 다음 노드만 가리킵니다. 따라서 어떤 노드에서 후속 노드로 이동하기는 쉽지만 선행 노드로 직접 이동할 수 없습니다. 이미 지나온 노드로 돌아가려면 헤드부터 다시 탐색해야 합니다.

핵심 문제 단순 연결 리스트는 링크의 방향이 한쪽뿐이므로 역방향 접근이 어렵고, 마지막 노드의 링크가 NULL이어서 끝에서 처음으로 곧바로 이어지지 않습니다.

이 한계를 보완하는 대표적인 변형이 원형 연결 리스트와 이중 연결 리스트입니다. 원형 연결 리스트는 마지막 노드에서 첫 노드로 다시 연결하여 순환을 만들고, 이중 연결 리스트는 선행 노드와 후속 노드를 가리키는 링크를 모두 둡니다. 두 성질을 결합하면 이중 원형 연결 리스트도 만들 수 있습니다.

구조	노드의 링크	마지막 연결	주요 특징
단순 연결 리스트	후속 노드 링크 1개	NULL	앞 방향 탐색만 직접 가능
이중 연결 리스트	선행·후속 링크 2개	선형 구조라면 끝 링크는 NULL	양방향 이동 가능
단순 원형 연결 리스트	후속 노드 링크 1개	첫 노드	어느 노드에서든 순환 가능
이중 원형 연결 리스트	선행·후속 링크 2개	앞뒤 방향 모두 원형 연결	양방향 순환 가능

원형 연결 리스트의 구조와 생성

마지막 노드가 첫 노드를 가리키는 구조

원형 연결 리스트에서는 마지막 노드의 링크가 NULL이 아니라 첫 노드를 가리킵니다. 따라서 마지막 원소 뒤에 아무 원소도 없다는 선형 리스트의 가정을 없애고, 한 방향으로 계속 이동하면 다시 출발 노드로 돌아옵니다. 반복적인 순번 처리나 순환 일정처럼 끝 다음에 처음이 이어지는 문제에 적합합니다.

종료 조건 링크가 NULL인지 검사하는 대신 현재 포인터가 다시 시작 노드와 같아졌는지를 검사합니다. 종료 조건을 잘못 잡으면 무한 반복이 생길 수 있습니다.

헤드 구조에는 첫 노드를 가리키는 포인터를 둡니다. 초기 상태에서는 헤드의 포인터가 NULL입니다. 새 노드를 만들 때는 메모리를 할당하고 데이터를 저장한 뒤 링크를 초기화합니다. 첫 노드를 삽입하면 헤드가 새 노드를 가리키고, 새 노드의 링크도 자기 자신을 가리키게 하여 길이 1인 원을 완성합니다.

상태	헤드의 값	마지막 노드의 링크
공백 리스트	NULL	노드가 없으므로 해당 없음
노드 1개	유일한 노드	자기 자신
노드 2개 이상	첫 노드	첫 노드

원형 연결 리스트의 삽입

첫 위치에 삽입하기

공백 리스트에 첫 노드를 삽입할 때는 헤드가 새 노드를 가리키게 하고 새 노드의 링크도 새 노드를 가리키게 합니다. 기존 노드가 있는 리스트의 첫 위치에 삽입하려면 마지막 노드를 먼저 찾습니다. 새 노드가 기존 첫 노드를 가리키게 하고, 마지막 노드의 링크를 새 노드로 바꾼 다음 헤드가 새 노드를 가리키게 합니다.

1. 마지막 노드의 링크가 현재 첫 노드인지 확인하며 마지막 노드를 찾습니다.
2. 새 노드의 링크를 기존 첫 노드로 설정합니다.
3. 마지막 노드의 링크를 새 노드로 변경합니다.
4. 헤드의 첫 노드 포인터를 새 노드로 변경합니다.

이 순서를 지키면 기존 원형 연결을 잃지 않은 채 새 노드를 첫 노드로 만들 수 있습니다. 헤드를 너무 일찍 바꾸거나 기존 첫 노드의 주소를 보관하지 않으면 연결이 끊길 수 있습니다.

특정 노드 뒤에 삽입하기

새 노드를 prevNode 뒤에 넣을 때는 먼저 새 노드의 링크가 prevNode의 기존 후속 노드를 가리키게 합니다. 그 다음 prevNode의 링크를 새 노드로 바꿉니다. 즉, 새 연결의 출구를 먼저 확보한 뒤 입구를 바꾸는 순서입니다.

포인터 갱신 NewNode->link = prevNode->link를 먼저 수행하고, 이어서 prevNode->link = NewNode를 수행합니다. 순서를 반대로 하면 기존 후속 노드의 주소를 잃을 수 있습니다.

원형 연결 리스트의 검색과 삭제

한 바퀴를 기준으로 검색하기

검색은 공백 여부를 먼저 확인한 뒤 첫 노드부터 시작합니다. 현재 노드의 데이터가 목표값과 같은지 검사하고, 아니면 prevNode를 현재 노드로 옮긴 뒤 현재 노드를 다음 노드로 이동합니다. 다시 첫 노드에 도달할 때까지 반복했는데 목표값을 찾지 못하면 검색 실패입니다.

첫 노드도 반드시 검사해야 하므로 do-while 형태의 반복이 자연스럽습니다. 조건을 먼저 검사하는 반복문을 사용할 경우 첫 노드 검사와 한 바퀴 종료 조건을 별도로 세심하게 처리해야 합니다.

삭제 대상의 선행 노드가 필요한 이유

삭제 대상 delNode를 찾았으면 prevNode의 링크가 delNode의 다음 노드를 가리키게 하여 delNode를 연결망에서 제외합니다. 그 뒤 delNode의 메모리를 해제합니다. 삭제 대상이 첫 노드이면 헤드도 다음 노드로 바꾸고, 마지막 노드가 새 첫 노드를 가리키도록 갱신해야 원이 유지됩니다.

첫 노드 삭제 단순히 헤드만 다음 노드로 옮기면 마지막 노드는 여전히 삭제된 노드를 가리킵니다. 마지막 노드의 링크까지 새 첫 노드로 변경해야 합니다.

노드가 하나뿐인 리스트에서 그 노드를 삭제하면 헤드는 NULL이 되어야 합니다. 일반적인 여러 노드 삭제 코드만 적용하면 해제된 노드를 자기 자신이 가리키는 잘못된 상태가 남을 수 있으므로 단일 노드 경계 조건을 분리하는 것이 안전합니다.

이중 연결 리스트의 구조

선행 노드와 후속 노드를 모두 가리키기

이중 연결 리스트의 각 노드는 선행 노드를 가리키는 Llink, 데이터, 후속 노드를 가리키는 Rlink를 가집니다. 한 노드에서 앞뒤 어느 방향으로도 이동할 수 있어 특정 노드의 선행 노드를 찾기 위해 헤드부터 다시 탐색할 필요가 없습니다.

강의록의 헤드 구조는 첫 노드를 가리키는 Fhead와 마지막 노드를 가리키는 Lhead를 둡니다. 공백 리스트에서는 두 포인터가 모두 NULL입니다. 노드가 생기면 양 끝의 포인터와 각 노드의 Llink·Rlink 관계를 일관되게 유지해야 합니다.

필드	가리키는 대상
Llink	현재 노드의 선행 노드
data	현재 노드에 저장한 데이터
Rlink	현재 노드의 후속 노드
Fhead	리스트의 첫 노드
Lhead	리스트의 마지막 노드

비용과 장점 노드마다 링크가 하나 더 필요해 기억 공간과 갱신 작업이 늘어나지만, 양방향 탐색과 특정 노드 삭제가 쉬워집니다.

이중 연결 리스트의 삽입과 삭제

prevNode 뒤에 새 노드 삽입하기

새 노드를 prevNode와 기존 후속 노드 사이에 넣으려면 네 방향의 연결을 맞춰야 합니다. 새 노드의 Rlink를 기존 후속 노드로, prevNode의 Rlink를 새 노드로, 새 노드의 Llink를 prevNode로, 기존 후속 노드의 Llink를 새 노드로 바꿉니다.

1. NewNode->Rlink = prevNode->Rlink
2. prevNode->Rlink = NewNode
3. NewNode->Llink = prevNode
4. NewNode->Rlink->Llink = NewNode

이 예시는 prevNode 뒤에 실제 후속 노드가 있는 중간 삽입입니다. 맨 앞이나 맨 뒤에 삽입할 때는 NULL 링크와 Fhead·Lhead를 별도로 갱신해야 합니다.

delNode 삭제하기

중간 노드 delNode를 삭제할 때는 선행 노드의 Rlink가 delNode의 후속 노드를 가리키게 하고, 후속 노드의 Llink가 delNode의 선행 노드를 가리키게 합니다. 양쪽 이웃을 서로 직접 연결한 뒤 delNode의 메모리를 해제합니다.

삭제 핵심식 delNode->Llink->Rlink = delNode->Rlink, delNode->Rlink->Llink = delNode->Llink를 수행한 뒤 free(delNode)합니다.

첫 노드나 마지막 노드를 삭제하면 한쪽 이웃이 없으므로 위의 중간 노드 코드만 그대로 사용할 수 없습니다. 첫 노드 삭제에서는 Fhead와 새 첫 노드의 Llink를, 마지막 노드 삭제에서는 Lhead와 새 마지막 노드의 Rlink를 조정해야 합니다.

핵심 개념 정리

• 단순 연결 리스트는 후속 노드로만 직접 이동할 수 있어 선행 노드 접근이 어렵습니다.
• 원형 연결 리스트는 마지막 노드가 첫 노드를 가리키므로 NULL 대신 시작점 재도달을 종료 조건으로 사용합니다.
• 원형 리스트 삽입·삭제에서는 마지막 노드와 첫 노드의 연결을 함께 보존해야 합니다.
• 이중 연결 리스트의 노드는 Llink와 Rlink를 가져 양방향 이동이 가능합니다.
• 이중 리스트의 삽입·삭제에서는 새 노드 또는 삭제 노드 양쪽의 링크를 모두 갱신해야 합니다.

최종 암기 문장 원형 리스트는 “마지막이 처음을 가리킨다”, 이중 리스트는 “앞 링크와 뒤 링크를 쌍으로 고친다”가 핵심입니다.

예상문제 20선

연결 리스트 변형의 구조와 포인터 갱신 과정을 확인하는 문제입니다. 각 문항에서 하나의 답을 선택한 뒤 해설로 판단 근거를 점검하세요.

1. 단순 연결 리스트의 각 노드가 직접 가리키는 것은?

① 선행 노드와 후속 노드 모두 ② 후속 노드 ③ 항상 첫 노드 ④ 항상 마지막 노드

정답입니다.

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

정답 및 해설 보기

정답: ②
단순 연결 리스트의 링크는 다음 노드, 즉 후속 노드만 가리킵니다.

2. 단순 연결 리스트에서 선행 노드 접근이 어려운 이유는?

① 모든 노드의 주소가 같아서 ② 데이터 필드가 없어서 ③ 마지막 노드가 첫 노드를 가리켜서 ④ 링크가 후속 노드 방향으로만 존재해서

정답입니다.

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

정답 및 해설 보기

정답: ④
역방향 링크가 없으므로 선행 노드를 찾으려면 헤드부터 다시 탐색해야 합니다.

3. 단순 원형 연결 리스트의 마지막 노드 링크가 가리키는 것은?

① 첫 노드 ② NULL ③ 자기 자신의 데이터 필드 ④ 헤드 구조의 주소만

정답입니다.

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

정답 및 해설 보기

정답: ①
원형 구조를 만들기 위해 마지막 노드는 첫 노드로 연결됩니다.

4. 원형 연결 리스트를 순회할 때 적절한 종료 조건은?

① 링크가 항상 NULL인지 확인한다. ② 데이터가 0인지 확인한다. ③ 현재 포인터가 다시 시작 노드에 도달했는지 확인한다. ④ 노드 주소가 감소하는지 확인한다.

정답입니다.

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

정답 및 해설 보기

정답: ③
원형 리스트에는 끝의 NULL이 없으므로 한 바퀴 돌아 시작점에 재도달했는지 검사합니다.

5. 공백 원형 연결 리스트의 헤드 포인터 값은?

① 항상 자기 자신 ② 마지막 노드 ③ NULL ④ 임의의 정수 1

정답입니다.

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

정답 및 해설 보기

정답: ③
노드가 하나도 없을 때 헤드는 가리킬 노드가 없어 NULL입니다.

6. 노드가 하나뿐인 원형 연결 리스트에서 그 노드의 링크는?

① 자기 자신을 가리킨다. ② 항상 NULL이다. ③ 헤드 구조만 가리킨다. ④ 새 메모리를 자동 할당한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
하나의 노드만으로 원을 만들려면 그 링크가 자신을 가리켜야 합니다.

7. 기존 원형 리스트의 첫 위치에 새 노드를 삽입할 때 찾아야 하는 노드는?

① 항상 두 번째 노드 ② 데이터가 가장 큰 노드 ③ NULL 노드 ④ 마지막 노드

정답입니다.

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

정답 및 해설 보기

정답: ④
마지막 노드의 링크도 새 첫 노드를 가리키도록 바꿔야 하므로 마지막 노드를 찾습니다.

8. 원형 리스트 첫 위치 삽입에서 새 노드의 링크가 먼저 가리켜야 하는 것은?

① 항상 NULL ② 기존 첫 노드 ③ 기존 마지막 노드의 선행 노드 ④ 헤드 구조의 데이터

정답입니다.

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

정답 및 해설 보기

정답: ②
새 노드가 기존 리스트의 앞에 연결되도록 기존 첫 노드 주소를 보존합니다.

9. prevNode 뒤에 NewNode를 삽입할 때 먼저 수행할 연결은?

① NewNode의 링크를 prevNode의 기존 후속 노드로 설정한다. ② prevNode의 링크를 먼저 NULL로 만든다. ③ 헤드를 무조건 NewNode로 바꾼다. ④ 기존 후속 노드를 해제한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
기존 후속 노드의 주소를 잃지 않도록 새 노드의 출구를 먼저 연결합니다.

10. 원형 연결 리스트 검색에 do-while 방식이 자연스러운 이유는?

① 링크가 항상 NULL이어서 ② 데이터를 정렬하기 위해서 ③ 메모리를 해제하기 위해서 ④ 첫 노드를 검사한 뒤 시작점 재도달 여부를 판단할 수 있어서

정답입니다.

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

정답 및 해설 보기

정답: ④
첫 노드도 검색 대상이므로 먼저 처리하고 이후 한 바퀴 완료를 검사하는 방식이 알맞습니다.

11. 원형 리스트에서 노드를 삭제할 때 prevNode가 필요한 주된 이유는?

① 삭제 노드의 데이터를 정렬하기 위해서 ② prevNode의 링크를 삭제 노드의 후속 노드로 바꾸기 위해서 ③ 노드를 새로 할당하기 위해서 ④ 모든 주소를 0으로 만들기 위해서

정답입니다.

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

정답 및 해설 보기

정답: ②
단순 링크 구조에서는 선행 노드를 통해 삭제 대상을 건너뛰도록 연결해야 합니다.

12. 원형 리스트의 첫 노드를 삭제할 때 추가로 바꾸어야 하는 연결은?

① 모든 노드의 데이터 값 ② 새 첫 노드의 메모리 크기 ③ 마지막 노드가 새 첫 노드를 가리키도록 하는 링크 ④ 중간 노드의 주소 순서

정답입니다.

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

정답 및 해설 보기

정답: ③
헤드만 옮기면 마지막 노드가 삭제된 노드를 계속 가리키므로 마지막 링크도 갱신합니다.

13. 원형 리스트의 유일한 노드를 삭제한 뒤 헤드는 어떻게 되어야 하는가?

① 삭제된 노드를 계속 가리킨다. ② 임의의 새 노드를 가리킨다. ③ 항상 마지막 노드 주소 1을 가진다. ④ NULL

정답입니다.

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

정답 및 해설 보기

정답: ④
모든 노드가 사라졌으므로 리스트는 공백 상태가 되고 헤드는 NULL입니다.

14. 이중 연결 리스트 노드의 기본 구성은?

① Llink, data, Rlink ② data와 링크 하나만 ③ Fhead와 Lhead만 ④ top과 rear만

정답입니다.

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

정답 및 해설 보기

정답: ①
이중 연결 리스트 노드는 선행 링크, 데이터, 후속 링크를 가집니다.

15. 이중 연결 리스트의 Llink가 가리키는 것은?

① 후속 노드 ② 항상 첫 노드 ③ 선행 노드 ④ 노드의 데이터 값

정답입니다.

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

정답 및 해설 보기

정답: ③
Llink는 현재 노드의 앞쪽 이웃인 선행 노드를 가리킵니다.

16. 강의록의 이중 연결 리스트 헤드에서 Fhead가 가리키는 것은?

① 마지막 노드 ② 첫 노드 ③ 삭제할 노드 ④ 항상 NULL

정답입니다.

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

정답 및 해설 보기

정답: ②
Fhead는 first head로 리스트의 첫 노드를 가리킵니다.

17. 강의록의 이중 연결 리스트 헤드에서 Lhead가 가리키는 것은?

① 첫 노드 ② 마지막 노드 ③ 항상 선행 노드 ④ 새 노드만

정답입니다.

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

정답 및 해설 보기

정답: ②
Lhead는 리스트의 마지막 노드를 가리키는 헤드 포인터입니다.

18. 이중 연결 리스트의 장점은?

① 노드마다 링크가 전혀 필요 없다. ② 모든 삽입이 링크 갱신 없이 가능하다. ③ 데이터가 자동으로 정렬된다. ④ 한 노드에서 선행·후속 방향으로 모두 이동할 수 있다.

정답입니다.

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

정답 및 해설 보기

정답: ④
두 링크를 이용하므로 양방향 탐색이 직접 가능합니다.

19. 이중 연결 리스트의 중간 노드 삽입 시 갱신해야 할 관계는?

① 새 노드의 데이터만 ② 헤드 포인터 하나만 ③ 새 노드 양쪽과 두 이웃 사이의 앞뒤 링크 ④ 마지막 노드의 데이터만

정답입니다.

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

정답 및 해설 보기

정답: ③
양방향 일관성을 위해 새 노드와 선행·후속 노드의 링크를 모두 연결해야 합니다.

20. 이중 연결 리스트에서 중간 delNode를 삭제하는 올바른 관점은?

① delNode의 선행 노드와 후속 노드를 서로 직접 연결한 뒤 해제한다. ② delNode의 데이터만 0으로 바꾼다. ③ 모든 노드를 헤드부터 해제한다. ④ 후속 노드를 반드시 새로 생성한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
양쪽 이웃이 서로 가리키도록 링크를 고친 뒤 삭제 노드의 메모리를 해제합니다.