I-3 단일 연결 리스트 — 노드 그림 하나로 네 선택지 해부하기
먼저 이 문제의 정체부터
연결 리스트 문제는 머릿속에서만 풀면 포인터가 쉽게 꼬입니다. 가장 먼저 Node(value,next) 세 칸짜리 그림과 \(\text{head}\to a\to b\to \text{nil}\)head→a→b→nil을 그리세요. 단일 연결(einfach verkettet)이라는 말은 각 노드가 다음 노드로 가는 next 링크를 갖는다는 뜻이지, 이전 노드 prev까지 갖는다는 뜻이 아닙니다.
이 문제의 핵심은 세 가지입니다. 임의 인덱스 직접 접근이 가능한가, 뒤로 이동할 수 있는가, 끝 삽입에 몇 번의 순회가 필요한가입니다. 모두 '현재 노드가 어떤 주소를 알고 있는가'에서 답이 나옵니다.
정답 A의 'höchstens zwei Traversierungen'는 정확히 두 번이 아니라 최대 두 번이라는 뜻입니다. tail pointer가 없으면 두 번 append할 때 최대 두 번 순회하고, tail pointer가 있으면 아예 순회하지 않을 수도 있으므로 둘 다 이 상한을 만족합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 배열과 연결 리스트의 저장 방식
배열은 원소가 연속된 주소에 있어 시작 주소와 인덱스로 A[i]의 위치를 계산할 수 있습니다. 연결 리스트의 노드는 메모리 여기저기에 있을 수 있고, 다음 노드 주소를 next에 저장해 연결합니다.
따라서 연결 리스트에서 i번째 노드의 주소는 head에서 next를 i번 따라가기 전에는 일반적으로 알 수 없습니다. 이것이 direct access와 sequential access의 차이입니다.
수식으로 정확히 쓰기
배열 접근 A[i]
Θ(1)핵심 규칙단일 연결 리스트의 i번째 위치 접근: \(\Theta(i)\)Θ(i), 최악 \(\Theta(n)\)Θ(n)
이 절에서 꼭 기억할 것
- 연결 리스트는 물리적으로 연속일 필요가 없다.
- 링크를 따라가는 비용을 세어야 한다.
개념 2 · 단일 연결 노드의 최소 구조
가장 단순한 단일 연결 리스트 노드는 value와 next 하나만 있으면 됩니다. 마지막 노드의 next는 nil/null입니다. '각 원소가 최소 두 포인터를 가진다'는 말은 단일 연결의 필수 조건이 아닙니다.
prev와 next를 모두 가지는 구조는 보통 이중 연결 리스트(doppelt verkettete Liste)입니다. 추가 포인터는 뒤로 이동을 가능하게 하지만 메모리와 갱신 작업을 더 요구합니다.
수식으로 정확히 쓰기
핵심 규칙단일 연결 노드 = (value,next)
핵심 규칙이중 연결 노드 = (value,prev,next)
이 절에서 꼭 기억할 것
- \(\text{einfach}=\text{next}\)
einfach=next만 필수 - \(\text{doppelt}=\text{prev}\)
doppelt=prev와 next
개념 3 · 순회(Traversal)의 의미
순회는 보통 head에서 시작해 next를 반복하여 리스트의 일부 또는 전체를 방문하는 것입니다. tail pointer가 없을 때 끝을 찾으려면 \(\text{next}=\text{nil}\)next=nil인 노드를 만날 때까지 이동하므로 \(\Theta(n)\)Θ(n) 시간이 걸립니다.
두 번의 append를 각각 단순하게 수행하면 첫 append 전에 한 번, 두 번째 append 전에 한 번 끝을 찾을 수 있습니다. 따라서 순회 횟수는 최대 두 번입니다. 두 번째 리스트가 한 노드 길어졌어도 이것은 순회의 '횟수'가 두 번이라는 뜻이며 방문 노드 수는 더 많을 수 있습니다.
수식으로 정확히 쓰기
핵심 규칙tail 없이 append: 연산마다 \(\Theta(n)\)Θ(n)
핵심 규칙append 두 번: 전체 순회 최대 두 번, 총 \(\Theta(n)\)Θ(n)
이 절에서 꼭 기억할 것
- 순회 횟수와 방문한 노드 수를 구분한다.
- 연속 두 append가 \(\Theta(2n)\)
Θ(2n)=\(\Theta(n)\)Θ(n)이어도 순회는 최대 두 번이다.
개념 4 · tail pointer가 주는 변화
리스트가 마지막 노드 주소를 tail에 유지하면 append는 \(\text{tail}.\text{next}=\text{new}, \text{tail}=\text{new}\)tail.next=new, tail=new두 갱신으로 \(\Theta(1)\)Θ(1)에 처리할 수 있습니다. 이 경우 전체 리스트 순회는 0번입니다.
하지만 tail이 있어도 단일 연결 노드마다 prev가 생기는 것은 아닙니다. tail은 리스트 전체를 대표하는 보조 포인터 하나이고, 각 노드의 필드와는 다른 개념입니다.
수식으로 정확히 쓰기
tail이 있으면 append
Θ(1)핵심 규칙순회 0번 ≤ 순회 2번
이 절에서 꼭 기억할 것
- tail pointer는 선택적 최적화다.
- A의 'at most'는 tail 유무 모두를 포괄한다.
개념 5 · 역방향 이동이 안 되는 이유
현재 노드가 next만 알고 있으면 이전 노드의 주소는 정보에 들어 있지 않습니다. 메모리 주소를 숫자로 추측해서 이전 노드를 찾을 수 없고, head에서 다시 순회하거나 별도 stack/prev 자료를 유지해야 합니다.
따라서 '단일 연결 리스트에서 뒤로 iterate할 수 있다'를 기본 연산으로 읽으면 거짓입니다. 별도 보조 저장소를 추가한다면 가능하지만 그것은 원래 단일 연결 링크만으로 하는 것이 아닙니다.
수식으로 정확히 쓰기
핵심 규칙현재 노드에서 current.next는 알 수 있음
핵심 규칙current.prev는 저장되지 않음
이 절에서 꼭 기억할 것
- 가능성은 허용된 정보와 연산 모델 안에서 판단한다.
- 보조 자료구조를 몰래 추가하지 않는다.
1. 시험장에서 따라 할 풀이 순서
singly linked; at most
연결 리스트: \(\text{head} \to [a|\text{next}] \to [b|\text{null}]\)head → [a|next] → [b|null]
\(B=\)B=거짓
\(C=\)C=거짓, 접근 비용=\(\Theta(i)\)Θ(i)
단어를 표시한다
einfach verkettet는 단일 연결, höchstens는 최대라는 뜻입니다.
핵심 규칙singly linked; at most
최소 노드를 그린다
Node(value,next)와 \(\text{head}\to a\to b\to \text{nil}\)
head→a→b→nil을 그립니다.핵심 규칙연결 리스트: \(\text{head} \to [a|\text{next}] \to [b|\text{null}]\)
head → [a|next] → [b|null]B를 포인터 개수로 판정한다
노드마다 next 하나면 충분하므로 최소 두 포인터라는 B는 거짓입니다.
\[B=거짓\]B=거짓C를 주소 계산으로 판정한다
A[i]처럼 주소를 계산할 수 없고 head부터 따라가므로 direct index access가 아닙니다.
핵심 규칙\(C=\)
C=거짓, 접근 비용=\(\Theta(i)\)Θ(i)D를 역방향 정보로 판정한다
prev가 저장되지 않으므로 기본적으로 뒤로 iterate할 수 없습니다.
\[D=거짓\]D=거짓A의 '최대'를 정확히 읽는다
tail이 없으면 append마다 한 번씩 최대 두 번 순회합니다. tail이 있으면 0번이므로 여전히 최대 두 번 이하입니다.
핵심 규칙순회 횟수 ∈ {0,1,2} ⇒ 최대 2
참 개수를 확인한다
A만 참이며 \(\text{exactly}_{\text{one}}\)
exactly(one)조건과 일치합니다.핵심 규칙정답 A
2. 이 문제를 실제로 끝까지 풀기
단일 연결 리스트의 최소 노드를 (value,next)로 놓습니다. 이 한 그림만으로 B는 깨집니다. 모든 노드에 포인터가 최소 두 개 필요하다는 주장과 달리 next 하나만으로 유효한 단일 연결 리스트를 만들 수 있습니다.
C의 직접 인덱스 접근도 불가능합니다. 배열은 base+i·\(\text{cell}_{\text{size}}\)cell(size)로 주소를 계산하지만, 연결 리스트의 i번째 주소는 앞 노드의 next 안에 있습니다. 따라서 head에서 링크를 따라가야 하고 최악 \(\Theta(n)\)Θ(n)입니다.
D의 역방향 순회는 prev 정보가 없어서 기본적으로 불가능합니다. 이전 노드를 찾으려면 head에서 다시 검색하거나 별도 정보를 저장해야 하므로 단일 연결 리스트 자체가 제공하는 뒤로 가기라고 볼 수 없습니다.
A는 두 원소를 차례로 끝에 삽입할 때 최대 두 번의 리스트 순회가 필요하다고 말합니다. tail이 없는 보통 구현에서는 첫 append에서 한 번, 두 번째 append에서 한 번 끝을 찾습니다. tail을 유지하는 구현에서는 0번이므로 '최대 두 번'을 여전히 만족합니다.
따라서 A만 참입니다. 이 문제는 시간복잡도 \(\Theta(n)\)Θ(n)과 traversal count를 구분하고, 'exactly'가 아닌 'at most'라는 상한 문언을 정확히 읽는 것이 핵심입니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A참 — 정답 후보
tail이 없으면 두 append 각각에서 끝을 찾아 최대 두 번 순회합니다. tail이 있으면 0번이어서 역시 2 이하입니다. '정확히 두 번'이 아니라 '최대 두 번'임이 핵심입니다.
빠른 확인법: 구현별 순회 횟수 2 또는 0 모두 ≤2입니다.
-
B거짓
단일 연결 노드는 value와 next만으로 충분합니다. prev까지 있는 두 포인터 구조는 이중 연결 리스트의 전형입니다.
빠른 확인법: Node(value,next)라는 반례 하나면 universal claim이 깨집니다.
-
C거짓
임의 인덱스의 주소를 바로 계산하지 못하고 head에서 next를 따라가야 합니다.
빠른 확인법: 10번째 노드 주소를 알기 위해 앞 9개 링크를 거쳐야 합니다.
-
D거짓
현재 노드에는 이전 주소가 없으므로 별도 저장 없이 역방향으로 한 칸 이동할 수 없습니다.
빠른 확인법: 그림에서 왼쪽을 가리키는 화살표가 있는지 확인하세요. 없습니다.
4. 초보자가 가장 자주 틀리는 이유
- höchstens를 '정확히'로 번역한다.
- tail pointer 하나와 각 노드의 prev pointer를 같은 것으로 본다.
- 두 번 순회와 \(\Theta(2n)\)
Θ(2n)을 다른 성장급으로 생각한다. - 배열의 index access를 모든 선형 자료구조가 제공한다고 생각한다.
- 메모리에서 이전 노드가 어딘가에 있으니 자동으로 뒤로 갈 수 있다고 생각한다.
- 보조 stack이나 head 재탐색을 허용해 D를 참으로 만든다.
- 단일 연결과 이중 연결 용어를 놓친다.
5. 시험 답안 템플릿
단일 연결 노드는 (value,next)만으로 충분하므로 B는 거짓이고, 임의 인덱스는 head에서 순회해야 하므로 C는 거짓이며, prev가 없어 기본 역방향 순회가 불가능하므로 D도 거짓이다. 끝 삽입 두 번은 tail이 없으면 최대 두 번 순회하고 tail이 있으면 0번이므로 A의 'höchstens zwei'가 참이다. 정답 A.
6. 스스로 이해했는지 확인
단일 연결 노드의 최소 포인터 필드는?
정답: 다음 노드를 가리키는 next 하나입니다.
i번째 원소 접근의 일반적 시간은?
정답: \(\Theta(i)\)Θ(i), 최악 \(\Theta(n)\)Θ(n)입니다.
tail이 없을 때 append 시간은?
정답: 끝을 찾는 순회 때문에 \(\Theta(n)\)Θ(n)입니다.
tail이 있을 때 append 시간은?
정답: tail.next와 tail을 갱신하여 \(\Theta(1)\)Θ(1)입니다.
왜 기본 역방향 순회가 안 되는가?
정답: 노드가 prev 주소를 저장하지 않기 때문입니다.
I-3의 정답과 핵심 단어는?
정답: A이며 핵심은 hö\(\text{chstens}=\)chstens=최대입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.3
복기된 문제 문언과 선택지Vorlesung\03BasicDataStructures.pdf· pp. 22-25 and p. 38
단일·이중 연결 리스트 구조와 연산Übung\AuD26_Sheet05.pdf· pp. 1-2
연결 리스트 연습 문제Übung\AuD26_Sheet05-Sol.pdf· pp. 1-2
연결 리스트 공식 풀이와 포인터 구조